首先,什么是
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
and
concatMap f xs == foldr ((++).f) [] xs
所以它可以逐步工作。对于您的示例,
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
= 1:take 5 xs1 where xs=1:xs1; xs1=next xs
= 1:take 5 xs1 where xs1=2:10:next xs1
= 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
= 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
....
concatMap
会连接和映射xs
,因为它接收到的参数就是这个。我不清楚您在这里困惑的是什么。 - ApproachingDarknessFishxs
的递归定义。 - melpomene[1] ++ concatMap (\x -> [x+1,x*10]) ([1] ++ concatMap (\x -> [x+1,x*10]) ([1] ++ concatMap (\x -> [x+1,x*10]) (...)))
。 - Daniel Wagner