[Haskell-cafe] Please help with double recursion

[Dmitri O.Kondratiev]

On Sat, May 28, 2011 at 3:57 PM, Daniel Fischer <
daniel.is.fischer at googlemail.com> wrote:

> On Saturday 28 May 2011 13:47:10, Dmitri O.Kondratiev wrote:
> > Hello,
> > I am trying to solve a simple task, but got stuck with double recursion
> > - for some reason not all list  elements get processed.
> > Please advice on a simple solution, using plane old recursion :)
> > *** Task:
> > From a sequence of chars build all possible chains where each chain
> > consists of chars that can be accessed from one to another.
> > For example, given the sequence:
> > "abcde"
> > In table below chars in a left column can access a list of chars in the
> > right column:
> > a | b c d
> > e
> >
> > b | c d
> > e
> >
> > c | d
> > e
> >
> > d |
> > e
> >
> >
> > Then chains for this example will be:
> > abcde, acde, ade, ae,
> > bcde, bde, be,
> > cde, cd, ce,
> > de
>
> I think
>
> import Data.List
>
> -- pair the first element with all later elements
> pairsFrom :: [a] -> [(a,a)]
> pairsFrom (x:xs) = [(x,y) | y <- xs]
> pairsFrom [] = []
>
> -- pair each element with all later ones
> allPairs :: [a] -> [(a,a)]
> allPairs xs = tails xs >>= pairsFrom
>
> -- alternative implementation with exlicit recursion:
>
> allPairs (x:xs) = pairsFrom (x:xs) ++ allPairs xs
> allPairs [] = []
>
>
> Prelude Data.List> allPairs "abcde"
> [('a','b'),('a','c'),('a','d'),('a','e'),('b','c'),('b','d'),('b','e'),
> ('c','d'),('c','e'),('d','e')]
>
> does what you want
>

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110528/040af46b/attachment.htm>