[Haskell-cafe] Newbie question related to list evaluation

Sai Hemanth K saihemanth at gmail.com
Sun Jan 6 13:34:39 EST 2008


I am new to functional and lazy programming languages ( that's correct, my
life has been pretty pathetic so far) and am not able to understand GHC's
behaviour for a particular function. Can someone help me please?

I am trying to write a function which would compare two strings (from
reverse) and return the position of first mismatch. This is part of the
right-to-left scan of bayer-moore algorithm.. and it is essential for me to
do it from reverse.
Since my goal is to learn haskell, I am not using Data.ByteString.

My function is as follows:

matchReverse :: String -> String ->Int->(Bool,Int)
matchReverse [] [] pos = (True,pos)
matchReverse _ [] pos = (False,pos)
matchReverse [] _ pos = (False,pos)
matchReverse (x:xs) (y:ys) pos = let (matched,pos) = matchReverse xs ys (pos
                                                  in if matched then
                                                     else (False,pos)

The behaviour I expected in four scenarios is as below:
1.matchReverse "kapilash" "kapilash" 0     --should return (True,0)
2.matchReverse "kapilash" "kapilast" 0     --should return (False,8)
3.matchReverse str1 str2 0                      --should return (False,0)
4.matchReverse str1 str1 0                      --should return (True,0)

where str1 and str2 are defined as below:
 str1 =  replicate 1000 'a'
 str2 =  'b':(replicate 999 'a')

what confounds me is that it is able to identify the first element of the
tuple in ALL the cases.
Invoking fst on the each of the four calls instantly returns the expected
value.(even for the cases 3 and 4 where, there are thousand elements)
But it seems to go into an infinite loop while calculating the 'snd' of the
tuple. Even for strings containing just one element each.
can someone throw some light on this please? Why does it go into an infinite

Many thanks

I drink I am thunk.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080107/f9dc0a49/attachment.htm

More information about the Haskell-Cafe mailing list