[Haskell-cafe] Please help with double recursion

[Daniel Fischer]

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