On 09/25/2014 12:03 AM, Andrei Alexandrescu wrote:
On 9/24/14, 2:43 PM, Joakim wrote:
On Wednesday, 24 September 2014 at 19:38:37 UTC, bearophile wrote:
Joakim:
I wonder why they found Haskell to be so slow, I thought it was
compiled.
The first reason for the performance of programs is how much care the
programmer has to write a fast program, secondly how good the chosen
algorithms are, and only then at a third place there are language
implementations.
So Haskell programmers don't care about fast programs and don't know how
to choose good algorithms? ;)
Sadly that's only half of a joke.
...
Some (non-exhaustive!) basic evidence for the other half:
http://book.realworldhaskell.org/read/profiling-and-optimization.html
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
Google for "Haskell tutorial", you'll get
http://www.haskell.org/haskellwiki/Tutorials at the top. First "best
place to start" leads to
http://www.seas.upenn.edu/~cis194/lectures/01-intro.html. On that page,
literally the first function defined is:
sumtorial :: Integer -> Integer
sumtorial 0 = 0
sumtorial n = n + sumtorial (n-1)
i.e. an linear-space way of doing summation.
sumtorial = foldl' (+) 0 . enumFromTo 0 :: Integer -> Integer
sumtorial n = n*(n+1) `div` 2 :: Integer
The next link, that wasn't considered, is
http://book.realworldhaskell.org/read/types-and-functions.html which
does a better job, by defining a function that is actually usable.
Just a bit below there's:
-- Compute the length of a list of Integers.
intListLength :: [Integer] -> Integer
intListLength [] = 0
intListLength (x:xs) = 1 + intListLength xs
i.e. an linear-space way of computing length. These are functions that
are computationally bankrupt, we're not talking small constant fish here.
...
Note that GHC has a history of transforming certain O(1) space
computations to Ω(N) space computations with certain optimizations
enabled. The relative overhead will decrease in such cases. :o)
But the other direction is allowed. I.e. it is not actually a given that
those examples will use linear space. (IIRC they will in practice.)
Well maybe that's not a very good tutorial. Let's move on to the second
recommended reading, the famous "Learn You a Haskell for Great Good!"
Sure that's going to be awesome. The first nontrivial function the
tutorial ever defines from first principles at
http://learnyouahaskell.com/syntax-in-functions#pattern-matching is...
factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)
... again, a gratuitously linear-space function.
Someone should do hard time for this.
...
To be fair, a "real" factorial uses Ω(n log n) space anyway.
