CODEWITHSUNDEEP
haskell
Rui Peres
Rui Peres

Reputation: 25927

Recursive call inside map

Having the following function:

between :: a -> [a] -> [[a]]
between i [] = [[i]]
between i r@(x:xs) = [[i]++r] ++ map f (between i xs)
                     where f = (\n->[x] ++ n)

And the result of between 0 [1,2] being:

[[0,1,2],[1,0,2],[1,2,0]]

How is this possible? I am able to understand the two first cases:

Is the map recursing as well? And keeping a reference to all initial x so it then just contacts all? In my head the final result would be something like:

[[0,1,2],[1,0,2],[2,0]]

PS: With "map recursing" as well is something a long the lines:

\n -> [1] + n
   \n ->[2] + n
      \n ->[3] + n
         \n ->[m] + n

Upvotes: 2

Views: 87

Answers (2)

bheklilr
bheklilr

Reputation: 54078

First of all, let's fix this function to use cons (:) rather than ++, since the former is more efficient and idiomatic when prepending an element to the front of a list, and it can also simplify the function a fair amount:

between i [] = [[i]]
between i r@(x:xs) = (i : r) : map (x:) (between i xs)

This will be easier to use to walk through the steps:

between 0 [1, 2] =
    (0 : [1, 2]) : map (1:) (between 0 [2])
    [0, 1, 2] : map (1:) ((0 : [2]) : map (2:) (between 0 []))
    [0, 1, 2] : map (1:) ([0, 2] : map (2:) [[0]])
    [0, 1, 2] : map (1:) ([0, 2] : [[2, 0]])
    [0, 1, 2] : map (1:) [[0, 2], [2, 0]]
    [0, 1, 2] : [1:[0, 2], 1:[2, 0]]
    [0, 1, 2] : [[1, 0, 2], [1, 2, 0]]
    [[0, 1, 2], [1, 0, 2], [1, 2, 0]]

So by equational reasoning, we can work out the steps GHC took to arrive at this answer.

Upvotes: 2

jamshidh
jamshidh

Reputation: 12070

But remember, between returns the result for the whole tail

between 0 [2]

gives

[[0, 2], [2, 0]]

applying f prepends 1 to everything

[[1, 0, 2], [1, 2, 0]]

Finally, we add the [[i]++r] (which would be better written as [i:r])

[[0, 1, 2], [1, 0, 2], [1, 2, 0]]

Upvotes: 1

Related Questions