Le Thu, 3 Dec 2009 13:20:31 +0100, David Virebayre 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. Bulat says that this optimization is not done, so I will do it by my hands (ho my poor lazy hands). -- Emmanuel Chantréau

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 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.

On Thu, Dec 3, 2009 at 12:21 PM, Alberto G. Corona wrote:

" In fact, the correct answer is that pEqualsP should produce an error and qEqualsQ should never terminate"

¿¿??? should? or you want to say "actually do that so the optimization does is not done"? The correct amswer is not the sould you mention, but True (IMHO). So the optimization can be done anyway.

No, the correct answer is actually _|_. Returning True would violate referential transparency: p = [1..] Now suppose p == p returned True. Then we can substitute any name for its value, by ref trans. So p == [1..] should also return True. This is reasonable. However, it is possible to prove (outside Haskell, but still rigoroously in terms of its semantics) that [1..] = fix (\xs -> 1 : map (+1) xs). So p == fix (1 : map (+1) xs) should also return True. This is getting unreasonable. Such an expectation would seem to require (==) to do a comprehensive proof search. Luke

2009/12/3 Neil Brown

...

Emmanuel CHANTREAU wrote:

...

Le Thu, 3 Dec 2009 13:20:31 +0100, David Virebayre 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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Hello Emmanuel, Thursday, December 3, 2009, 6:23:56 PM, you wrote:

that "forall x; List x => x==x". GHC have all informations to do this optimization job, because haskell functions definitions are mathematics definitions.

GHC doesn't make ALL possible optimizations, isn't it obvious? ;) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

David Menendez wrote:

Alec Berryman wrote:

...

I don't know of a library to intern strings, but it's not too hard to implement. I couldn't find the code I wrote to do this, but I looked around a bit and this is about what I remember doing:

http://www.haskell.org/pipermail/haskell-cafe/2005-June/010335.html

For the application I was using, interning strings did provide a significant reduction in memory, but for whatever reason didn't help with speed.

I'd use a trie. Edison provides Data.Edison.Assoc.TernaryTrie, and there are a few other trie packages at hackage.

One of those: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bytestring-trie also uses ByteStrings instead of Strings. This will further reduce your memory footprint and will improve performance (because of cache consistency, less pointer chasing, and using C's fast string comparison function). I've been meaning to write a ByteString interning library on top of it, but haven't found the time just yet. -- Live well, ~wren