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 = []