代码之家 › 专栏 › 技术社区 › Jonno_FTW

列表理解在haskell中不能给出正确的结果

list-comprehension haskell

Jonno_FTW · 技术社区 · 16 年前

我正在做 project euler question 136 ,并提出了以下测试示例:

module Main where
import Data.List

unsum x y z n = (y > 0) && (z > 0) && (((x*x)  - (y*y)- (z*z)) == n) && ((x - y) == (y - z))
answer = snub $ takeWhile (<100) [n|x<-[1..],d<-[1..x`div`2],n<-[x..100],y<-[x-d],z<-[y-d], unsum x y z n ]
    where 
      snub [] = []
      snub (x:xs) | elem x xs = snub (filter (/=x) xs)
                  | otherwise = x : snub xs

snub 将从列表中删除所有重复的数字。

这个例子应该给出25个解决方案 n 在哪里? x^2 - y^2 - z^2 == n 所有的数字都是正的(或者我从问题中收集到的),是一个算术级数,这样 x-y == y-z .但是当我使用代码时,会列出11个解决方案 n 返回。

我在清单理解上做了什么错事,我遗漏了哪些优化?

1 回复 | 直到 11 年前

barkmadley 16 年前

第1点

我试过这个问题,发现这是 n 是我想出的

[4,3,16,12,7,20,11,48,28,19,80,44,23,52,112,31,68,76,1156,43,176,559...

这可能意味着 takeWhile (<100) 用于确定何时停止的筛选函数是否错误。在相关说明中,我尝试运行此:

answer = snub $ filter (<=100) $ takeWhile (<200) [...listcomprehension...]

但我放弃了,因为时间太长了。这就引出了第二点。

第2点

在优化方面,看看你的列表理解在原始输出方面产生了什么。

Main> take 30 [(x,y,z,n) | x<-[1..], d<-[1..x`div`2], n<-[x..100], y<-[x-d], z<-[y-d]]
[(2,1,0,2),(2,1,0,3),(2,1,0,4),(2,1,0,5),(2,1,0,6),(2,1,0,7),(2,1,0,8),(2,1,0,9),
(2,1,0,10),(2,1,0,11),(2,1,0,12),(2,1,0,13),(2,1,0,14),(2,1,0,15),(2,1,0,16),(2,1,0,17),
(2,1,0,18),(2,1,0,19),(2,1,0,20),(2,1,0,21),(2,1,0,22),(2,1,0,23),(2,1,0,24),(2,1,0,25),
(2,1,0,26),(2,1,0,27),(2,1,0,28),(2,1,0,29),(2,1,0,30),(2,1,0,31)]

这意味着对x y z和n的每个组合调用unsm,这有点多余,因为我们知道 2^2 - 1^2 - 0^2 = 3 .

移动 N号 从列表理解(因为上面的原因而变慢)到一个函数,仅仅是列表理解 (x,y,z) 有效的组合。

ns = map nsum [(x, x-d, x-d-d) | x <- [1..], d <- [1..x`div`2]]
nsum (x,y,z) = x^2 - y^2 - z^2

然后就可以从这个无限列表中计算出答案了,但是要注意使用takewhile。

推荐文章

Honza S. · 在列表理解中更新词典

2 年前

Suyash Nachankar · 为什么矩阵的所有行都与最后一行相同?

2 年前

kesarling · 这个Haskell列表理解是如何评估的?

2 年前

Ruslan199 · python中的条件列出了理解

2 年前

Chris · 如何在OpenSCAD中的FOR循环中成对创建矢量元素

2 年前

Jme · 为什么在Python中解包时理解只适用于元组?

2 年前

WeCanDoItGuys · 使用列表理解创建一副多副牌[重复]

2 年前

tonydanza123 · 如果值不存在,则列表理解返回列表

2 年前

user21641220 · 是否可以通过单一理解来检查一组中的任何项目是否在另一组中?

2 年前

SkyMonkey · Python函数返回一个新列表,该列表包含回文字符串和偶数长度的字符串

2 年前