Haskell sublist with foldr

1
votes

I'm trying to make a function in haskell but my goal is doing it by using foldr over list, this is an example:

sublistas [5,1,2] 
 [[],[2],[1],[1,2],[5],[5,2],[5,1],[5,1,2]]

efficiency is not an issue. What I try so far gives to me the error:

cannot construct the infinite type .....

sublistas = foldr (\x rs -> [x] ++ map (x:) rs) [[]]

I tried a long time, maybe someone could give me some ideas here?

1
haskellcombinationsfold
Did you intentionally leave out [5,2] because you want only contiguous sublists? - Alec
No no @Alec, I forget it, thank you, I updated the q - Damián Rafael Lattenero
An equivalent without foldr is sublistas = filterM (const [True, False]) - 4castle
sublists = foldr (\x l -> l ++ map (x:) l) [[]] - Alec
For funzies, the contiguous sublists would be sublistas xs = tails xs >>= tail . inits - 4castle

1 Answers

2
votes

You can use:

foldr (\x rs -> rs ++ map (x:) rs) [[]]

For example:

Prelude> foldr (\x rs -> rs ++ map (x:) rs) [[]] [5,1,2]
[[],[2],[1],[1,2],[5],[5,2],[5,1],[5,1,2]]

The proposed foldr thus works as follows: we start with a [[]]. Now for an element x, we generate the concatenation, of all lists already generated (in the first step [], and these lists prepended with the element, so [2]).

So after a first step, we obtain [[],[2]]. Next we fold again and now we generate [[],[2],[1],[1,2]]. Finally we also work with 5, resulting in [[],[2],[1],[1,2],[5],[5,2],[5,1],[5,1,2]].

The above explanation has to be seen in a lazy manner: rs is not necessary calculated (first), unless that is necessary.

Your lambda expression \x rs -> [x] ++ map (x:) rs is incorrect for two reasons:

  • [x] is a list containing a item of the list you provide, not a list of lists of items you provide, so a type error; and
  • you should not add an [x] to the result anyway: you pass all elements that are already generated, together with all the elements you prepend with x.