Re: [Haskell-beginners] Definition of last: why complicate it?

You can test the speed in your ghci: -- pretty last plast :: [a] -> a plast [x] = x plast (_:xs) = plast xs plast [] = error "empty list!" -- ugly last ulast :: [a] -> a ulast [] = error "empty list!" ulast (x:xs) = ulast' x xs where ulast' y [] = y ulast' _ (y:ys) = ulast' y ys Not a big difference tough: ghci> :set +s ghci> ulast [1..20000000] 20000000 (2.59 secs, 2721962752 bytes) ghci> plast [1..20000000] 20000000 (2.70 secs, 2401902096 bytes) *Main> However, if you disable optimization (ghci -O0), the difference is more clear: ghci> ulast [1..20000000] 20000000 (2.56 secs, 2729847944 bytes) ghci> plast [1..20000000] 20000000 (3.30 secs, 2401899840 bytes) On Fri, Apr 4, 2014 at 8:12 PM, Rudy Matela wrote:

Hi,

Basically the second one should be faster. I'm *guessing* here as *I'm no Haskell wizard*, so someone correct me if I'm wrong.

In the first version, at each iteraction (applying to a non-empty list), the program will:

1. Check for a non-empty list, with one element -- return x if true *then* 2. Check for a non-empty list -- do something to the tail if true

So basically, at each iteration you're doing two "check operations", and you know that the first operation will be true only for the last element which is wasteful. On a array with 10 elements you do roughly 19 "check operations" (2n - 1).

In the second version:

0. Check for empty list error (you only do that once) because the recursion is on last' then, for each element: 1. check wether the passes list is empty (1 check) -- return y if true, apply recursion if false

On a array with 10 elements you'll do roughly 11 "check operations" (n+1).

According to a stackoverflow answer [1], this should be done automatically by GHC. Why it's still defined like that I don't know: maybe because the code is for when using other compilers, or maybe I misinterpreted the stackoverflow post and GHC is not able to do that.

[1]: https://stackoverflow.com/a/12661937, under "Case Expressions"

Regards, Rudy

On Fri, Apr 4, 2014 at 7:17 PM, Dimitri DeFigueiredo wrote:

...

I was looking at the definition of last in the prelude and saw this code

(from http://hackage.haskell.org/package/base-4.2.0.1/docs/src/GHC-List.html)

-- | Extract the last element of a list, which must be finite and non-empty. last :: [a] -> a #ifdef USE_REPORT_PRELUDE last [x] = x last (_:xs) = last xs last [] = errorEmptyList "last" #else -- eliminate repeated cases last [] = errorEmptyList "last" last (x:xs) = last' x xs where last' y [] = y last' _ (y:ys) = last' y ys #endif

Question: What does the second "eliminate repeated cases" definition of last gain compared to the first (simpler) one?

Thanks

Dimitri _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners