Understanding the concatMap recursion
I'm generally confused and looking for a very detailed and explanatory answer on how this code works:
let xs = [1] ++ concatMap (\x -> [x+1,x*10]) xs in xs
How does concatMap know what to display and concat?
I understand simpler examples:
let x = [1] ++ x
Here it is evaluated as [1] ++ [1] ++ [1] ..
But I don't seem to understand the first example with concatMap. It just doesn't make sense to me. I can often work with recursion without problems. However, one piece of code is very confusing.
source to share
Try a much simpler example:
let xs = 1 : xs in xs
OK, so it xs
points to (:)
node. The head pointer from here points to 1
, and the tail pointer points to xs
(i.e. back to yourself). So it is either a circular list or an infinite list. (Haskell sees them as the same thing.) So far so good.
Now try a more complex example:
let xs = 1 : map (+1) xs in xs
Do you know what this will do?
So, xs
points to a (:)
node. The head pointer points to 1. The tail pointer points to the expression map (+1) xs
, which xs
will go back to the beginning.
If you try to "look" at the contents of this list, it will cause the expression to map
start executing. The definition map
is
map f js =
case js of
k:ks -> (f k) : (map f ks)
[] -> []
So map
looks at xs
to see if he is []
or (:)
. As you know, it is (:)
. Thus, the first pattern is applied.
This means that the whole expression is map (+1) xs
overwritten with (:)
with its pointer pointing to (+1) 1
, and its pointer pointing to map (+1) xs2
(with xs2
indicating the tail pointer xs
).
At this point, the check (+1) 1
turns him into 2
. So now we basically have
xs = 1 : 2 : map (+1) xs2 ^ | |___________|
This cycle repeats when browsing the list. Critically, every moment map
points to a node directly in front of it. If he ever catches up with himself, you have a problem. But map
only ever looks at the nodes we have already computed, so that's okay.
So the bottom line is xs = 1 : 2 : 3 : 4 : ...
If you understand this, you should understand your more complex example.
If you want to hurt yourself, try:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
This is Haskell's standard spell for splashing Fibonacci numbers in O (N) time (not O (N * N), as the more obvious recursion will give you).
source to share
Think of concatMap as a simple composition of concat and map (concat. Map).
In this particular case, you initialize xs with 1. After you run your map, it will raise the lambda to work with 1 (the first position in the list) and create a list containing two values: 2 and 10 Concat just fetches those two values from of this list and puts them naked in xs, concatenating them with the existing 1. At this moment xs contains 1, 2 and 10 (xs = [1,2,10]).
Now xs contains 1, 2 and 10, and the card will repeat the process (starting from the second position in the list of course), now runs on 2 and creates a list containing 3 and 20, and a second list containing 11 and 100 when running on 10 ( third position in the list). Concat will now extract these 4 values and add them to the xs content. Now xs contains 1, 2, 10, 3, 20, 11 and 100 (xs = [1,2,10,3,20,11,100]).
And you can rinse and repeat, this time the card acting at the fourth position in the list (and each subsequent position), and concat does its job to remove the new list containers and put the values directly into the top-level list. As you can see, this process will generate this endless list.
Does it help?
source to share
First, what is it concat
? It combines the lists presented to it in the list:
concat [ [1], [2], [3] ] = [ 1, 2, 3 ]
concat [ [1], [2,22], [3] ] = [ 1, 2, 22, 3 ]
etc. What does it do map
? It converts each item to a list that is presented:
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] ]
But it concatMap f xs
matches 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 ]
But he doesn't need to see the list of inputs all the way to continue creating his elements one by one. This is due to Haskell's laziness. Simply put,
concat [ [2,10], [3,20], [4,30] ]
= [ 2,10, 3,20, 4,30 ]
= [ 2,10] ++ concat [ [3,20], [4,30] ]
This means that in fact
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++[])...))
so it works gradually. For your example
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
This simply means: xs
- a list containing 1
, and then x+1
and x*10
for each element x
in the xs
- from the very beginning. We could also write this as
xs = 1 : [y | x <- xs, y <- [x+1, x*10]]
So for 1, 2 and 10 will be added "to the end" and then for 2, 3 and 20 will be created for 10-11 and 100, etc .:
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]
....
Of course, this will not be judged by itself; the definition is "dormant" prior to use, for example. to print the first 6 elements xs
:
Prelude> let xs = 1: [y | x <-xs, y <- [x + 1, x * 10]]
Prelude> take 6 xs
[1,2,10,3,20,11]
As we can see, what has actually been defined here is not an infinite list - after all, there are no infinite things - but the process of calculating as many of its elements as possible.
Another way of writing this definition is
xs = 1 : next xs
where
next (x:xs) = x+1 : x*10 : next xs
where the structure of the computation is even clearer: next
"looks back" at xs
as it is defined, 1 barb first; then 2; then 3; etc. (because it produces two new list items for each one that it consumes, so this definition is productive). This is characteristic of the "recursive" definition. Its calculation continues as
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
....
source to share