lazy comparison for equality ?
Konst Sushenko
konsu@microsoft.com
Wed, 24 Apr 2002 13:19:04 -0700
In addition to what Hal said,
I think that even assuming that you want to write a function like that
that is only supposed to be applied to finite lists (like, say,
prelude's 'and' function, which does not terminate on an infinite list
of True values) you still cannot do it because haskell lists are not
like C lists.
There is no notion, to my understanding, of list circularity. There are
finite and infinite lists. Your example of a list that you call a
circular list is just a definition of a recursive function that produces
an infinite list.
So what you are almost asking is how to write a function that checks if
a list has repeated sub-sequences, which is not of course precisely the
same that you asked (because even a finite list can have repeated
sub-sequences), but close. And this is just one of many problems taken
care of by various string search algorithms.
konst
> -----Original Message-----
> From: Hal Daume III [mailto:hdaume@ISI.EDU]=20
> Sent: Wednesday, April 24, 2002 12:38 PM
> To: klusacek@atrey.karlin.mff.cuni.cz
> Cc: haskell-cafe@haskell.org
> Subject: Re: lazy comparison for equality ?
>=20
>=20
> I don't think you can write such a function. For instance,=20
> how would you
> know whether [1..] is circular or not? In order to know that it's not
> you'd need to evaluate it fully.
>=20
> --
> Hal Daume III
>=20
> "Computer science is no more about computers | hdaume@isi.edu
> than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
>=20
> On Wed, 24 Apr 2002 klusacek@atrey.karlin.mff.cuni.cz wrote:
>=20
> >=20
> > Hi -
> > I'm a Haskell beginner and I have a problem.=20
> >=20
> > Let's have a list which may be normal list
> > list1 =3D [1,2,3]
> > or a circular list
> > list2 =3D 1:2:list2
> >=20
> > Now I'd like to have a function which tells me whether the=20
> > given list is circular or not. This doesn't work:
> >=20
> > circ l =3D l l
> > circ2 l [] =3D False
> > circ2 l (_:as) | l=3D=3Das =3D True
> > | True =3D (circ2 l as)
> >=20
> >=20
> > It seems that comparison l=3D=3Das really compares element by=20
> element thus
> > falling into an infinite loop. I would need to compare=20
> pointers instead of
> > values.
> >=20
> > Does anybody know how this could be done ?
> >=20
> > Thanks.
> >=20
> >=20
> >=20
> >=20
> >=20
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >=20
>=20
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>=20