[Haskell-beginners] Definition of last: why complicate it?
Daniel Fischer
daniel.is.fischer at googlemail.com
Fri Apr 4 23:23:41 UTC 2014
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
More information about the Beginners
mailing list