[Haskell-cafe] Newbie question related to list evaluation
jonathanccast at fastmail.fm
Sun Jan 6 13:40:12 EST 2008
On 6 Jan 2008, at 10:34 AM, Sai Hemanth K wrote:
> 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
> 4.matchReverse str1 str1 0 --should return
> 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
> I drink I am thunk.
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe