Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Definition of last: why complicate it? (Dimitri DeFigueiredo)
2. Re: Definition of last: why complicate it? (Brandon Allbery)
3. Re: Definition of last: why complicate it? (Daniel Fischer)
4. Re: Definition of last: why complicate it? (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Fri, 04 Apr 2014 15:55:57 -0600
From: Dimitri DeFigueiredo <[email protected]>
To: [email protected]
Cc: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Definition of last: why complicate
it?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
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 }
======
------------------------------
Message: 2
Date: Fri, 4 Apr 2014 18:51:11 -0400
From: Brandon Allbery <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Definition of last: why complicate
it?
Message-ID:
<cakfcl4v1dleburnaemzoq2rwejt55k-+76mo_ywrz9nhsnz...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Fri, Apr 4, 2014 at 3:53 PM, Daniel Fischer <
[email protected]> wrote:
> 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.
>
Also worth noting is that ghci does not not have an optimizer; this might
well matter with large lists.
--
brandon s allbery kf8nh sine nomine associates
[email protected] [email protected]
unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140404/4862c3c9/attachment-0001.html>
------------------------------
Message: 3
Date: Sat, 05 Apr 2014 01:23:41 +0200
From: Daniel Fischer <[email protected]>
To: Dimitri DeFigueiredo <[email protected]>
Cc: [email protected]
Subject: Re: [Haskell-beginners] Definition of last: why complicate
it?
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
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
------------------------------
Message: 4
Date: Sat, 5 Apr 2014 10:19:03 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Cc: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Definition of last: why complicate
it?
Message-ID:
<capy+zdt2hqb3prqmwb36wbbm5xzk3uejgol0+f2m-fghffn...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Sat, Apr 5, 2014 at 4:55 AM, Dimitri DeFigueiredo <
[email protected]> wrote:
> For comparison, could you also translate the inefficient version of plast
> into the case notation you use above?
>
You probably already know this already, but it's worth underscoring for
everyone that it's not the translation into case notation /per se/ that
gives you the incremental performance improvement.
A function definition by parts is syntactic sugar for a single case
expression.
All syntactic sugar, including others like do-notation, where clauses,
etc., gets eliminated at the earliest stages when code is handed off to ghc.
I encourage newcomers to familiarize themselves with desugaring to avoid
unpleasant surprises. The sugared syntax often suggests mystery and magic
when there's really nothing of that sort at all.
Coming back to the topic of function definition by parts, aka piecewise
definition, it appears that at least one reputable school thinks it's
"weird" and "confusing" enough to be warrant a ban in homework:
http://www.reddit.com/r/haskell/comments/223fi4/need_help/cgiywxi
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140405/1b88dc09/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 70, Issue 9
****************************************
