Finite self-referential list hangs.
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? Thank you for any help. -TC
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 = []
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
participants (3)
-
Brent Yorgey -
Dean Herington -
tcollin371