[Haskell-cafe] Please help with double recursion

[Richard O'Keefe]

On 28/05/2011, at 11:47 PM, 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

You have a set S of characters and a binary relation R ⊆ S × S
and a chain is a sequence [x0,x1,...] such that
  x[0] ∈ S
and for all i > 0,
  x[i-1] R x[i]

Can a chain be empty?

What constraints on R do you have that lead you to think that
each chain is finite, or are you expecting infinite chains as well?
(S = {a}, R = {(a,a)} admits chains of any length, including ones
that do not terminate.)