# [Haskell-cafe] Newbie question related to list evaluation

Jonathan Cast jonathanccast at fastmail.fm
Sun Jan 6 13:40:12 EST 2008

```On 6 Jan 2008, at 10:34 AM, Sai Hemanth K wrote:

> Hi,
>
> 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
>
> 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 +1)
>                                                   in if matched
> then ((x==y),pos)
>                                                      else (False,pos)

let is always recursive in Haskell, so this is a recursive definition
of pos.  To break the recursion, use

matchReverse (x:xs) (y:ys) pos = let (matched, pos') = matchReverse
xs ys (pos + 1)
in if matched then ((x==y), pos')
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 loop?
>
> Many thanks
> Kapilash
>
>
> --
> I drink I am thunk.
> _______________________________________________