[Haskell-cafe] Optimization with Strings ?

[Holger Siegel]

Am Donnerstag, den 03.12.2009, 16:23 +0100 schrieb Emmanuel CHANTREAU:
> 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.

This does not always hold, because the equivalence known from
mathematics differs from Haskell's strict equality when it comes to
infinite or undefined values. Consider

  let x = repeat () in x == x

and

  let x = error "oops" in x == x

In both cases your optimized program would return True, although the
value is undefined (bottom).