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

[Daniel Fischer]

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