[Haskell-cafe] Optimization with Strings ?
Neil Brown
nccb2 at kent.ac.uk
Thu Dec 3 10:31:56 EST 2009
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.
More information about the Haskell-Cafe
mailing list