Haskell 中的无限列表

Question

我正在尝试定义一个函数，以在我的简单语法中创建所有可能单词的无限列表。但是当我输入 head (generate [] []) 时 ghci 冻结了，尽管 head (generate' [] []) 工作正常（但我仍然想要一个无限列表）。有什么问题？

data Start = Start deriving(Show)
data MyExpr = MyExprStart Start | MyExpr1 MyExpr | MyExpr2 MyExpr deriving(Show)

generate :: [MyExpr] -> [MyExpr] -> [MyExpr]
generate [] []         = generate [MyExprStart Start] []
generate current prev  = generate (concatMap nextExprs current) (prev ++ current)

generate' :: [MyExpr] -> [MyExpr] -> [MyExpr]
generate' [] []         = generate' [MyExprStart Start] []
generate' current prev  =
  if (length current + length prev) < 5 then
    generate' (concatMap nextExprs current) (prev ++ current)
  else prev ++ current

nextExprs :: MyExpr -> [MyExpr]
nextExprs expr = [MyExpr1 expr, MyExpr2 expr]

更新：谢谢，我明白了。我想我应该这样定义我的函数：

generate :: [MyExpr] -> [MyExpr]
generate []         = generate [MyExprStart Start]
generate current    = current ++ generate (concatMap nextExprs current)

Answer 1

generate :: [MyExpr] -> [MyExpr] -> [MyExpr]
generate ... = generate ...
generate ... = generate ...

此表单的任何定义在产生任何输出之前总是会调用自身。这种归纳结构只有在至少在某些时候 returns 递归之前输出的某些部分才能定义，例如发出输出列表的第一个元素。

generate' :: [MyExpr] -> [MyExpr] -> [MyExpr]
generate' [] []         = generate' [MyExprStart Start] []
generate' current prev  =
  if (length current + length prev) < 5 then
    generate' (concatMap nextExprs current) (prev ++ current)
  else prev ++ current

相比之下，在 generate' 中，else 分支不会递归，因此它会产生输出。即使我们有类似

的东西

else someNonEmptyList ++ generate' ...

这可行，因为会生成前几个列表元素。

此外，请记住，生成所有可能的表达式将潜在的无限列表与 ++ 合并是一个坏主意。事实上，如果 xs 是无限的，那么 xs ++ ys 等于 xs，因为 ys 永远不会在有限的时间内到达。当 xs 和 ys 无穷大时，您可能希望它们公平交错。

A similar question used the omega monad 实现了完整枚举。

Answer 2

generate 函数冻结，因为它编码了无限递归。看：它的每个案例都只是调用函数本身。当它实际上 returns 不是对自身的调用时，没有任何条件。因此，当您尝试运行它时，它只会永远调用自己。

另一方面，generate' 函数将在两个输入列表的总长度超过 5 时立即退出。所以这就是 return 给你的结果。

要使此函数在完全评估之前开始 returning 数据（它永远不会这样做），您需要首先 return 非递归案例，然后将递归案例附加到他们通过递归调用 generate：

generate = (MyExprStart Start) : [recur e | e <- generate, recur <- [MyExpr1, MyExpr2]]

GHCi:

> head generate
MyExprStart Start
> take 10 generate
[MyExprStart Start, MyExpr1 (MyExprStart Start),
 MyExpr2 (MyExprStart Start), MyExpr1 (MyExpr1 (MyExprStart Start)),
 MyExpr2 (MyExpr1 (MyExprStart Start)),
 MyExpr1 (MyExpr2 (MyExprStart Start)),
 MyExpr2 (MyExpr2 (MyExprStart Start)),
 MyExpr1 (MyExpr1 (MyExpr1 (MyExprStart Start))), 
 MyExpr2 (MyExpr1 (MyExpr1 (MyExprStart Start))),
 MyExpr1 (MyExpr2 (MyExpr1 (MyExprStart Start)))]

注意：列表理解中生成器的顺序很重要。如果交换它们，执行将永远不会到达 MyExpr2，因为它需要先耗尽 generate 列表，而该列表是无限的。

Haskell 中的无限列表

Infinite list in Haskell

haskell

functional-programming

lazy-evaluation