List breaking implemented recursively

Question

I start Haskell and I experimented with recursive functions.

I am working on a function:

 separate :: [a] -> [[[a]]]

which takes a list and displays all sections of this list.

For example, 123 becomes:

1|2|3
12|3
1|23
13|2
132

I managed to implement a recursive function that creates a variant 1|2|3:

separate' :: [a] -> [[a]]
separate' (r:rs) = [r]:separate' xs

>separate [1,2,3]
[[1],[2],[3]]

I am stuck trying to create other recursion options.

Answer 1

You can think of this function as choosing for each place between two elements of the list whether to include separation there. Therefore, for starters, there should be 2 ^n-1 sections for a list of n-elements: you can use this as a quick check for a possible solution.

(, , ), .

:

separate :: [a] -> [[[a]]]
separate [] = [[]]

: , . .

, , , :

separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
                  in undefined -- TODO

, . , , . , :

separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
                      split = undefined -- TODO
                      noSplit = undefined -- TODO
                  in split ++ noSplit

, x? recur, [x] :

separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
                      split = do
                        partition <- recur
                        return $ [x] : partition
                      noSplit = undefined -- TODO
                  in split ++ noSplit

? ! recur x :

separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
                      split = do
                        partition <- recur
                        return $ [x] : partition
                      noSplit = do
                        (y:ys) <- recur
                        return $ (x:y):ys
                  in split ++ noSplit

:

*Temp> separate "123"
[["1","2","3"],["1","23"],["12","3"],["123"]]

Answer 2

:

import Control.Applicative ((<$>))

separate :: Foldable t => t a -> [[[a]]]
separate = foldr (\i -> concatMap (inc i)) [[]]
    where
    inc i []     = [[[i]]]
    inc i (x:xs) = ((i:x):xs):((x:) <$> inc i xs)

\> separate [1, 2]
[[[1,2]],[[2],[1]]]

\> separate [1, 2, 3]
[[[1,2,3]],[[2,3],[1]],[[1,3],[2]],[[3],[1,2]],[[3],[2],[1]]]