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

[Dimitri DeFigueiredo]

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=<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]) ->
> 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
>
>