haskell - 理解 concatMap 递归

Question

我总体上很困惑，并正在寻找关于此代码如何工作的非常详细和解释性的答案:

let xs = [1] ++ concatMap (\x -> [x+1,x*10]) xs in xs

concatMap 如何知道要映射和连接什么？

我了解更多基本示例:

let x = [1] ++ x

这里它的评估方式如下:[1]++ [1]++ [1] ..

但我似乎不理解 concatMap 的第一个示例。这对我来说没有意义。我可以经常使用递归，没有任何问题。然而，那一段代码非常困惑。

Answer 1

让我们尝试一个更简单的示例:

let xs = 1 : xs in xs

好的，所以xs指向(:)节点。这里的头指针指向1 ，尾指针指向 xs (即回到自身)。所以这要么是一个循环列表，要么是一个无限列表。 ( haskell 认为两者是同一件事。)到目前为止，一切都很好。

现在，让我们尝试一个更难的示例:

let xs = 1 : map (+1) xs in xs

你知道这会做什么吗？

所以xs指向(:)节点。头指针指向 1。尾指针指向表达式 map (+1) xs ，与 xs再次指向顶部。

如果您尝试“查看”此列表的内容，则会导致map表达式开始执行。 map的定义是

map f js =
  case js of
    k:ks -> (f k) : (map f ks)
    []   -> []

所以map看看xs看看是否是[]或(:) 。据我们所知，它是 (:) 。所以第一个模式适用。

这意味着整个map (+1) xs表达式被 (:) 覆盖，其头指针指向 (+1) 1其尾部指针指向map (+1) xs2 ( xs2 表示指向 xs 尾部的指针)。

此时，检查(+1) 1将其变成2 。所以现在我们基本上有了

xs = 1 : 2 : map (+1) xs2
           ^           |
           |___________|

当您检查列表时，会重复此循环。至关重要的是，每时每刻map指向其自身之前的一个节点。如果它追上了自己，你就会遇到问题。但是map只查看我们已经计算过的节点，所以没问题。

最终结果是 xs = 1 : 2 : 3 : 4 : ...

如果您能理解这一点，您应该能够理解您自己的更复杂的示例。

如果您想让让自己头疼，请尝试:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

这是一个标准的 Haskell 咒语，用于在 O(N) 时间内吐出斐波那契数(而不是 O(N*N)，因为更明显的递归会给你带来)。