[Haskell-cafe] Please help with double recursion

Daniel Fischer daniel.is.fischer at googlemail.com
Sat May 28 14:31:50 CEST 2011

On Saturday 28 May 2011 14:19:18, Dmitri O.Kondratiev wrote:
> Thanks for simple and beautiful code to get all pairs.
> Yet, I need to get to the next step - from all pairs to build all
> chains, to get as a result a list of lists:
> [[abcde, acde, ade, ae,]
> [bcde, bde, be,]
> [cde, cd, ce,]
> de]]
> This is where I got stuck.

-- instead of pairing with a single later element, we cons with the
-- tail beginning at that later element
chainsFromFirst :: [a] -> [[a]]
chainsFromFirst (x:xs) = [x:ys | ys <- init (tails xs)]
chainsFromFirst [] = []

-- we need init (tails xs) becuase we don't want the final empty tail

allChains :: [a] -> [[a]]
allChains xs = tails xs >>= chainsFromFirst

-- we could use init (tails xs) here too, but that is not necessary

More information about the Haskell-Cafe mailing list