get haskell segmented list in the specified pattern

total_idiot 0
Viewed 65

I am supposed to get segment of Haskell list.

Input: f3 [0,1,2,3]

Expected output: [[],[0],[0,1],[1],[0,1,2],[1,2],[2],[0,1,2,3],[1,2,3],[2,3],[3]]

I solved it like this but I can't get it into the specified pattern.

inits_ :: [a] -> [[a]]
inits_ [] = []
inits_ xs = xs : inits_ (init xs)

segments :: [a] -> [[a]]
segments [] = []
segments (x:xs) = inits_ (x:xs) ++ segments xs

Evaluating the expression:

segments [0,1,2,3]

Yields:

[[0,1,2,3],[0,1,2],[0,1],[0],[1,2,3],[1,2],[1],[2,3],[2],[3]]
haskell functional-programming
1 Answers

You've solved it by concatenating the inits of the tails. In order words, you've taken the tails of [0,1,2,3]:

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

and expanded them to their inits:

[0,1,2,3]  -->  [0,1,2,3],[0,1,2],[0,1],[0]
[1,2,3]    -->  [1,2,3],[1,2],[1]
[2,3]      -->  [2,3],[2]
[3]        -->  [3]

and then combined those in order to get your final answer:

> segments [0,1,2,3]
[[0,1,2,3],[0,1,2],[0,1],[0],[1,2,3],[1,2],[1],[2,3],[2],[3]]

What if you instead started with the inits (in reverse order):

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

and expanded them to their tails:

[0]        -->  [0]
[0,1]      -->  [0,1],[1]
[0,1,2]    -->  [0,1,2],[1,2],[2]
[0,1,2,3]  -->  [0,1,2,3],[1,2,3],[2,3],[3]

and combined those in order:

> segments [0,1,2,3]
[[0],[0,1],[1],[0,1,2],[1,2],[2],[0,1,2,3],[1,2,3],[2,3],[3]]

That's missing the initial empty segment (as was your answer), but it's otherwise the order you want.

As a hint, this slightly modified version of segments' will combine the tails in the right order and will even add the empty segment in the base case:

segments' :: [a] -> [[a]]
segments' [] = [[]]
segments' xs = segments' (init xs) ++ tails_ xs

You just need to define tails_ so it works like so:

λ> tails_ [0,1,2,3]
[[0,1,2,3],[1,2,3],[2,3],[3]]
K. A. Buhr0
Related