[Haskell-cafe] Optimization with Strings ?

[Daniel Fischer]

Am Donnerstag 03 Dezember 2009 16:31:56 schrieb Neil Brown:
> Emmanuel CHANTREAU wrote:
> > Le Thu, 3 Dec 2009 13:20:31 +0100,
> >
> > David Virebayre <dav.vire+haskell at gmail.com> a écrit :
> >> It doesn't work this way : Strings are just lists of Chars. Comparison
> >> is made recursively, Char by Char. You can have a look at the source
> >> to make sure :
> >>
> >> instance (Eq a) => Eq [a] where
> >>     []     == []     = True
> >>     (x:xs) == (y:ys) = x == y && xs == ys
> >>     _xs    == _ys    = False
> >
> > Hello
> >
> > Thank you David and Bulat for your answers.
> >
> > I don't see the proof you see. Because GHC could store two sames
> > objects juste once and by the definition of == on lists it could deduce
> > that "forall x; List x => x==x". GHC have all informations to do this
> > optimization job, because haskell functions definitions are mathematics
> > definitions.
>
> Besides any other reasons, Haskell has the error function, and infinite
> lists.  Consider:
>
> p :: String
> p = error "Haha!"
>
> q :: String
> q = repeat 'a'
>
> pEqualsP :: Bool
> pEqualsP = p == p
>
> qEqualsQ :: Bool
> qEqualsQ = q == q
>
> By your rule, pEqualsP and qEqualsQ should be True.  In fact, the
> correct answer is that pEqualsP should produce an error and qEqualsQ
> should never terminate.  Since Strings can contain such errors and
> infinite lists, you can't know for certain that an object equals itself
> without checking its entire length, which is what the original
> definition for equals did anyway.  There may be strict data structures
> for which your optimisation might be applicable, though.
>
> Neil.

However, GHC offers a *really unsafe* function that allows to quickly check whether two 
values refer to the same heap-object. But it won't help Emmanuel, because any indirection 
causes it to say no and "let x = expression in x == x" should never appear in code anyway.