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. Re: Re: Is Haskell for me? (Nathan M. Holden)
2. Re: Re: Is Haskell for me? (Jon Harrop)
3. Re: Type classes and synonyms (Philip Scott)
4. Re: Type classes and synonyms (Chadda? Fouch?)
5. Re: Type classes and synonyms (Daniel Fischer)
6. Re: Type classes and synonyms (Philip Scott)
7. Re: Type classes and synonyms (Felipe Lessa)
----------------------------------------------------------------------
Message: 1
Date: Sat, 21 Nov 2009 13:57:21 -0500
From: "Nathan M. Holden" <[email protected]>
Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="iso-8859-1"
I'm not a Haskell expert-- in fact, I'm a beginner, and that's why I'm here,
but I read your blog post on the subject of this hash table program, and it
seems to me from reading the comments in reply that you're just here trolling,
because you're using an algorithm that is fundamentally not purely functional,
and of course that's going to be slower, just like asking Joel Zumaya to pitch
left handed.
If you were being honest about your complaint, you'd make an apples-to-apples
comparison, and a number of commenters on your blog have proposed
implementations that perform much better than your example.
Sorry if I'm just being a jerk,
Nathan M. Holden,
Haskell Beginner
On Saturday 21 November 2009 12:55:03 pm [email protected] wrote:
> Message: 4
> Date: Sat, 21 Nov 2009 18:02:33 +0000
> From: Jon Harrop <[email protected]>
> Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
> To: Ben Lippmeier <[email protected]>
> Cc: beginners <[email protected]>
> Message-ID: <[email protected]>
> Content-Type: text/plain; charset="iso-8859-1"
>
> On Saturday 21 November 2009 11:56:09 Ben Lippmeier wrote:
> > Hmm. I'd be careful about conflating algorithmic complexity with memory
> > management issues.
>
> No need. Just look at how badly the performance scales for Haskell vs other
> languages. For example, inserting 1-16 million floating point key/values
> into a hash table:
>
> Haskell OCaml F#
> 1M: 3.198s 1.0x 1.129s 1.0x 0.080s 1.0x
> 2M: 8.498s 2.7x 2.313s 2.0x 0.138s 1.7x
> 4M: 25.697s 8.0x 4.567s 4.0x 0.281s 3.5x
> 8M: 97.994s 30.6x 10.450s 9.3x 0.637s 8.0x
> 16M: 388.080s 121.4x 23.261s 20.6x 1.338s 16.7x
>
> Note that Haskell is 290x slower than F# on that last test.
>
> In practice, you would turn to a purely functional dictionary in Haskell
> based upon balanced binary trees in order to work around this
> long-standing bug in the GC but those trees incur O(log n) indirections
> and typically run orders of magnitude slower than a decent hash table.
>
> Suffice to say, Haskell is nowhere near being in the ballpark of C++'s
> performance for basic functionality like dictionaries and sorting.
>
> > 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.
>
> Can you write a program that demonstrates this effect as I did?
>
> > 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.
>
> Can you write a program that demonstrates this effect as I did?
------------------------------
Message: 2
Date: Sat, 21 Nov 2009 20:52:30 +0000
From: Jon Harrop <[email protected]>
Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
To: "Nathan M. Holden" <[email protected]>,
[email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Saturday 21 November 2009 18:57:21 you wrote:
> I'm not a Haskell expert-- in fact, I'm a beginner, and that's why I'm
> here, but I read your blog post on the subject of this hash table program,
> and it seems to me from reading the comments in reply that you're just here
> trolling, because you're using an algorithm that is fundamentally not
> purely functional, and of course that's going to be slower, just like
> asking Joel Zumaya to pitch left handed.
>
> If you were being honest about your complaint, you'd make an
> apples-to-apples comparison, and a number of commenters on your blog have
> proposed implementations that perform much better than your example.
>
> Sorry if I'm just being a jerk,
Not at all, that is a perfectly reasonable concern but I did already try to
address it in my previous post:
> > In practice, you would turn to a purely functional dictionary in Haskell
> > based upon balanced binary trees in order to work around this
> > long-standing bug in the GC but those trees incur O(log n) indirections
> > and typically run orders of magnitude slower than a decent hash table.
For example, the following Haskell program builds a purely functional
Data.Map:
module Main where
import Prelude hiding (lookup)
import Data.Map (empty, insert, lookup, size)
n = 1000000
build m 0 = m
build m n = build (insert x (1.0 / x) m) (n-1)
where x = fromIntegral n :: Double
main = do
let
m = build empty n
(Just v) = lookup 100 m
print $ size m
print v
Running this program with different "n" gives:
Data.Map
1M: 2.797s 1.0x
2M: 6.090s 2.2x
4M: 14.226s 5.1x
8M: 28.449s 10.2x
16M: 83.171s 29.7x
This is several times faster than Haskell's Data.Hashtable (because of the
long-standing bug in their GC that I described) and is scaling better.
However, if you compare with the timings I gave before:
Data.Hashtable OCaml F#
1M: 3.198s 1.0x 1.129s 1.0x 0.080s 1.0x
2M: 8.498s 2.7x 2.313s 2.0x 0.138s 1.7x
4M: 25.697s 8.0x 4.567s 4.0x 0.281s 3.5x
8M: 97.994s 30.6x 10.450s 9.3x 0.637s 8.0x
16M: 388.080s 121.4x 23.261s 20.6x 1.338s 16.7x
you'll see that the absolute performance of this idiomatic Haskell solution is
still absolutely awful: consistently about 50x slower than the F#.
This is also true in the context of sorting: Haskell's standard library
routines for sorting are orders of magnitude slower than those found in most
other compiled languages.
Suffice to say, idiomatic Haskell is also nowhere near being in the same
ballpark as C++ with respect to performance. Realistically, with enough
expertise you should be able to optimize most of your Haskell programs to
beat Python's performance but there are some important cases where you will
not even be able to do that.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
------------------------------
Message: 3
Date: Sat, 21 Nov 2009 20:33:28 +0000
From: Philip Scott <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="iso-8859-1"
Hi ho,
> In general, however, you just need practice. Go code! =)
Righto, I am getting stuck in with that. One last question; I've been trying
to read up on Arrows and my mind is being boggled. Via experiment, I have
worked out what 'second' was doing (the documentation is useless unless you
already understand a lot of stuff I clearly don't)
For the other newbies, 'second' takes a function and a tuple, it applies the
function to the second thing in your tuple and returns a tuple with the first
value unchanged, and the result of applying 'f' to the second:
> second (\x -> "fish") (10,20)
(10,"fish")
What I am struggling to understand is what on earth the type signature means:
:t second
second :: (Arrow a) => a b c -> a (d, b) (d, c)
How can (\x -> "fish") be an 'a b c' when it really looks like this:
:t (\x->"fish")
(\x->"fish") :: t -> [Char]
And I am pretty sure I never made any Arrpws...
I feel I am on the verge of understanding something deep and fundamentally
philosophical about the typesystem but I can't quite bend my mind around to it
:)
All the best,
Philip
------------------------------
Message: 4
Date: Sat, 21 Nov 2009 21:51:06 +0100
From: Chadda? Fouch? <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: Philip Scott <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Sat, Nov 21, 2009 at 9:33 PM, Philip Scott
<[email protected]> wrote:
> For the other newbies, 'second' takes a function and a tuple, it applies the
> function to the second thing in your tuple and returns a tuple with the first
> value unchanged, and the result of applying 'f' to the second:
That's what it does on a specific arrow, though generally that's the idea.
> What I am struggling to understand is what on earth the type signature means:
>
> :t second
> second :: (Arrow a) => a b c -> a (d, b) (d, c)
>
> How can (\x -> "fish") be an 'a b c' when it really looks like this:
>
> :t (\x->"fish")
> (\x->"fish") :: t -> [Char]
Right, but you must understand that (->) is a type constructor, just
like Maybe or Either or your Ts. It takes two types parameter and
return a function type. So "a -> b" is the infix syntax, but you could
write that "(->) a b" just like you can write "3 + 5" as "(+) 3 5".
Once you've done that on your function you get "(->) t Char" which
looks a bit more like "a b c"...
The final piece is that (->) is an Arrow, the most basic one but still
an Arrow, so if you replace a by (->) in the type of second, you get :
second :: (->) b c -> (->) (d, b) (d, c)
which is just
second :: (b -> c) -> (d, b) -> (d, c)
which corresponds exactly to the action of second you described
(that's the only function that could have this type, except bottom of
course).
--
Jedaï
------------------------------
Message: 5
Date: Sat, 21 Nov 2009 21:51:42 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Samstag 21 November 2009 21:33:28 schrieb Philip Scott:
> Hi ho,
>
> > In general, however, you just need practice. Go code! =)
>
> Righto, I am getting stuck in with that. One last question; I've been
> trying to read up on Arrows and my mind is being boggled. Via experiment, I
> have worked out what 'second' was doing (the documentation is useless
> unless you already understand a lot of stuff I clearly don't)
>
> For the other newbies, 'second' takes a function and a tuple, it applies
> the function to the second thing in your tuple and returns a tuple with the
> first
>
> value unchanged, and the result of applying 'f' to the second:
> > second (\x -> "fish") (10,20)
>
> (10,"fish")
>
> What I am struggling to understand is what on earth the type signature means:
> :t second
>
> second :: (Arrow a) => a b c -> a (d, b) (d, c)
>
> How can (\x -> "fish") be an 'a b c' when it really looks like this:
> :t (\x->"fish")
> (\x->"fish") :: t -> [Char]
a is a type variable (restricted to be a member of the Arrow class).
Now the type ghci reports for (\x -> "fish") is printed in infix form, in
prefix form, it
reads
:t (\x -> "fish")
(\x -> "fish") :: (->) t [Char]
so we find
a = (->)
b = t
c = [Char]
and you're using the most widespread instance of Arrow, (->).
Arrows are a generalisation of functions.
Until you're more familiar with Arrows, I suggest replacing any
(Arrow a) with (->) in the type signatures to understand what things mean in
the familiar
case.
Next in line would probably be Kleisli arrows (Monad m => a -> m b; it's
wrapped in a
newtype for Control.Arrow), break at any level of abstraction you want and
return later.
>
> And I am pretty sure I never made any Arrpws...
There are a few others have made for you to use :)
>
> I feel I am on the verge of understanding something deep and fundamentally
> philosophical about the typesystem but I can't quite bend my mind around to
> it
>
> :)
>
> All the best,
>
> Philip
------------------------------
Message: 6
Date: Sat, 21 Nov 2009 21:07:38 +0000
From: Philip Scott <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="utf-8"
> The final piece is that (->) is an Arrow, the most basic one but still
> an Arrow, so if you replace a by (->) in the type of second, you get :
> second :: (->) b c -> (->) (d, b) (d, c)
> which is just
> second :: (b -> c) -> (d, b) -> (d, c)
Ahh I see, very clever! There is method to the madness after all; I should
never have doubted you Haskell. Thank you for taking the time to explain that
:)
Do you know of any good discussions/tutorials on Arrows? I've only managed to
find little snippets here and there
http://www.haskell.org/arrows/
Doesn't have a lot of detail and
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Arrow.html
..would probably be useful once I actually understand what is going on but
right now I think a slap in the face with a big wet fish might help me more ;)
- Philip
------------------------------
Message: 7
Date: Sat, 21 Nov 2009 19:08:33 -0200
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sat, Nov 21, 2009 at 08:33:28PM +0000, Philip Scott wrote:
> Righto, I am getting stuck in with that. One last question; I've been trying
> to read up on Arrows and my mind is being boggled. Via experiment, I have
> worked out what 'second' was doing (the documentation is useless unless you
> already understand a lot of stuff I clearly don't)
>
> For the other newbies, 'second' takes a function and a tuple, it applies the
> function to the second thing in your tuple and returns a tuple with the first
> value unchanged, and the result of applying 'f' to the second:
>
> > second (\x -> "fish") (10,20)
> (10,"fish")
>
> What I am struggling to understand is what on earth the type signature means:
>
> :t second
> second :: (Arrow a) => a b c -> a (d, b) (d, c)
>
> How can (\x -> "fish") be an 'a b c' when it really looks like this:
>
> :t (\x->"fish")
> (\x->"fish") :: t -> [Char]
>
> And I am pretty sure I never made any Arrpws...
>
> I feel I am on the verge of understanding something deep and fundamentally
> philosophical about the typesystem but I can't quite bend my mind around to it
> :)
The problem you're facing is that you have to think of the arrow
operator (->) as a type constructor. IOW, to unify :
a b c with t -> [Char]
you have the following "assignments":
a ~ (->)
b ~ t
c ~ [Char]
In another other words,
t -> [Char] is the same as (->) t [Char]
Now it's easy to see whats happening. Note that (->) is an
instance to Arrow, in GHCi:
Prelude Control.Arrow> :i Arrow
class (Control.Category.Category a) => Arrow a where
arr :: (b -> c) -> a b c
first :: a b c -> a (b, d) (c, d)
second :: a b c -> a (d, b) (d, c)
(***) :: a b c -> a b' c' -> a (b, b') (c, c')
(&&&) :: a b c -> a b c' -> a b (c, c')
-- Defined in Control.Arrow
instance Arrow (->) -- Defined in Control.Arrow <<< HERE <<<
instance (Monad m) => Arrow (Kleisli m) -- Defined in Control.Arrow
Specializing those types to Arrow (->) and using the common infix
notation we have that:
arr :: (b -> c) -> (b -> c)
first :: (b -> c) -> ((b, d) -> (c, d))
second :: (b -> c) -> ((d, b) -> (d, c))
(***) :: (b -> c) -> (b' -> c') -> ((b, b') -> (c, c'))
(&&&) :: (b -> c) -> (b' -> c') -> (b -> (c, c'))
Note that 'arr = id'. That's why we may use all Arrow functions
on, err, plain functions without having wrap everything with
'arr' (as you would with any other arrow).
It's a good exercise to try to reproduce the definition of the
Arrow (->) instance by defining the functions above. Most
definitions, if not all, are just the corresponding free theorems
(meaning roughly that the definition follows from the type
because that's the only definition that doesn't have
undefined's).
HTH!
--
Felipe.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 17, Issue 21
*****************************************
