---------- Forwarded message ----------
From: Dmitri O.Kondratiev <dokondr@gmail.com>
Date: Sat, May 28, 2011 at 3:47 PM
Subject: Please help with double recursion
To: haskell-cafe@haskell.org

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

*** My incomplete result,
which I get running my program (see at the end of this message):
('a','b'),('b','c'),('c','d'),('d','e'), -- abcde,
('c','e'), -- ce,
('b','d'),('d','e'), -- bde,
('b','e') -- be,
('a','c'),('c','d'),('d','e'), -- acde
('c','e'),
('a','d'),('d','e'), -- ade,
('a','e') -- ae

Sequence 'abcde' contains 'bcde', 'cde', 'cd', 'de'. How to add all these sub-sequences as a separate sequences in my output?
And I have 'ce' sequence duplicated, which I don't need.
Also, how to output chains as a list of lists? Such as:
[[abcde, acde, ade, ae,]
[bcde, bde, be,]
[cde, cd, ce,]
de]]

*** my code

test = chains testPairs 'a' []
testPairs = pairs testSeq
testSeq = "abcde"

-- From a list of '((from,to),1)' pairs build char chains
-- Char chain is a list of chars: [from1, to1 = from2, to2 = from3, to3 = from4, ...]
-- 'pairList' - a list of pairs

chains pairList from chainList = chainWrk (nextTo pairList from) from chainList
where
    chainWrk [] from chainList = chainList
    chainWrk (to:tos) from chainList =
      chainWrk tos from (chains pairList to (chainList ++ [(from,to)]))

-- Find direct neighbors for 'from'
nextTo pairList from =
toList (findPairs pairList from) []

-- From a list of '((from,to),1)' pairs build a list of 'to'-s
toList [] tos = tos
toList (((from,to),len):ps) tos = toList ps (tos ++ [to])

-- From 'pairList' find elements with 'from' equal to 'start'
-- 'pairList' is a list of '((from,to),1)' pairs
findPairs pairList search = filter (flt search) pairList
                          where
                            flt search ((from, to), len) = search == from

-- From a sequence of chars buid a list of '((from,to),1)' pairs
pairs [] = []
pairs (x:xs) = pairWrk x xs [] ++ pairs xs

pairWrk hd [] pairLst = pairLst
pairWrk hd (x:xs) pairLst = pairWrk hd xs (pairLst ++ [((hd,x),1)])