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

[Dimitri DeFigueiredo]

I think that in the second case (ulast' in your test) still performs 2 
checks per iteration as it has to check for the empty list on its second 
argument at every recursive call (that's how it knows it's done). So, we 
are performing the same number of iterations. Maybe there's another 
reason for the "ugly"  version to be preferred. Even if it is 
performance and not lazyness, I still don't understand what would make 
it faster.

Thanks,

Dimitri



Em 04/04/14 13:26, Rudy Matela escreveu:
> 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
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners