For some reason, my previous message got truncated, so I repeat it in hope
that it will come complete this time:
---------- Forwarded message ----------
From: Dmitri O.Kondratiev <doko...@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)])
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
