[Haskell-beginners] Finite self-referential list hangs.

[Brent Yorgey]

On Sat, Mar 17, 2012 at 05:32:24PM +0000, tcollin371 wrote:
> I am trying to generate a search tree for a logic puzzle using a list that generates itself by using earlier states to derive later states.  The search tree is finite, but when it reaches the end, it hangs and while the list doesn't grow, it doesn't finish.
> 
> I've boiled the problem down to a much simpler list as follows:
> 
> tryThis :: [Int]
> tryThis = 3 : [ x | x <- tryThis' tryThis]
>   where
>     tryThis' :: [Int] -> [Int]
>     tryThis' [] = []
>     tryThis' (x : xs) = result' x ++ tryThis' xs
>       where
>         result' :: Int -> [Int]
>         result' 3 = [2, 2, 2]
>         result' 2 = [1, 1]
>         result' 1 = [0]
>         result' 0 = []

By the way,

  [ x | x <- foo ] == foo

so we can simplify this to

  tryThis = 3 : tryThis' tryThis
    where
      ...

Also, tryThis' = concatMap result', so it can be further simplified to

  tryThis = 3 : concatMap result' tryThis
    where
      result' :: Int -> [Int]
      result' 3 = ...

Of course, this still does not terminate.  The problem, intuitively,
is that the concatMap "catches up with itself" and after the last 0 is
generated, it is waiting to find out what the next element will be, 
in order to generate the very element it is waiting for!  Here is one
way to solve it:

  tryThis2 :: [Int]
  tryThis2 = concat tryThis2'
    where
      tryThis2' = [3] : process tryThis2'
      process ([] : _)   = []
      process (xs : xss) = concatMap result' xs : process xss
      result' 3 = [2,2,2]
      result' 2 = [1,1]
      result' 1 = [0]
      result' 0 = []

The idea is that we delay doing the concat until the very end, so
during the actual generation we have a list of lists, where each inner
list contains all the numbers generated at some "stage".  For example
we have [[3], [2,2,2], ...]. That way we can tell when no new numbers
were generated by the previous stage and stop (that's the first case
of 'process').

-Brent