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

[Dean Herington]

At 5:32 PM +0000 3/17/12, 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 = []
>
>When I load this into GHCi and type tryThis, it prints a list of all 
>of the numbers I would expect, then hangs.  Does the self-generating 
>technique not work with finite lists?  Shouldn't tryThis' just 
>generate a final empty list that would terminate this?  How can this 
>be written to successfully terminate?

As you observed, tryThis' doesn't know to terminate because its xs 
never becomes [], even at (what you know is) the end.  You need to 
program a termination check that doesn't need to look into the 
future.  Here's one way (probably not the best):

tryThis2 :: [Int]
tryThis2 = 3 : [ x | x <- tryThis' 1 0 tryThis2]
   where
     tryThis' :: Int -> Int -> [Int] -> [Int]
     tryThis' n m _ | m == n = []
     tryThis' n m (x : xs) = let gen = result' x in gen ++ tryThis' (n 
+ length gen) (m + 1) xs
       where
         result' :: Int -> [Int]
         result' 3 = [2, 2, 2]
         result' 2 = [1, 1]
         result' 1 = [0]
         result' 0 = []