了解concatMap递归

Question

我非常困惑，希望能得到一个详细的解释，让我理解这段代码是如何工作的:

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

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

我可以理解更基础的例子：

let x = [1] ++ x

这里它会被评估为 [1] ++ [1] ++ [1] ..

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

- Afonso Matos

---

concatMap 会连接和映射 xs，因为它接收到的参数就是这个。我不清楚您在这里困惑的是什么。 - ApproachingDarknessFish

@TuttiFruttiJacuzzi 这是 xs 的递归定义。 - melpomene

对于你理解的直接类比，它会被评估为[1] ++ concatMap (\x -> [x+1,x*10]) ([1] ++ concatMap (\x -> [x+1,x*10]) ([1] ++ concatMap (\x -> [x+1,x*10]) (...)))。 - Daniel Wagner

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) 的时间）。

- MathematicalOrchid

Answer 2

将concatMap视为concat . map（concat和map的简单组合）。

在这种情况下，您正在使用1初始化xs。一旦开始运行映射，它将提升lambda以在1上操作（列表中的第一个位置），并创建包含两个值2和10的列表。Concat只是从该列表中提取这两个值，并将它们裸露地放入xs中，并与现有的1连接起来。此时，xs包含1、2和10（xs = [1,2,10]）。

现在，xs包含1、2和10，而map将重复此过程（当然，从列表中的第二个位置开始），现在在2上操作并创建包含3和20以及在10（列表中的第三个位置）上操作时创建包含11和100的第二个列表。Concat现在将提取这4个值并将它们附加到xs的内容中。现在，xs包含1、2、10、3、20、11和100（xs = [1,2,10,3,20,11,100]）。

你可以重复这个过程，这次将map操作应用于列表中的第四个位置（以及每个后续位置），并且concat会执行其工作，以删除新列表容器并将值直接放入顶级列表。正如你所看到的，这个过程会生成一个无限的列表。

这有帮助吗？

- fgv

Answer 3

首先，什么是concat？它将以列表形式呈现的列表连接起来：

concat [ [1], [2],    [3] ] = [ 1, 2, 3 ]
concat [ [1], [2,22], [3] ] = [ 1, 2, 22, 3 ]

等等。 map 是什么？它会转换其所呈现的列表中的每个元素：

map (1+)               [1, 2, 3] = [ 2, 3, 4 ]
map (:[])              [1, 2, 3] = [ [1], [2], [3] ]
map (\x-> [x+1, x*10]) [1, 2, 3] = [ [2,10], [3,20], [4,30] ]

但是concatMap f xs与concat (map f xs)是相同的：

concatMap (\x-> [x+1, x*10]) [1, 2, 3] 
 = concat (map (\x-> [x+1, x*10]) [1, 2, 3])
 = concat [ [2,10], [3,20], [4,30] ]
 = [ 2,10, 3,20, 4,30 ]

但是，它不需要将输入列表处理到末尾，就可以逐个生成其元素以便进行后续操作。这是由于Haskell的惰性计算。简而言之，

   concat [ [2,10], [3,20], [4,30] ]
 = [ 2,10, 3,20, 4,30 ]
 = [ 2,10] ++ concat [ [3,20], [4,30] ]

这意味着实际上，

concat xs == foldr (++) [] xs
-- concat [a,b,...,n] = a ++ (b ++ (... ++ (n++[])...))

and

concatMap f xs == foldr ((++).f) [] xs
-- concatMap f [a,b,...,n] = f a ++ (f b ++ (... ++ (f n++[])...))

所以它可以逐步工作。对于您的示例，

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

这意味着：xs是一个列表，其中包含1，然后对于xs中的每个元素x，依次包含x+1和x*10 - 再次从开头开始。我们也可以将其写成这样。

xs = 1 : [y | x <- xs, y <- [x+1, x*10]]

所以对于1，2和10将被“追加”到列表的末尾，然后对于2，将生成3和20，对于10- 11和100，依此类推：

xs =   1    a    b    c    d    e    f    g    h ....
    [2,10]=[a,b]
   =   1    2   10    c    d    e    f    g    h ....
          [3,20]=[c,d]
   =   1    2   10    3   20    e    f    g    h ....
               [11,100]=[e,f]
       ....

当然，这个定义不会被单独评估；它是“休眠”的，直到被使用，例如打印xs的前6个元素：

Prelude> let xs = 1 : [y | x <- xs, y <- [x+1, x*10]]
Prelude> take 6 xs
[1,2,10,3,20,11]

正如我们所看到的，这里真正定义的不是一个无限列表 - 毕竟没有无限的东西 - 而是计算其元素所需的过程。

另一种编写此定义的方法是

xs = 1 : next xs
         where
         next (x:xs) = x+1 : x*10 : next xs

在这里，计算的结构变得更加清晰： next 在被定义时会“回顾”到 xs，首先是向后 1 格；然后是 2 格；然后是 3 格；以此类推（因为它为每个消耗的元素产生两个新的列表元素；因此这个定义是 有生产力的）。这是一种 “共递归” 定义的特征。它的计算过程如下：

take 6 xs
 = take 6 xs where xs=1:next xs                   -- next looks 1 element back
 = 1:take 5 xs1 where xs=1:xs1; xs1=next xs
 = 1:take 5 xs1 where xs1=2:10:next xs1                -- 2 elements back
 = 1:2:take 4 xs2 where xs1=2:xs2; xs2=10:next xs1
 = 1:2:10:take 3 xs3 where xs1=2:xs2; xs2=10:xs3; xs3=next xs1
 = 1:2:10:take 3 xs3 where xs2=10:xs3; xs3=3:20:next xs2       -- 3 elements 
 = 1:2:10:3:take 2 xs4 where xs2=10:xs3; xs3=3:xs4; xs4=20:next xs2
 = 1:2:10:3:20:take 1 xs5 where xs2=10:xs3; xs3=3:xs4; xs4=20:xs5; xs5=next xs2
 = 1:2:10:3:20:take 1 xs5 where xs3=3:xs4; xs4=20:xs5; xs5=11:100:next xs3     -- 4 
 ....

- Will Ness