这个毫无疑问的愚蠢问题的灵感来自在Haskell中这个列表排列实现到底做了什么?
假设
perms [] = [[]]
perms xxs = [ (y:ys) | ( y, xs ) <- pix xxs , ys <- perms xs ]
--where
pix [] = []
pix ( x:xs ) = ( x , xs ) : [ ( y, x : ys ) | ( y, ys ) <- pix xs ]
Twan van Laarhoven写道:"这个函数做的第一件事是从整个列表中选择第一个元素，这一点也不懒惰。"好的——当然!但我很困惑-
我不明白为什么ghci会这样做:
*Main> let p = perms [1..]
*Main> let hs = map head p
*Main> take 1 hs
*** Exception: stack overflow
为什么ghci不能打印[1]?
叹息……彼得
回答评论:
正如我在回复卡斯滕的回答时所说的，我已经"推理"出我的
*Main> let hs = map head p
*Main> take 1 hs
加上Haskell的惰性，将允许ghci不计算(y:ys) in perms中的ys，因为上面只"想要"第一个'y'的值;简而言之，我认为我并没有真正计算第一个烫发期[1.]一点也不。但是，正如卡斯滕和里德·巴顿实际上指出的那样，懒惰不是重点，我的论点是错误的。
添加(我希望不是弄乱)他们的答案，如果
ans = take 1 hs
那么，由于perms定义中的列表推导式，
ans is in the image of some function from the Cartesian product
(pix [1..]) X perms [2..].
但是我怎么知道笛卡尔积，函数的定义域，不是空集呢?否则，ans就不存在了……(也就是说，我怎么知道第一学期[1..])存在吗?或者，正如里德·巴顿(Reid Barton)更简洁地说的那样，我怎么知道烫发[1…)
当且仅当每个因子不为空时，乘积不为空。我知道第一个不是空的(检查!)-但我怎么知道烫发[2..]因子不是空的吗?哦，唉，递归地说，我死了。
让我们看看它要做什么(让我们使用GHCi调试器)
λ> :break perms
Breakpoint 0 activated...
λ> perms [1..]
Stopped at perms
λ> :step
Stopped at RHS perms xxs
xxs :: [Integer] = 1 : _
λ> :step
Stopped at RHS perms xxs (comprehension)
xxs :: [Integer] = 1 : _
λ> :step
Stopped at pix
λ> :step
Stopped at RHS pix (x:xs)
x :: Integer = 1
xs :: [Integer] = _
λ> :step
Stopped at RHS perms xxs (comprehension)
xs :: [t] = _
λ> :step
Stopped at perms
λ> :step
Stopped at rhs perms xxs
_result :: [[Integer]] = _
xxs :: [Integer] = 2 : _
...
我试着翻译一下位置，我删除了所有，但最后一个_result(在那里你看到它仍然不在任何WHNF列表中)
最重要的是最后一行:你能看到你进入了和开头一样的行，但是现在是无限列表的尾部吗?
这是因为你画了ys <- perms xs，如果你继续你会看到xxs = 3 : _…
最后，你必须遍历所有的列表才能得到任何结果——这在这里当然是不可能的。
评论
take 1 $ perm [1..]在这里不会改变任何东西，因为它必须对上述表达式的结果进行评估，直到它得到_:_或[]，但正如您所看到的，它永远不会这样做-当然，如果您添加诸如
first () = take 1 $ perms [1..]
，然后做
:break first
first ()
: step
-我认为这是一种有趣的探索方式-尽管它可能有点乏味
回复你的评论
lazy不是一个简单的概念，是的，原则上你的推理还不错——但是take和map都需要将给定的列表解构成类似_:_的东西，现在这意味着你至少需要看到列表的(:)构造函数(或者[]) -但是在这里(正如我试图用调试会话向你展示的那样)列表的块永远不会达到这个状态(如果s the _result '部分)-这不是Haskell中懒惰的问题，而是与你的算法/算法的实现细节有关。
看到它可以工作，你只需要看看Data.List中的permutations -如果你试着用它来运行你的代码，它会工作得很好:
λ> import Data.List (permutations)
λ> map head . take 1 $ permutations [1..]
[1]
λ>
λ> import Data.List (permutations)
λ> take 1 $ permutations [1..]
但是这当然会继续打印直到时间结束(内存之类的)
如果你感兴趣的话，你可以看看permutations的实现。
你怎么知道perms [1..]是非空的?