[Haskell-cafe] Newbie question related to list evaluation
Sai Hemanth K
saihemanth at gmail.com
Sun Jan 6 13:45:57 EST 2008
AAh! Thanks a ton!
Hemanth K
On Jan 7, 2008 12:10 AM, Rodrigo Queiro <overdrigzed at gmail.com> wrote:
> 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
> >
> >
>
--
I drink I am thunk.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080107/b4345758/attachment.htm
More information about the Haskell-Cafe
mailing list