On Sat, May 28, 2011 at 3:57 PM, Daniel Fischer < daniel.is.fischer@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.