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

I think you should change your function definition from:

inits' :: [Int] -> [[Int]]

to:

inits' :: [a] -> [[a]]

Since inits from Data.List is of type [a] -> [[a]], and it doesn't care whats actually in the list. It needs to be polymorphic and accept a list of any type.

Furthermore, since others have shown the most straightforward recursive approach, you can also use foldr here.

Here is the base code:

inits' :: [a] -> [[a]]
inits' = foldr (\x acc -> [] : (map (x:) acc)) [[]]

Where [[]] is the base case, just like in your function. For the actual recursive part, here is how it works with the call inits' [1, 2, 3, 4]:

• Starts folding from the right at value 4, and creates [[], [4]]
• Now on value 3, and creates [[], [3], [3, 4]
• Now on value 2, and creates [[], [2], [2, 3], [2, 3, 4]]
• Now on value 1, and creates [[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]

Which gives the final nested list required, similarily to the function call:

*Main> inits' [1,2,3,4]
[[],[1],[1,2],[1,2,3],[1,2,3,4]]

From the behavior described above, you just need to focus on [] : (map (x:) acc), where you map the current value x being folded into your accumulated list acc, while also prepending an empty list on each fold.

If you still have trouble understanding foldr, you can look at this minimal example of how the folding performs from the right:

foldr f x [a, b, c] = a `f` (b `f` (c `f` x))

and How does foldr work?

Answer 2

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 3

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]]