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 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

---

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

Hi Daniel, I really like your translation of ulast' below ulast' y ys = case ys of [] -> y z:zs -> ulast' z zs This makes it really clear there is only one comparison happening. I tried looking at core with the -O option (ghc 7.6.3), but am having a had time making sense of it. For comparison, could you also translate the inefficient version of plast into the case notation you use above? Thanks, Dimitri ==================== Tidy Core ==================== Result size of Tidy Core = {terms: 49, types: 58, coercions: 0} lvl_rgS :: [GHC.Types.Char] [GblId] lvl_rgS = GHC.CString.unpackCString# "empty list!" Test.ulast2 :: forall a_b. a_b [GblId, Str=DmdType b] Test.ulast2 = \ (@ a_b) -> GHC.Err.error @ a_b lvl_rgS Rec { Test.ulast1 [Occ=LoopBreaker] :: forall a_b. a_b -> [a_b] -> a_b [GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LS] Test.ulast1 = \ (@ a_b) (y_aeQ :: a_b) (ds_df8 :: [a_b]) -> case ds_df8 of _ { [] -> y_aeQ; : y1_aeR ys_aeS -> Test.ulast1 @ a_b y1_aeR ys_aeS } end Rec } Test.ulast :: forall a_aeH. [a_aeH] -> a_aeH [GblId, Arity=1, Str=DmdType S, Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=1, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [30] 50 0}] Test.ulast = \ (@ a_b) (ds_df6 :: [a_b]) -> case ds_df6 of _ { [] -> Test.ulast2 @ a_b; : x_aeN xs_aeO -> Test.ulast1 @ a_b x_aeN xs_aeO } lvl1_rgT :: forall a_d. a_d [GblId, Str=DmdType b] lvl1_rgT = \ (@ a_d) -> GHC.Err.error @ a_d lvl_rgS Rec { Test.plast [Occ=LoopBreaker] :: forall a_aeI. [a_aeI] -> a_aeI [GblId, Arity=1, Str=DmdType S] Test.plast = \ (@ a_d) (ds_dfc :: [a_d]) -> case ds_dfc of _ { [] -> lvl1_rgT @ a_d; : x_aeJ ds1_dfd -> case ds1_dfd of wild1_X8 { [] -> x_aeJ; : ipv_sfz ipv1_sfA -> Test.plast @ a_d wild1_X8 } } end Rec } ======

Hi Daniel,

Thanks so much for the detailed explanations!
I got it now.

:-D

Dimitri


Em 04/04/14 17:23, Daniel Fischer escreveu:
> On Friday 04 April 2014, 15:55:57, Dimitri DeFigueiredo wrote:
>> Hi Daniel,
>>
>> I really like your translation of ulast' below
>>
>> ulast' y ys = case ys of
>>                   [] -> y
>>                   z:zs -> ulast' z zs
>>
>> This makes it really clear there is only one comparison happening. I
>> tried looking
>> at core with the -O option (ghc 7.6.3), but am having a had time making
>> sense of it.
> I'll add explanations between the core below.
>
>> For comparison, could you also translate the inefficient version of plast
>> into the case notation you use above?
> GHC already did that, I'll put it next to the core at the bottom.
>
>>
>> Thanks,
>>
>> Dimitri
>>
>> ==================== Tidy Core ====================
>> Result size of Tidy Core = {terms: 49, types: 58, coercions: 0}
>>
>> lvl_rgS :: [GHC.Types.Char]
>> [GblId]
>> lvl_rgS = GHC.CString.unpackCString# "empty list!"
>>
>> Test.ulast2 :: forall a_b. a_b
>> [GblId, Str=DmdType b]
>> Test.ulast2 = \ (@ a_b) -> GHC.Err.error @ a_b lvl_rgS
> All of the above is uninteresting, apart from some stats at the header line,
> we have the error call in case the function is called with an empty list.
>
> What follows is the code for the worker ulast', named ulast1 in the core.
>
>> Rec {
>> Test.ulast1 [Occ=LoopBreaker] :: forall a_b. a_b -> [a_b] -> a_b
> ulast1is a loop-breaker, it cannot be inlined (it is recursive, thus it cannot
> be inlined anyway), but that need not interest at the moment. Its type is
>
> a -> [a] -> a
>
> but GHC added a suffix to get unique identifiers. You can suppress that with
> the flag -dsuppress-uniques
>
>> [GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LS]
> It takes two arguments, doesn't refer to any CAFs, and is lazy in the first
> argument, strict in the second.
>
>> Test.ulast1 =
>>     \ (@ a_b) (y_aeQ :: a_b) (ds_df8 :: [a_b]) ->
> The arguments. First is the type at which it is called, then come
> - the last list element we have found so far, y_aeQ, and
> - the remaining part of the list, ds_df8.
>
>>       case ds_df8 of _ {
> The list argument is evaluated (to weak head normal form), but it is never
> referred to later as a whole, hence it's not bound to an identifier, so we
> have a wild-card `_` after the `case ... of`
>
>>         [] -> y_aeQ;
> Totally Haskell, if the remaining part of the list is empty, return the last
> element, otherwise
>   
>>         : y1_aeR ys_aeS -> Test.ulast1 @ a_b y1_aeR ys_aeS
> remember the next list element and recur. In core, we have unparenthesised
> prefix application also of infix operators, so the match that in Haskell looks
>
>      y1_aeR : ys_aeS
>
> looks a bit different in core, but is recognisable.
>   
>>       }
>> end Rec }
> Now comes the code for the wrapper. That's not recursive, hence we don't have
> the "Rec" annotations, and it's not a loop-breaker, it can be inlined. The
> type signature is clear, with an explicit forall.
>   
>> Test.ulast :: forall a_aeH. [a_aeH] -> a_aeH
>> [GblId,
>>    Arity=1,
>>    Str=DmdType S,
> It takes one argument and is strict in that argument, next comes unfolding
> info, in case it shall be inlined elsewhere, that doesn't need to interest us
> now.
>
>>    Unf=Unf{Src=, TopLvl=True, Arity=1, Value=True,
>>            ConLike=True, WorkFree=True, Expandable=True,
>>            Guidance=IF_ARGS [30] 50 0}]
>> Test.ulast =
>>     \ (@ a_b) (ds_df6 :: [a_b]) ->
> The type at which ulast is called, and the argument it is passed
>
>>       case ds_df6 of _ {
> The list is evaluated (to WHNF),
>
>>         [] -> Test.ulast2 @ a_b;
> If the list is empty, call error
>
>>         : x_aeN xs_aeO -> Test.ulast1 @ a_b x_aeN xs_aeO
> Otherwise call the worker
>
>>       }
>>
>> lvl1_rgT :: forall a_d. a_d
>> [GblId, Str=DmdType b]
>> lvl1_rgT = \ (@ a_d) -> GHC.Err.error @ a_d lvl_rgS
> Another error call, this time to be called from plast
>
>> Rec {
>> Test.plast [Occ=LoopBreaker] :: forall a_aeI. [a_aeI] -> a_aeI
> plast is recursive, a loop-breaker (no inlining possible), and its type
>
>> [GblId, Arity=1, Str=DmdType S]
> it takes one argument, and is strict in it
>
>> Test.plast =
>>     \ (@ a_d) (ds_dfc :: [a_d]) ->
>>       case ds_dfc of _ {
> The list is evaluated
>
>>         [] -> lvl1_rgT @ a_d;
> If it is empty, call error,
>
>>         : x_aeJ ds1_dfd ->
> otherwise, bind the first element and the tail to names
>
>>           case ds1_dfd of wild1_X8 {
> and evaluate the tail. The tail may be referenced later, hence the evaluated
> tail is bound to a name - wild1_X8.
>
>>             [] -> x_aeJ;
> If the tail is empty, return the first (only) element of plast's argument
>
>>             : ipv_sfz ipv1_sfA -> Test.plast @ a_d wild1_X8
> otherwise recur on the tail.
>
>>           }
>>       }
>> end Rec }
> The Haskell case-construct corresponding to the core is
>
> plast :: [a] -> a
> plast xs = case xs of
>               [] -> error "empty list!"
>               y:ys -> case ys of
>                         [] -> y
>                         z:zs -> plast ys
>
>

On Friday 04 April 2014, 20:12:50, Rudy Matela wrote:

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.

One can check that, just copy the source (hiding Prelude.last or renaming it) and compile, with -ddump-simpl to get the core GHC produces (it takes a little practice to read core, but it's sufficiently similar to Haskell to start understanding much of it quickly). With -O2, all GHC versions I tried (6.12.3, 7.0.2, 7.2.2, 7.4.2, 7.6.1, 7.6.3) produced (almost¹) the more efficient version from the USE_REPORT_PRELUDE source, but with only -O, none did. If the libraries are guaranteed to be compiled with -O2 when building the compiler, there would be no need for the other source. But since that is not guaranteed, it's better to manually write the better version. Footnote (¹): what GHC produces with -O2 is slightly different, it tests for a singleton list once in the wrapper before the worker is called, but it also creates a rule that when it is called on a list that is known at compile-time to be nonempty, the worker shall be called directly. Cheers, Daniel