[Haskell-cafe] Newbie question related to list evaluation

[Jonathan Cast]

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  
> 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 +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.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe