Defining inits function recursively

Question

In Data.List module there's inits function that turns for example, [1,2,3,4] -> [[],[1],[1,2],[1,2,3],[1,2,3,4]]

I'm trying to define similar function using recursion, however I can't think of a way doing in correct order. The closest I have gotten is the list backwards, result = [[],[4],[3,4],[2,3,4],[1,2,3,4]]:

inits' :: [Int] -> [[Int]]
inits' [] = [[]]
inits' (x:xs) = inits' xs ++ [(x:xs)]

I'm not exactly sure how I could create a list by appending one element at time in the correct order? Could someone point in right direction, or is it not possible to do via recursion?

Answer 1

The easiest thing to try for such a function is just looking at the desired result and “reverse-pattern-matching” on the RHS of the function equation.

You already have that with

inits' [] = [[]]

Now with inits (x:xs), for example inits (1:[2,3,4]), you know that the result should be [[],[1],[1,2],[1,2,3],[1,2,3,4]], which matches the pattern []:_. So

inits' (x:xs) = [] : _

Now, the simplest recursion would be to just call inits' again on xs, like

inits' (x:xs) = [] : inits' xs

however, that doesn't give the correct result: assuming the recursive call works correctly, you have

inits' (1:[2,3,4]) = [] : [[],[2],[2,3],[2,3,4]]
                   = [[],[],[2],[2,3],[2,3,4]]

The 1 is completely missing, obviously, because we didn't actually use it in the definition. We need to use it, in fact it should be prepended before all of the list-chunks in the recursive result. You can do that with map.

Answer 2

We can prepend the data of all the remaining inits, like for example:

inits' :: [a] -> [[a]]
inits' [] = [[]]
inits' (x:xs) = [] : map (x:) (inits' xs)

As a basecase we return a singleton list with an empty list when the input is an empty list.

In the recursive case, we first yield the empty list, followed by the inits' of the tail of the list, but all these elements are prepended with x (with map (x:)).

Then we have:

Prelude> inits' [1,4,2,5]
[[],[1],[1,4],[1,4,2],[1,4,2,5]]

Since (not in evaluation order):

   inits' [1,4,2,5]
-> [] : map (1:) (inits' [4,2,5])
-> [] : map (1:) ([] : map (4:) (inits' [2,5]))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) (inits' [5])))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) ([] : map (5:) (inits' []))))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) ([] : map (5:) [[]])))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) ([] : [[5]])))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) [[],[5]]))
-> [] : map (1:) ([] : map (4:) ([] : [[2],[2,5]]))
-> [] : map (1:) ([] : map (4:) [[],[2],[2,5]])
-> [] : map (1:) ([] : [[4],[4,2],[4,2,5]])
-> [] : map (1:) [[],[4],[4,2],[4,2,5]]
-> [] : [[1],[1,4],[1,4,2],[1,4,2,5]]
-> [[],[1],[1,4],[1,4,2],[1,4,2,5]]