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?

@WillemVanOnsem, that's a pretty good approach most of the time, but to get optimal performance even in weird cases, it's better to use a proper queue. — dfeuer, Jan 16 '18 at 14:28
In particular, forcing the entire result should be O(n^2), but reaching any element of any result list should ideally be O(i+k) (i.e., the distance to that element). Accomplishing both of those simultaneously seems to require a persistent queue. — dfeuer, Jan 16 '18 at 15:27
@dfeuer `map ($[]) . scanl (\a x-> a . (x:)) id` seems to fulfill both of your requirements. am I missing something? — Will Ness, Jan 16 '18 at 16:11
This [question](https://stackoverflow.com/questions/27672585/efficient-version-of-inits) seems to address an efficient version of `inits`. — RoadRunner, Jan 16 '18 at 16:32
@WillNess, you successfully confused me for a bit, but yes, I'm pretty sure you're missing something. You'll end up with an element that looks something like `(((a:) . (b:)) . (c:)) . (d:) $ []`. This needs to be reassociated before revealing its head. So if you do something like `map headMay (inits xs)`, I expect you'll run into trouble. — dfeuer, Jan 16 '18 at 22:15
On the other hand, I forgot the simple way to be optimal (big-O, but with mediocre constant factors): use `take`. But that may not be "recursive" enough for this question. — dfeuer, Jan 16 '18 at 23:10
@dfeuer the re-association is *O(i)* as well, as per your requirement (`i` the index into the original list). indeed, running `head $ (map ($[]) . scanl (\a x-> a . (x:)) id) [1..] !! 300000` and again with `3000000`, [the run times ratio](https://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth) is 10.0. (cf. [this](https://stackoverflow.com/questions/13879260/why-are-difference-lists-more-efficient-than-regular-concatenation/13879693#13879693)) — Will Ness, Jan 17 '18 at 08:51
@WillNess, my requirement probably wasn't stringent enough to get the full point. Consider `rnf (map headMay (inits xs))`. I believe your version is quadratic for that, while the one in `base` and the `take` based one are linear. Compare reflection without remorse. — dfeuer, Jan 17 '18 at 09:17
@dfeuer that of course will be quadratic, yes. `map headMay $ zipWith (\_ i -> take i xs) xs [0..]` won't, indeed. Nice. — Will Ness, Jan 17 '18 at 09:32
to sum it up, the take-based version does the absolute minimum upfront, so has to count when accessing each list in the result, to compensate. the DL version does the "counting", in effect building the resulting lists in full, upfront, so that subsequent traversing of each list is the cheapest. — Will Ness, Jan 17 '18 at 11:18

score 4 · Answer 1 · answered Jan 16 '18 at 14:24

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.

score 3 · Accepted Answer · answered Jan 16 '18 at 14:21

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

this definition looks exactly equivalent to the ["horrifyingly inefficient"](https://stackoverflow.com/a/27674051/849891) one [from ghc 7.8.3](http://hackage.haskell.org/package/base-4.7.0.1/docs/src/Data-List.html#inits). quick testing `head $ inits' [1..] !! n` at the ghci prompt, interpreted, indeed reveals ~n^2 empirical orders of growth. — Will Ness, Jan 17 '18 at 08:39

RoadRunner · Answer 3 · 2018-01-17T11:18:04.450

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?

Defining inits function recursively

3 Answers3