Haskell Writing myLength
haskell
Solution
When you say "`length` in `Prelude` returns ... in 0.37 sec", which compiler are you referring to? If you are using GHC, you can see, e.g., here that the actual implementation differs from the simple
length [] = 0
length (x:xs) = 1 + length xs
Namely, it is:
length l = len l 0#
where
len :: [a] -> Int# -> Int
len [] a# = I# a#
len (_:xs) a# = len xs (a# +# 1#)
This code uses an accumulator and avoids the problem of huge unevaluated thunks by using unboxed integers, i.e., this version is highly optimized.
To illustrate the problem with the "simple" version, consider how `length [1, 2, 3]` is evaluated:
length [1, 2, 3]
=> 1 + length [2, 3]
=> 1 + (1 + length [3])
=> 1 + (1 + (1 + length []))
=> 1 + (1 + (1 + 0))
The sum is not evaluated until its result is really needed, thus you see that when the input is a huge list, you will create a huge sum in memory first and then only evaluate it when its result is really needed.
In contrast the optimized version evaluates as follows:
length [1, 2, 3]
=> len [1, 2, 3] 0#
=> len [2, 3] (1#)
=> len [3] (2#)
=> len [] (3#)
=> 3
i.e., the "+1" is done immediately.
Problem
I was working on this page http://www.haskell.org/haskellwiki/99_questions/Solutions/4 I understand what each function means and it is fun to see that a function can be defined in numerous ways like this. However, I just started wondering which one is faster. And I thought it would be the one it says is `length` in `Prelude`. ``` length [] = 0 length (x:xs) = 1 + length xs ``` However, this is much slower than `length` in `Prelude`. On my computer `length` in `Prelude` returns a length of `[1..10^7]` in 0.37 sec. However the function defined as above took 15.26 sec. I defined my own length function, which makes use of an accumulator. It took only 8.99 sec. I am wondering why these big differences occurred?