Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. points-free problem (I. J. Kennedy) 2. Re: points-free problem (Daniel Fischer) 3. Re: points-free problem (Michael Mossey) 4. Re: points-free problem (Daniel Fischer) 5. Re: Re: Is Haskell for me? (Jon Harrop) 6. Re: Re: Is Haskell for me? (Ben Lippmeier) 7. Re: Re: Is Haskell for me? (Nicolas Pouillard) 8. Re: Re: Is Haskell for me? (Ben Lippmeier) 9. Re: Re: Is Haskell for me? (Nicolas Pouillard) ---------------------------------------------------------------------- Message: 1 Date: Fri, 20 Nov 2009 16:22:08 -0600 From: "I. J. Kennedy" <j...@realmode.com> Subject: [Haskell-beginners] points-free problem To: beginners@haskell.org Message-ID: <1008bfc90911201422t56f00c6ep429f929d155d7...@mail.gmail.com> Content-Type: text/plain; charset=UTF-8 I know I'm going to kick myself when the answer is revealed by one of you kind folks, but after staring at this a while I just can't figure out what's going on. The compiler (ghci) is trying so hard to tell me what's wrong, but I am failing to understand. I thought for the most part one could take a function definition like f x = (blah blah blah) x and turn it into points-free style by f = (blah blah blah) But from the dialog below, my assumption is incorrect. Help? I. J. Kennedy > sortBy (compare `on` fst) [(2,3),(0,1),(1,5)]  -- test a little sort > expression [(0,1),(1,5),(2,3)] > let sortpairs xss = sortBy (compare `on` fst) xss  -- make it into a > function > :t sortpairs sortpairs :: (Ord a) => [(a, b)] -> [(a, b)] > sortpairs [(2,3),(0,1),(1,5)] [(0,1),(1,5),(2,3)] > let sortpairs = sortBy (compare `on` fst)   -- points-free style > sortpairs [(2,3),(0,1),(1,5)] <interactive>:1:24:    No instance for (Num ())     arising from the literal `1' at <interactive>:1:24    Possible fix: add an instance declaration for (Num ())    In the expression: 1    In the expression: (1, 5)    In the first argument of `sortpairs', namely      `[(2, 3), (0, 1), (1, 5)]' > :t sortpairs sortpairs :: [((), b)] -> [((), b)] -- what?! ------------------------------ Message: 2 Date: Fri, 20 Nov 2009 23:41:53 +0100 From: Daniel Fischer <daniel.is.fisc...@web.de> Subject: Re: [Haskell-beginners] points-free problem To: beginners@haskell.org Message-ID: <200911202341.53566.daniel.is.fisc...@web.de> Content-Type: text/plain; charset="utf-8" Am Freitag 20 November 2009 23:22:08 schrieb I. J. Kennedy: > I know I'm going to kick myself when the answer is revealed by one of > you kind folks, but after staring at this a while I just can't figure > out what's going on. The compiler (ghci) is trying so hard to tell me > what's wrong, but I am failing to understand. I thought for the most > part one could take a function definition like > > f x = (blah blah blah) x > > and turn it into points-free style by > > f = (blah blah blah) > > But from the dialog below, my assumption is incorrect. > Help? > > I. J. Kennedy Monomorphism restriction. By that, if you bind f via f = (blah blah blah) and don't give a type signature, f gets a monomorphic type. Dreadful details in the report, section 4.5.(?) Put ":set -XNoMonomorphismRestriction" in your .ghci file. > > > sortBy (compare `on` fst) [(2,3),(0,1),(1,5)]  -- test a little sort > > expression > > [(0,1),(1,5),(2,3)] > > > let sortpairs xss = sortBy (compare `on` fst) xss  -- make it into a > > function > > > > :t sortpairs > > sortpairs :: (Ord a) => [(a, b)] -> [(a, b)] > > > sortpairs [(2,3),(0,1),(1,5)] > > [(0,1),(1,5),(2,3)] > > > let sortpairs = sortBy (compare `on` fst)   -- points-free style > > sortpairs [(2,3),(0,1),(1,5)] > > <interactive>:1:24: >    No instance for (Num ()) >     arising from the literal `1' at <interactive>:1:24 >    Possible fix: add an instance declaration for (Num ()) >    In the expression: 1 >    In the expression: (1, 5) >    In the first argument of `sortpairs', namely >      `[(2, 3), (0, 1), (1, 5)]' > > > :t sortpairs > > sortpairs :: [((), b)] -> [((), b)] -- what?! ------------------------------ Message: 3 Date: Fri, 20 Nov 2009 15:10:48 -0800 From: Michael Mossey <m...@alumni.caltech.edu> Subject: Re: [Haskell-beginners] points-free problem To: beginners <beginners@haskell.org> Message-ID: <4b0721f8.4090...@alumni.caltech.edu> Content-Type: text/plain; charset=UTF-8; format=flowed I've been on this list for something like 7 months and I think "monomorphism restriction" is the answer to about 70% of newbie/intermediate questions. I don't always understand their questions but one can pretty much guess the answer. Daniel Fischer wrote: > Monomorphism restriction. > By that, if you bind f via > > f = (blah blah blah) > > and don't give a type signature, f gets a monomorphic type. Dreadful details > in the > report, section 4.5.(?) > ------------------------------ Message: 4 Date: Sat, 21 Nov 2009 00:31:42 +0100 From: Daniel Fischer <daniel.is.fisc...@web.de> Subject: Re: [Haskell-beginners] points-free problem To: beginners@haskell.org Message-ID: <200911210031.42688.daniel.is.fisc...@web.de> Content-Type: text/plain; charset="utf-8" Am Samstag 21 November 2009 00:10:48 schrieb Michael Mossey: > I've been on this list for something like 7 months and I think > "monomorphism restriction" is the answer to about 70% of Certainly seems like that sometimes. But actually it's only 46.35% ;) Earnestly, it's apparently the thing by far the most people trip over. It would probably be a good thing to have it disabled by default in ghci as that's where it bites most often. On the other hand, it means lots of easy answers on the lists 8-) > newbie/intermediate questions. I don't always understand their questions > but one can pretty much guess the answer. > > Daniel Fischer wrote: > > Monomorphism restriction. > > By that, if you bind f via > > > > f = (blah blah blah) > > > > and don't give a type signature, f gets a monomorphic type. Dreadful > > details in the report, section 4.5.(?) > ------------------------------ Message: 5 Date: Sat, 21 Nov 2009 04:36:42 +0000 From: Jon Harrop <j...@ffconsultancy.com> Subject: Re: [Haskell-beginners] Re: Is Haskell for me? To: beginners@haskell.org Message-ID: <200911210436.42523....@ffconsultancy.com> Content-Type: text/plain; charset="iso-8859-1" On Friday 06 November 2009 17:19:50 Shawn Willden wrote: > On Friday 06 November 2009 09:52:48 am Cory Knapp wrote: > > Idiomatic Haskell won't be as fast as idiomatic C++, but it will blow > > Python away. > > Based on the little bit of stuff I've done, I think I'd characterize it > this way: C++ will be maybe twice as fast as Haskell. Maybe a little > more, maybe a little less, depending on a lot of details. For heavy > computation, Python will be a couple orders of magnitude slower than both. > > IOW, Haskell is slower than C++ but it's in the same ballpark. > > Would anyone disagree? The long-standing bug in GHC's garbage collector that makes writing a single boxed value into an array O(n) instead of O(1), because the GC dirties and retraverses the entire array, makes it impossible to write efficient Haskell code to solve many basic problems. Here is a simple dictionary benchmark where Python is 4x faster than Haskell because this bug means it is impossible to implement a competitively- performant dictionary: http://flyingfrogblog.blogspot.com/2009/04/f-vs-ocaml-vs-haskell-hash-table.html Haskell's celebrated idiomatic quicksort is actually 6,000x slower than a traditional implementation on this machine and consumes asymptotically more memory (making it useless for quite mundane problems): http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell Although people have created array-based quicksorts in Haskell the same perf bug in the GC means that a generic quicksort in Haskell would be asymptotically slower if it were given an array of boxed values. As an aside, purity complicates the creation of a parallel generic quicksort because it is necessary to mutate different parts of the same array in parallel. AFAICT, writing an efficient parallel generic quicksort is an unsolved problem in Haskell. Suffice to say, I cannot agree that Haskell is in the same ballpark as C++ in terms of performance. :-) -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e ------------------------------ Message: 6 Date: Sat, 21 Nov 2009 17:38:09 +1100 From: Ben Lippmeier <ben.lippme...@anu.edu.au> Subject: Re: [Haskell-beginners] Re: Is Haskell for me? To: Jon Harrop <j...@ffconsultancy.com> Cc: beginners@haskell.org Message-ID: <a52d4e32-b673-460c-a9dd-9f1b9e677...@anu.edu.au> Content-Type: text/plain; charset=us-ascii On 21/11/2009, at 15:36 , Jon Harrop wrote: > The long-standing bug in GHC's garbage collector that makes writing a single > boxed value into an array O(n) instead of O(1), because the GC dirties and > retraverses the entire array, makes it impossible to write efficient Haskell > code to solve many basic problems. Are you talking about http://hackage.haskell.org/trac/ghc/ticket/650 ? The way I read that ticket is that writing a boxed value to a mutable array is still O(1), but the garbage collector traverses the whole array during scanning. That could certainly slow down GC cycles, but how does it make array update O(n)? (update of the standard Haskell "pure" arrays being a separate issue, of course). Ben. ------------------------------ Message: 7 Date: Sat, 21 Nov 2009 11:13:22 +0100 From: Nicolas Pouillard <nicolas.pouill...@gmail.com> Subject: Re: [Haskell-beginners] Re: Is Haskell for me? To: Ben Lippmeier <ben.lippme...@anu.edu.au> Cc: beginners <beginners@haskell.org> Message-ID: <1258798176-sup-2...@peray> Content-Type: text/plain; charset=UTF-8 Excerpts from Ben Lippmeier's message of Sat Nov 21 07:38:09 +0100 2009: > > On 21/11/2009, at 15:36 , Jon Harrop wrote: > > > The long-standing bug in GHC's garbage collector that makes writing a > > single > > boxed value into an array O(n) instead of O(1), because the GC dirties and > > retraverses the entire array, makes it impossible to write efficient > > Haskell > > code to solve many basic problems. > > Are you talking about http://hackage.haskell.org/trac/ghc/ticket/650 ? > > The way I read that ticket is that writing a boxed value to a mutable array > is still O(1), but the garbage collector traverses the whole array during > scanning. That could certainly slow down GC cycles, but how does it make > array update O(n)? He means in worst case. Writing once, will cause O(n) during the next GC. Of course if you do a lot of updates between two GCs their is no extra penalty. So if you make 'k' updates between 2 GCs it costs you k*O(1)+O(n) which is still O(n) but practically nicer than k*O(n). -- Nicolas Pouillard http://nicolaspouillard.fr ------------------------------ Message: 8 Date: Sat, 21 Nov 2009 22:56:09 +1100 From: Ben Lippmeier <ben.lippme...@anu.edu.au> Subject: Re: [Haskell-beginners] Re: Is Haskell for me? To: Nicolas Pouillard <nicolas.pouill...@gmail.com> Cc: beginners <beginners@haskell.org> Message-ID: <5816568e-3afa-4e23-aae4-7acc60b43...@anu.edu.au> Content-Type: text/plain; charset=us-ascii On 21/11/2009, at 21:13 , Nicolas Pouillard wrote: > Excerpts from Ben Lippmeier's message of Sat Nov 21 07:38:09 +0100 2009: >> >> On 21/11/2009, at 15:36 , Jon Harrop wrote: >> >>> The long-standing bug in GHC's garbage collector that makes writing a >>> single >>> boxed value into an array O(n) instead of O(1), because the GC dirties and >>> retraverses the entire array, makes it impossible to write efficient >>> Haskell >>> code to solve many basic problems. >> >> Are you talking about http://hackage.haskell.org/trac/ghc/ticket/650 ? >> >> The way I read that ticket is that writing a boxed value to a mutable array >> is still O(1), but the garbage collector traverses the whole array during >> scanning. That could certainly slow down GC cycles, but how does it make >> array update O(n)? > > He means in worst case. Writing once, will cause O(n) during the next GC. Of > course if you do a lot of updates between two GCs their is no extra penalty. > So if you make 'k' updates between 2 GCs it costs you k*O(1)+O(n) which is > still O(n) but practically nicer than k*O(n). > Hmm. I'd be careful about conflating algorithmic complexity with memory management issues. By the above reasoning, if I were to run any program using arrays on a system with a two space garbage collector (which copies all live objects during each GC) I could say the worst case algorithmic complexity was O(n). That doesn't sound right. I could take this further and say that in a virtual memory system, there is a chance that the whole heap gets copied to the disk and back between each array update. I might again say this has O(n) complexity, but it wouldn't be very helpful... Ben. ------------------------------ Message: 9 Date: Sat, 21 Nov 2009 15:10:05 +0100 From: Nicolas Pouillard <nicolas.pouill...@gmail.com> Subject: Re: [Haskell-beginners] Re: Is Haskell for me? To: Ben Lippmeier <ben.lippme...@anu.edu.au> Cc: beginners <beginners@haskell.org> Message-ID: <1258812414-sup-2...@peray> Content-Type: text/plain; charset=UTF-8 Excerpts from Ben Lippmeier's message of Sat Nov 21 12:56:09 +0100 2009: > > On 21/11/2009, at 21:13 , Nicolas Pouillard wrote: > > > Excerpts from Ben Lippmeier's message of Sat Nov 21 07:38:09 +0100 2009: > >> > >> On 21/11/2009, at 15:36 , Jon Harrop wrote: > >> > >>> The long-standing bug in GHC's garbage collector that makes writing a > >>> single > >>> boxed value into an array O(n) instead of O(1), because the GC dirties > >>> and > >>> retraverses the entire array, makes it impossible to write efficient > >>> Haskell > >>> code to solve many basic problems. > >> > >> Are you talking about http://hackage.haskell.org/trac/ghc/ticket/650 ? > >> > >> The way I read that ticket is that writing a boxed value to a mutable > >> array is still O(1), but the garbage collector traverses the whole array > >> during > >> scanning. That could certainly slow down GC cycles, but how does it make > >> array update O(n)? > > > > He means in worst case. Writing once, will cause O(n) during the next GC. Of > > course if you do a lot of updates between two GCs their is no extra penalty. > > So if you make 'k' updates between 2 GCs it costs you k*O(1)+O(n) which is > > still O(n) but practically nicer than k*O(n). > > > Hmm. I'd be careful about conflating algorithmic complexity with memory > management issues. By the above reasoning, if I were to run any program using > arrays on a system with a two space garbage collector (which copies all live > objects during each GC) I could say the worst case algorithmic complexity was > O(n). That doesn't sound right. > I could take this further and say that in a virtual memory system, there is a > chance that the whole heap gets copied to the disk and back between each > array update. I might again say this has O(n) complexity, but it wouldn't be > very helpful... Your algorithm is O(1) but the current run-time system can take a time closer to O(n). This could be the case with a two spaces GC or with swapping. -- Nicolas Pouillard http://nicolaspouillard.fr ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 17, Issue 19 *****************************************