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

[Rudy Matela]

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
<defigueiredo at ucdavis.edu> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners