[Haskell-beginners] Definition of last: why complicate it?
Rudy Matela
rudy at matela.com.br
Fri Apr 4 19:26:32 UTC 2014
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
More information about the Beginners
mailing list