[Haskell-cafe] Newbie question related to list evaluation

[Rodrigo Queiro]

You have used the name 'pos' twice, for both the parameter and the
returned value of the recursive call. The reason this results in an
infinite loop is that in code like

let x = x + 1

Haskell treats both xs to be references to the same thing, so evaluates:
x
= x + 1
= (x + 1) + 1
= ((x + 1) + 1) + 1
...

which results in the infinite loop.

On 06/01/2008, Sai Hemanth K <saihemanth at gmail.com> 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)
>
>
>
> 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
>
>