Re: [Haskell-cafe] Optimization with Strings ?
On Thu, Dec 3, 2009 at 8:25 AM, John D. Earle johndea...@cox.net wrote: Haskell has a problem with its type system and is not rigorous. Haskell is not a suitable language for proof assistants and so I would advise you to stay clear of Haskell. Standard ML was engineered with the needs of proof assistants in mind and so you may want to look into Standard ML, but you should be very happy with Objective CAML. It has an excellent reputation. The Coq proof assistant which is another French product is based on Objective CAML. If I understand you correctly, SML was engineered with the needs of a proof assistant in mind, but OCaml is a very different language. And it seems you are pushing F#/OCaml not SML. Do F# and OCaml have full formal semantics for their type systems that have been verified? Or are they merely based on Hindley-Milner type systems? If it is the latter, then could you help me understand why Haskell is so much worse? If it's the former could you please point me to the appropriate research so I can educate myself? If the objection is primarily String performance based then I would recommend that you take a look at ByteString or uvector. Please help me understand the holes in Haskell's type system. Have you published some research on the flaws of Haskell's design? If Haskell is unsound I'd certainly like to know where and why so that I can improve my programs. Please help. Thanks, Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
Please help me understand the holes in Haskell's type system. Not really wanting to support the troll, but ... unsafePerformIO? Can't it be removed? -- Colin Adams Preston, Lancashire, ENGLAND ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
Or maybe it should be renamed proofObligationsOnUseNeedToBeSupliedBySuitablyQualifiedIndividualPerformIO which is what it really is - unsafe in the wrong hands Nei On 4 Dec 2009, at 08:57, Colin Adams wrote: Please help me understand the holes in Haskell's type system. Not really wanting to support the troll, but ... unsafePerformIO? Can't it be removed? -- Colin Adams Preston, Lancashire, ENGLAND ___ 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
Re: [Haskell-cafe] Optimization with Strings ?
But the type system doesn't insist on such a proof - so is it not a hole? 2009/12/4 Neil Davies semanticphilosop...@googlemail.com: Or maybe it should be renamed proofObligationsOnUseNeedToBeSupliedBySuitablyQualifiedIndividualPerformIO which is what it really is - unsafe in the wrong hands Nei On 4 Dec 2009, at 08:57, Colin Adams wrote: Please help me understand the holes in Haskell's type system. Not really wanting to support the troll, but ... unsafePerformIO? Can't it be removed? -- Colin Adams Preston, Lancashire, ENGLAND ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Colin Adams Preston, Lancashire, ENGLAND ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
Ah but the type system is the proof - it doesn't permit you to construct things that are 'unsafe' - the whole way the language (and its implementation) is constructed is to do that for you. The issue is that, very occasionally, you the programmer (usually for reasons of performance - runtime or code lines) want something slightly out of the ordinary. This is the escape mechanism. To quote the late, great DNA - it is all about rigidly defined areas of doubt and uncertainty - one of the arts of programming is to push all the nasty doubt and uncertainty into a small corner where you can beat it to death with a large dose of logic, proof and (occasional) handwaving... Now before you start talking about 'surely the type system should be complete' - I refer you to http://en.wikipedia.org/wiki/Gödel%27s_incompleteness_theorem Take comfort in that, I do, it means that us humans still have a role... Neil On 4 Dec 2009, at 09:16, Colin Adams wrote: But the type system doesn't insist on such a proof - so is it not a hole? 2009/12/4 Neil Davies semanticphilosop...@googlemail.com: Or maybe it should be renamed proofObligationsOnUseNeedToBeSupliedBySuitablyQualifiedIndividualPerformIO which is what it really is - unsafe in the wrong hands Nei On 4 Dec 2009, at 08:57, Colin Adams wrote: Please help me understand the holes in Haskell's type system. Not really wanting to support the troll, but ... unsafePerformIO? Can't it be removed? -- Colin Adams Preston, Lancashire, ENGLAND ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Colin Adams Preston, Lancashire, ENGLAND ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
On Thu, 2009-12-03 at 13:03 +0100, Emmanuel CHANTREAU wrote: Hello In my futur program, it use a lot of binary trees with strings (words) as leaf. There is just arround 1000 words and they will appear a lot of times. The program will possibly consume a lot of process and memory (it is a mathematics proover). I began this program in C++ but haskell has a prety good speed and memory footprint and is easier. But I don't know if it worth to do this optimization: having a dictionary to translate string words in Int. The answer depends on the automatic optimizations in GHC, because GHC could compare quickely two strings if it is the same object, so it depends if program generated by GHC have a dictionary (tree) of strings internaly. Someone knows this ? There's nothing automatic about it. It depends on the implementation of the type of string you are using. For the String type there is no equality short-cut, for ByteString there is. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Optimization with Strings ?
Hello In my futur program, it use a lot of binary trees with strings (words) as leaf. There is just arround 1000 words and they will appear a lot of times. The program will possibly consume a lot of process and memory (it is a mathematics proover). I began this program in C++ but haskell has a prety good speed and memory footprint and is easier. But I don't know if it worth to do this optimization: having a dictionary to translate string words in Int. The answer depends on the automatic optimizations in GHC, because GHC could compare quickely two strings if it is the same object, so it depends if program generated by GHC have a dictionary (tree) of strings internaly. Someone knows this ? (Sorry for my english, I'm french) thank you -- Emmanuel Chantréau ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
On Thu, Dec 3, 2009 at 1:03 PM, Emmanuel CHANTREAU echant+hask...@maretmanu.org wrote: In my futur program, it use a lot of binary trees with strings (words) as leaf. There is just arround 1000 words and they will appear a lot of times. The program will possibly consume a lot of process and memory (it is a mathematics proover). I began this program in C++ but haskell has a prety good speed and memory footprint and is easier. But I don't know if it worth to do this optimization: having a dictionary to translate string words in Int. The answer depends on the automatic optimizations in GHC, because GHC could compare quickely two strings if it is the same object, so it depends if program generated by GHC have a dictionary (tree) of strings internaly. Someone knows this ? 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 So you will have to code your own optimisation. David. P.S. In French if you didn't understand: Ca ne marche pas comme ça. Les chaines de caractères ne sont que des listes de caractères. La comparaison sur les listes est faite récursivement, caractère par caractère, il suffit pour s'en assurer de regarder au source : Donc il vaut mieux que tu implémente ton propre dictionnaire. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
Hello Emmanuel, Thursday, December 3, 2009, 3:03:02 PM, you wrote: memory footprint and is easier. But I don't know if it worth to do this optimization: having a dictionary to translate string words in Int. GHC compiler already has this optimization. unfortunately it's not in the code it generates but in compiler itself (GHC is written in Haskell and compiled by itself). so it is definitely worth an implementation if you handle lots of strings as compiler does -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
Le Thu, 3 Dec 2009 13:20:31 +0100, David Virebayre dav.vire+hask...@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. Bulat says that this optimization is not done, so I will do it by my hands (ho my poor lazy hands). -- Emmanuel Chantréau ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
Emmanuel CHANTREAU wrote: Le Thu, 3 Dec 2009 13:20:31 +0100, David Virebayre dav.vire+hask...@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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
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+hask...@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). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Optimization with Strings ?
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, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Optimization with Strings ?
Dear Emmanuel Chantréau, You may want to look into Objective CAML http://caml.inria.fr/ which is a French product as you can see from the Internet address. It is likely better suited to the task than Haskell and has a reputation for speed. For those who prefer object oriented programming it has facilities for that which may ease your transition from C++. The Microsoft F# language is based on Objective CAML. Haskell has a problem with its type system and is not rigorous. Haskell is not a suitable language for proof assistants and so I would advise you to stay clear of Haskell. Standard ML was engineered with the needs of proof assistants in mind and so you may want to look into Standard ML, but you should be very happy with Objective CAML. It has an excellent reputation. The Coq proof assistant which is another French product is based on Objective CAML. If you do decide that Haskell is the way, it will help ease your transition to Haskell. There is nothing that says you can't keep your fingers in several pies at once.___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
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+hask...@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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
JohnDEarle: You may want to look into Objective CAML http://caml.inria.fr/ which is a French product as you can see from the Internet address. It is likely better suited to the task than Haskell and has a reputation for speed. For those who prefer object oriented programming it has facilities for that which may ease your transition from C++. The Microsoft F# language is based on Objective CAML. Haskell has a problem with its type system and is not rigorous. Haskell is not a suitable language for proof assistants and so I would advise you to stay clear of Haskell. Standard ML was engineered with the needs of proof assistants in mind and so you may want to look into Standard ML, but you should be very happy with Objective CAML. It has an excellent reputation. The Coq proof assistant which is another French product is based on Objective CAML. Ok, that is serious trolling. There are several proof assistants written in Haskell: http://hackage.haskell.org/package/Agda http://hackage.haskell.org/package/ivor http://www.e-pig.org/ http://wiki.di.uminho.pt/wiki/bin/view/PURe/Camila http://www.cwi.nl/~jve/demo/ http://www.haskell.org/dumatel/ http://www.cs.chalmers.se/~koen/folkung/ http://taz.cs.wcupa.edu/~dmead/code/prover/ http://www.math.chalmers.se/~koen/paradox/ http://proofgeneral.inf.ed.ac.uk/Kit http://www.haskell.org/yarrow/ and the guarantees of purity the type system provides are extremely useful for verification purposes. Please, before posting like this to the Haskell community, inform yourself more of what the Haskell community has produced. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
Emmanuel CHANTREAU on 2009-12-03 13:03:02 +0100: In my futur program, it use a lot of binary trees with strings (words) as leaf. There is just arround 1000 words and they will appear a lot of times. The program will possibly consume a lot of process and memory (it is a mathematics proover). I began this program in C++ but haskell has a prety good speed and memory footprint and is easier. But I don't know if it worth to do this optimization: having a dictionary to translate string words in Int. The answer depends on the automatic optimizations in GHC, because GHC could compare quickely two strings if it is the same object, so it depends if program generated by GHC have a dictionary (tree) of strings internaly. Someone knows this ? 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
On Thu, Dec 3, 2009 at 12:32 PM, Alec Berryman a...@thened.net wrote: Emmanuel CHANTREAU on 2009-12-03 13:03:02 +0100: In my futur program, it use a lot of binary trees with strings (words) as leaf. There is just arround 1000 words and they will appear a lot of times. The program will possibly consume a lot of process and memory (it is a mathematics proover). I began this program in C++ but haskell has a prety good speed and memory footprint and is easier. But I don't know if it worth to do this optimization: having a dictionary to translate string words in Int. The answer depends on the automatic optimizations in GHC, because GHC could compare quickely two strings if it is the same object, so it depends if program generated by GHC have a dictionary (tree) of strings internaly. Someone knows this ? 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. -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
Thank you Sir for giving me a good laugh! On Thu, Dec 3, 2009 at 5:25 PM, John D. Earle johndea...@cox.net wrote: Dear Emmanuel Chantréau, You may want to look into Objective CAML http://caml.inria.fr/ which is a French product as you can see from the Internet address. It is likely better suited to the task than Haskell and has a reputation for speed. For those who prefer object oriented programming it has facilities for that which may ease your transition from C++. The Microsoft F# language is based on Objective CAML. Haskell has a problem with its type system and is not rigorous. Haskell is not a suitable language for proof assistants and so I would advise you to stay clear of Haskell. Standard ML was engineered with the needs of proof assistants in mind and so you may want to look into Standard ML, but you should be very happy with Objective CAML. It has an excellent reputation. The Coq proof assistant which is another French product is based on Objective CAML. If you do decide that Haskell is the way, it will help ease your transition to Haskell. There is nothing that says you can't keep your fingers in several pies at once. ___ 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
Fwd: [Haskell-cafe] Optimization with Strings ?
Use makeStableName from System.Mem.StableName StableName`s are just for checking pointer equality. Instead of checking for equality of the strings, check for pointer equality of their stableNames a dirty way: pointerEq x y= unsafePerformIO $ do px - makeStableName x py - makeStableName y return x == y pEq x y | pointerEq x y == True = True | otherwise = x == y 2009/12/3 David Virebayre dav.vire+hask...@gmail.comdav.vire%2bhask...@gmail.com On Thu, Dec 3, 2009 at 1:03 PM, Emmanuel CHANTREAU echant+hask...@maretmanu.org echant%2bhask...@maretmanu.org wrote: In my futur program, it use a lot of binary trees with strings (words) as leaf. There is just arround 1000 words and they will appear a lot of times. The program will possibly consume a lot of process and memory (it is a mathematics proover). I began this program in C++ but haskell has a prety good speed and memory footprint and is easier. But I don't know if it worth to do this optimization: having a dictionary to translate string words in Int. The answer depends on the automatic optimizations in GHC, because GHC could compare quickely two strings if it is the same object, so it depends if program generated by GHC have a dictionary (tree) of strings internaly. Someone knows this ? 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 So you will have to code your own optimisation. David. P.S. In French if you didn't understand: Ca ne marche pas comme ça. Les chaines de caractères ne sont que des listes de caractères. La comparaison sur les listes est faite récursivement, caractère par caractère, il suffit pour s'en assurer de regarder au source : Donc il vaut mieux que tu implémente ton propre dictionnaire. ___ 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
Re: [Haskell-cafe] Optimization with Strings ?
You might want to check out the stringtable-atom and bytestring-trie packages; these are the packages to which I turn when I want to see if I can speed up my code by using a different data structure to map String's to values. Cheers, Greg On Dec 3, 2009, at 4:03 AM, Emmanuel CHANTREAU wrote: Hello In my futur program, it use a lot of binary trees with strings (words) as leaf. There is just arround 1000 words and they will appear a lot of times. The program will possibly consume a lot of process and memory (it is a mathematics proover). I began this program in C++ but haskell has a prety good speed and memory footprint and is easier. But I don't know if it worth to do this optimization: having a dictionary to translate string words in Int. The answer depends on the automatic optimizations in GHC, because GHC could compare quickely two strings if it is the same object, so it depends if program generated by GHC have a dictionary (tree) of strings internaly. Someone knows this ? (Sorry for my english, I'm french) thank you -- Emmanuel Chantréau ___ 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
Re: [Haskell-cafe] Optimization with Strings ?
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. 2009/12/3 Neil Brown nc...@kent.ac.uk Emmanuel CHANTREAU wrote: Le Thu, 3 Dec 2009 13:20:31 +0100, David Virebayre dav.vire+hask...@gmail.comdav.vire%2bhask...@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. ___ 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
Re: [Haskell-cafe] Optimization with Strings ?
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimization with Strings ?
On Thu, Dec 3, 2009 at 12:21 PM, Alberto G. Corona agocor...@gmail.com 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 nc...@kent.ac.uk Emmanuel CHANTREAU wrote: Le Thu, 3 Dec 2009 13:20:31 +0100, David Virebayre dav.vire+hask...@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. ___ 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
