Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
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" <[email protected]>
Subject: [Haskell-beginners] points-free problem
To: [email protected]
Message-ID:
<[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] points-free problem
To: [email protected]
Message-ID: <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] points-free problem
To: beginners <[email protected]>
Message-ID: <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] points-free problem
To: [email protected]
Message-ID: <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
To: [email protected]
Message-ID: <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
To: Jon Harrop <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
To: Ben Lippmeier <[email protected]>
Cc: beginners <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
To: Nicolas Pouillard <[email protected]>
Cc: beginners <[email protected]>
Message-ID: <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
To: Ben Lippmeier <[email protected]>
Cc: beginners <[email protected]>
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
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 17, Issue 19
*****************************************
