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

[Rudy Matela]

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 <rudy at matela.com.br> 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
> <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