为什么 ghci 不能打印整数第一个排列的头部，计算 'selection-style'？
why can't ghci print the head of the first permutation of the integers, calculated 'selection-style'?
这个毫无疑问的低能问题的灵感来自
What does this list permutations implementation in Haskell exactly do?
假设
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 写道 "the first thing this function does is pick the first element from the entire list, which is not lazy at all." 好的 - 当然！但是我很困惑-
我不明白为什么 ghci 会执行以下操作：
*Main> let p = perms [1..]
*Main> let hs = map head p
*Main> take 1 hs
*** Exception: stack overflow
为什么 ghci 不能打印 [1]？
唉...
彼得
对答案的评论：
正如我在回复 Carsten 的回答时所说，我'reasoned'
*Main> let hs = map head p
*Main> take 1 hs
连同 Haskell 的懒惰，将允许 ghci 在 perms 中不计算 (y:ys) 中的 ys，因为上面只有 'wanted' 第一个 [=48] 的值=];简而言之，我在争论我根本没有真正计算 perms [1..] 的第一项。
但是，正如 Carsten 和 Reid Barton 实际上在下面指出的那样，懒惰不是重点，我的论点是错误的。
如果
添加到（我希望不要破坏）他们的答案
ans = take 1 hs
然后，由于 perms 定义中的列表理解，
ans is in the image of some function from the Cartesian product
(pix [1..]) X perms [2..].
但是我怎么知道笛卡尔积（我的函数的域）不是空集？因为，否则，ans 不存在...（即，我怎么知道 perms[1..] 的第一项存在？或者，正如 Reid Barton 更简洁地说的那样，我怎么知道 perms[1..] 的第一项存在？ .] 不为空？)
当且仅当每个因素不为空时，产品不为空。我知道第一个不为空（检查！）——但我怎么知道 perms [2..] 因子不为空？哦——唉，通过递归，我死定了。
你怎么知道 perms [1..] 是非空的？
好吧，让我们看看它必须做什么（让我们使用 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
在 ghci 中 - 我认为这是一种有趣的探索方式 - 尽管它可能有点乏味
回复您的评论
lazy 不是一个简单的概念是的，原则上你的推理还不错 - 但 take 和 map 都需要将给定列表解构为 _:_ 之类的东西，现在这个意味着您至少需要查看列表的 (:) 构造函数（或 [] ）-但是在这里（正如我试图通过调试会话向您展示的那样） 列表的 chunk 永远不会达到这个状态（它 s the_result` 部分） - 这不是 problem Haskell 中的惰性但是你的算法/算法的实现细节。
要查看它 可以 工作，您只需要查看 Data.List 中的 permutations - 如果您尝试 运行 你的代码将正常工作：
λ> import Data.List (permutations)
λ> map head . take 1 $ permutations [1..]
[1]
λ>
也是这样：
λ> import Data.List (permutations)
λ> take 1 $ permutations [1..]
但是当然这将继续打印直到时间结束（内存，无论什么）
如果你有兴趣，你也可以看看implementation of permutations。
这个毫无疑问的低能问题的灵感来自 What does this list permutations implementation in Haskell exactly do?
假设
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 写道 "the first thing this function does is pick the first element from the entire list, which is not lazy at all." 好的 - 当然！但是我很困惑-
我不明白为什么 ghci 会执行以下操作：
*Main> let p = perms [1..]
*Main> let hs = map head p
*Main> take 1 hs
*** Exception: stack overflow
为什么 ghci 不能打印 [1]？
唉...
彼得
对答案的评论：
正如我在回复 Carsten 的回答时所说，我'reasoned'
*Main> let hs = map head p
*Main> take 1 hs
连同 Haskell 的懒惰，将允许 ghci 在 perms 中不计算 (y:ys) 中的 ys，因为上面只有 'wanted' 第一个 [=48] 的值=];简而言之，我在争论我根本没有真正计算 perms [1..] 的第一项。 但是，正如 Carsten 和 Reid Barton 实际上在下面指出的那样，懒惰不是重点，我的论点是错误的。
如果
添加到（我希望不要破坏）他们的答案 ans = take 1 hs
然后，由于 perms 定义中的列表理解，
ans is in the image of some function from the Cartesian product
(pix [1..]) X perms [2..].
但是我怎么知道笛卡尔积（我的函数的域）不是空集？因为，否则，ans 不存在...（即，我怎么知道 perms[1..] 的第一项存在？或者，正如 Reid Barton 更简洁地说的那样，我怎么知道 perms[1..] 的第一项存在？ .] 不为空？)
当且仅当每个因素不为空时，产品不为空。我知道第一个不为空（检查！）——但我怎么知道 perms [2..] 因子不为空？哦——唉，通过递归，我死定了。
你怎么知道 perms [1..] 是非空的？
好吧，让我们看看它必须做什么（让我们使用 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
在 ghci 中 - 我认为这是一种有趣的探索方式 - 尽管它可能有点乏味
回复您的评论
lazy 不是一个简单的概念是的，原则上你的推理还不错 - 但 take 和 map 都需要将给定列表解构为 _:_ 之类的东西，现在这个意味着您至少需要查看列表的 (:) 构造函数（或 [] ）-但是在这里（正如我试图通过调试会话向您展示的那样） 列表的 chunk 永远不会达到这个状态（它 s the_result` 部分） - 这不是 problem Haskell 中的惰性但是你的算法/算法的实现细节。
要查看它 可以 工作，您只需要查看 Data.List 中的 permutations - 如果您尝试 运行 你的代码将正常工作：
λ> import Data.List (permutations)
λ> map head . take 1 $ permutations [1..]
[1]
λ>
也是这样：
λ> import Data.List (permutations)
λ> take 1 $ permutations [1..]
但是当然这将继续打印直到时间结束（内存，无论什么）
如果你有兴趣，你也可以看看implementation of permutations。