How to expand haskell expressions?

Abhishek Rajpoot 0
Viewed 71

How to expand

concat( map (interleave 2) [[3,4][4,3]])

interleave::a->[a]->[[a]]
interleave x []=[[x]]
interleave x (y:ys)=(x:y:ys):map (y:) (interleave x ys)

I used ghci interpreter and got the following answer:

[[2,3,4],[4,2,3],[3,4,2],[2,4,3],[3,2,4],[4,3,2]]

I run the following code :

map (interleave 2) [[3,4][4,3]]

and got the output :

[[[2,3,4],[4,2,3],[3,4,2]],[[2,4,3],[3,2,4],[4,3,2]]]

When I do dry run I did the following:

concat( map (interleave 2) [[3,4][4,3]])
=>
concat( interleave 2 [3,4], interleave 2 [4,3])
=>
concat([[2,3,4],[4,2,3],[3,4,2]],[[2,4,3],[3,2,4],[4,3,2]])
=>
[2,3,4,4,2,3,3,4,2,2,4,3,3,4,2,4,3,2]

Can someone please explain how the expression evaluated?

haskell
1 Answers

The parenthesis are confusing. The map (interleave 2) [[3,4], [4,3]] will produce a list. Indeed:

   map (interleave 2) [[3,4][4,3]]
-> [interleave 2 [3, 4], interleave 2 [4, 3]]

now interleave will produce itself a list of lists where it inserts items at any possible insertion point, so:

   [interleave 2 [3, 4], interleave 2 [4, 3]]
-> [[[2, 3, 4], [3, 2, 4], [3, 4, 2]], [[2, 4, 3], [4, 2, 3], [4, 2, 3]]]

This is thus a list of lists of lists of integers. Now we concatenate those, so that means that the two lists that are elements of the outer list are concatenated, so:

   concat [[[2, 3, 4], [3, 2, 4], [3, 4, 2]], [[2, 4, 3], [4, 2, 3], [4, 2, 3]]]
-> [[2, 3, 4], [3, 2, 4], [3, 4, 2], [2, 4, 3], [4, 2, 3], [4, 2, 3]]
Willem Van Onsem0
Related