Can the head of a list ever represent more than one value

Question

If I call the function `interleave` (defined below - it's a function to insert a number (or any type) at each position of a list) like this the resulting lists are all the same length ``` interleave 1 [2,3,4] [[1,2,3,4],[2,1,3,4],[2,3,1,4],[2,3,4,1]] ``` However, I expected the list lengths to be increasingly shorter because the recursive call to `interleave` passes the list minus the head (i.e only `ys`). Since the tail of the list keeps getting shorter with each call, I expect the resulting lists to be shorter. ``` interleave :: a -> [a] -> [[a]] interleave x [] = [[x]] interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys) ``` How do the lists end up being the same length if the list argument to the recursive call is increasingly shorter? The only answer I can imagine is that the mapped value `map (y:)` represents more than one digit in the recursive calls (i.e. it's the 2 in [2,1,3,4] and the `2,3` in [2,3,1,4] and the `2,3,4` in [2,3,4,1]` but I'm not sure if that's possible…

Accepted Answer

The list lengths of the recursive calls are indeed progressively shorter; however, the function modifies the results from the recursive calls to lengthen them. Let's build up from the bottom. For empty lists, nothing interesting happens:

```
interleave 1 []
= { first clause of definition }
[[1]]
```

But by the time we get to a list with one element, we already see the interesting thing happening. Specifically, since the result of the recursive call is passed to `map (y:)`, the short lists produced by the recursive call are each expanded by one element.

```
interleave 1 [4]
= { list syntax }
interleave 1 (4:[])
= { second clause of definition }
(1:4:[]) : map (4:) (interleave 1 [])
= { recursive call, which produces short answers }
(1:4:[]) : map (4:) [[1]]
= { definition of map, which lengthens each answer }
(1:4:[]) : [4:[1]]
= { list syntax }
[[1,4],[4,1]]
```

In a similar way, `interleave 1 [3,4]` makes the recursive call `interleave 1 [4]` to produce `[[1,4],[4,1]]`, but then uses `map (3:)` to lengthen each element of that to `[[3,1,4],[3,4,1]]`.

Addressing your direct questions in turn now:

How do the lists end up being the same length if the list argument to the recursive call is increasingly shorter?

Each time a recursive call on a shorter list is made, the results of the recursive call are made longer -- these are exactly balanced out so that calling `interleave` with a length-`n` list will result in a collection of length-`n+1` lists.

can `y` (the head of the list) represent more than a single value in the recursive calls?

No, the head of a list is always a single value. The real magic is that each recursive call is adding onto the head -- so you can get many extra heads from many recursive calls.

confirm/explain if the `(x:y:ys)` in `(x:y:ys) : map (y:) (interleave x ys)` only ever represents one list (i.e. it is the `[1,2,3,4-` with the integer argument inserted in the first position).

Correct.

Can the head of a list ever represent more than one value

Solution

Problem