[Haskell-cafe] Please help with double recursion

[wren ng thornton]

On 5/28/11 8:31 AM, Daniel Fischer wrote:
> On Saturday 28 May 2011 14:19:18, Dmitri O.Kondratiev wrote:
>>
>> 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.
>
> -- instead of pairing with a single later element, we cons with the
> -- tail beginning at that later element
> chainsFromFirst :: [a] ->  [[a]]
> chainsFromFirst (x:xs) = [x:ys | ys<- init (tails xs)]
> chainsFromFirst [] = []
>
> -- we need init (tails xs) becuase we don't want the final empty tail
>
>
> allChains :: [a] ->  [[a]]
> allChains xs = tails xs>>= chainsFromFirst
>
> -- we could use init (tails xs) here too, but that is not necessary

The variant I came up with was:

     allChains xs = do
         y:ys     <- tails xs
         zs@(_:_) <- tails ys
         return (y:zs)

Which is essentially the same. I only very rarely use list 
comprehensions, but if you prefer that syntax you can always do:

     allChains xs = [ (y:zs) | y:ys <- tails xs, zs@(_:_) <- tails ys ]

-- 
Live well,
~wren