On 6 Feb 2008, at 16:32, Peter Padawitz wrote:
Can anybody give me a simple explanation why the second definition
of a palindrome checker does not terminate, although the first one
does?
pal :: Eq a => [a] -> Bool
pal s = b where (b,r) = eqrev s r []
eqrev :: Eq a => [a] -> [a] -> [a] -> (Bool,[a])
eqrev (x:s1) ~(y:s2) acc = (x==y&&b,r) where (b,r) = eqrev s1 s2
(x:acc)
eqrev _ _ acc = (True,acc)
I. eqrev "" (_|_) acc = (True, acc)
II.a. eqrev "1" (_|_) "" = ('1' == (_|_) && b, r) where (b,r) = eqrev
"" (_|_) "1"
By (I), (b,r) = (True, "1"), so eqrev "1" (_|_) "" = ((_|_),"1")
II.b. eqrev "1" "1" "" = ('1' == '1' && b, r) where (b,r) = eqrev ""
"" "1"
(b,r) = (True,"1"), so eqrev "1" "1" "" = (True,"1")
Therefore, the least fixed point of \r -> eqrev "1" r "" is "1" and
the answer is True.
pal :: Eq a => [a] -> Bool
pal s = b where (b,r) = eqrev' s r
eqrev' :: Eq a => [a] -> [a] -> (Bool,[a])
eqrev' (x:s1) ~(y:s2) = (x==y&&b,r++[y]) where (b,r) = eqrev' s1 s2
eqrev' _ _ = (True,[])
I. eqrev' "" (_|_) = (True,[])
II.a. eqrev' "1" (_|_) = ('1' == (_|_) && b, r ++ [(_|_)]) where (b,r)
= eqrev' "" (_|_)
By (I), (b,r) = (True,[]), so eqrev' "1" (_|_) = ((_|_),[(_|_)])
II.b. eqrev' "1" [(_|_)] = ('1' == (_|_) && b, r ++ [(_|_)]) where
(b,r) = eqrev' "" []
(b,r) = (True,[]), so eqrev' "1" [(_|_)] = ((_|_),[(_|_)])
Therefore, the least fixed point of \r -> eqrev' "1" r is [(_|_)] and
the answer is (_|_). No wonder it hangs.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
