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: Long time no Haskell....simple typeclass question
(Nicholls, Mark)
2. Continuations (Cary Cherng)
3. Re: Continuations (Michael Snoyman)
4. Re: Continuations (Jay Sulzberger)
5. Re: Continuations (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Wed, 31 Dec 2014 13:26:03 +0000
From: "Nicholls, Mark" <[email protected]>
To: "The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell" <[email protected]>
Subject: Re: [Haskell-beginners] Long time no Haskell....simple
typeclass question
Message-ID:
<e7e7fdf32472ff48bb0e4d9dc4283d0e83849...@mtvne-exmb02.mtvne.ad.viacom.com>
Content-Type: text/plain; charset="us-ascii"
Actually I can fix it by following the Haskell advice and reading
http://blog.omega-prime.co.uk/?p=127 and turning on some extensions...
Basically....
You DO follow Haskell's advice by amending the class declaration with a class
content on the exe function, but you can let the instance declaration declare
the constraint by....
turning the constraint into a type (ConstraintKinds)
You then use type families (TypeFamilies) to calculate the constraint in the
instance declaration.
> {-# LANGUAGE TypeFamilies, ConstraintKinds #-}
> import GHC.Prim
> data Func a b = Func (a->b)
> exeFunc :: (Ord a) => Func a b -> a -> b
> exeFunc (Func g) = g
> class IFunc f where
> type ExeConstraint f a b :: Constraint
> exe :: (ExeConstraint f a b) => f a b -> a -> b
> instance IFunc Func where
> type ExeConstraint Func a b = Ord a
> exe = exeFunc
As opposed to the instance declaration for the function type, which has no
constraint
> instance IFunc (->) where
> type ExeConstraint (->) a b = ()
> exe f = f
In some sense it still feels clumsy....with my F bounded OO type head
on...which I'm told I must ignore....in something like C# this would be
something like...
interface IOrd {}
interface IFunc<A,B>
{
B Exe(A a);
}
class Fun<A,B> : IFunc<A,B>
where A : IOrd
{
readonly Func<A,B> f;
public Fun(Func<A,B> f) { this.f = f; }
public B Exe(A a)
{
return this.f(a);
}
}
i.e. here the IFunc declaration is closed...and blissfully unaware of any
horrible constraints that need to be applied in order for the compiler to make
the data type inhabit the type.
If I want to make my typeclass definitions as closed in Haskell, it would seem
that I would always have to declare them with indexed types as constraints?
Or am I missing something? (I expect there is a reason, and I'm aware I'm
comparing apple Haskell type(classe)s with orange C# types).
CONFIDENTIALITY NOTICE
This e-mail (and any attached files) is confidential and protected by copyright
(and other intellectual property rights). If you are not the intended recipient
please e-mail the sender and then delete the email and any attached files
immediately. Any further use or dissemination is prohibited.
While MTV Networks Europe has taken steps to ensure that this email and any
attachments are virus free, it is your responsibility to ensure that this
message and any attachments are virus free and do not affect your systems /
data.
Communicating by email is not 100% secure and carries risks such as delay, data
corruption, non-delivery, wrongful interception and unauthorised amendment. If
you communicate with us by e-mail, you acknowledge and assume these risks, and
you agree to take appropriate measures to minimise these risks when e-mailing
us.
MTV Networks International, MTV Networks UK & Ireland, Greenhouse, Nickelodeon
Viacom Consumer Products, VBSi, Viacom Brand Solutions International, Be
Viacom, Viacom International Media Networks and VIMN and Comedy Central are all
trading names of MTV Networks Europe. MTV Networks Europe is a partnership
between MTV Networks Europe Inc. and Viacom Networks Europe Inc. Address for
service in Great Britain is 17-29 Hawley Crescent, London, NW1 8TT.
------------------------------
Message: 2
Date: Wed, 31 Dec 2014 20:00:04 -0800
From: Cary Cherng <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Continuations
Message-ID:
<capxkqhg-8pbowfhzuticn0fpfru5tannx8bnurgp_uprupv...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
I read (http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style)
that in some circumstances, CPS can be used to improve performance by
eliminating certain construction-pattern matching sequences (i.e. a
function returns a complex structure which the caller will at some
point deconstruct). And that attoparsec is an example of this.
I don't see exactly how CPS gives rise to concrete examples of
performance gains. Moreover how does this arise in parsing for example
with attoparsec as mentioned.
I also encountered various web frameworks such as mflow that are based
on continuations. How a typical http restful system is made into
something based around continuations is not something that is obvious
to me. And what is gained from that?
------------------------------
Message: 3
Date: Thu, 01 Jan 2015 06:42:28 +0000
From: Michael Snoyman <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Continuations
Message-ID:
<caka2jgjsvv8z22a90amdftdfywdzecdvejaoe1buswxjb66...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
To give an idea of why CPS transform can sometimes be more efficient,
consider the following two approaches to a "safe divide" function, which
check if the denominator is 0:
divMay :: Double -> Double -> Maybe Double
divMay x y
| y == 0 = Nothing
| otherwise = Just (x / y)
divCPS :: Double -> Double -> a -> (Double -> a) -> a
divCPS x y onFail onSuccess
| y == 0 = onFail
| otherwise = onSuccess (x / y)
Presumably, divMay will always force the allocation of a new object when y
is not 0, through its usage of Just. divCPS, on the other hand, does not
need to perform any allocation. I say presumably, because often times the
compiler will be able to optimize this. To see evidence of that, I've put
together a small benchmark[1], If I compile with optimizations turned of
(-O0), I get results showing that CPS is faster. And looking at the
core[2], we can see that divMay really does result in an extra allocation:
$ ghc-core --no-cast -- -O0 foo.hs
divMay'_r454 :: Double -> Double
divMay'_r454 =
\ (y_a4hf :: Double) ->
Data.Maybe.fromMaybe
@ Double
(D# 0.0)
(case ==
@ Double $fEqDouble y_a4hf (D# 0.0)
of _ [Occ=Dead] {
False ->
Data.Maybe.Just
@ Double
(/
@ Double
$fFractionalDouble
(D# 10.0)
y_a4hf);
True -> Data.Maybe.Nothing @ Double
})
divCPS'_r455 :: Double -> Double
divCPS'_r455 =
\ (y_a4hg :: Double) ->
case ==
@ Double $fEqDouble y_a4hg (D# 0.0)
of _ [Occ=Dead] {
False ->
id
@ Double
(/
@ Double
$fFractionalDouble
(D# 10.0)
y_a4hg);
True -> D# 0.0
}
Yes, core has a lot of stuff going on due to the explicit type signatures,
the "magic hash" unboxed types showing up, etc. But as you can see, there's
a call to Data.Maybe.Just in divMay' that is not present in divCPS'.
Now let's explain that "presumably" comment. GHC is really smart, and if
you let it, it will often times optimize away these kinds of things,
especially in small examples like this. In this case, the benchmark results
show up as almost identical between the two versions, which is hardly
surprising when you look at the core:
$ ghc-core --no-cast -- -O2 foo.hs
divMay'_r4ci :: Double -> Double
divMay'_r4ci =
\ (y_a4oE :: Double) ->
case y_a4oE of _ [Occ=Dead] { D# x_a4Ml ->
case x_a4Ml of wild1_X10 {
__DEFAULT ->
case /## 10.0 wild1_X10 of wild2_a4Rj { __DEFAULT ->
D# wild2_a4Rj
};
0.0 -> main9
}
}
divCPS'_r4cj :: Double -> Double
divCPS'_r4cj =
\ (y_a4oF :: Double) ->
case y_a4oF of _ [Occ=Dead] { D# x_a4Ml ->
case x_a4Ml of wild1_X15 {
__DEFAULT ->
case /## 10.0 wild1_X15 of wild2_a4Rj { __DEFAULT ->
D# wild2_a4Rj
};
0.0 -> main9
}
}
If you look past the different variable names, you'll see that the two
functions are in fact identical. So to sum up this (longer than expected)
email:
* CPS allows you to avoid extra allocations,
* but often times GHC can perform that optimization for you itself.
You can look at the attoparsec codebase to see its usage of CPS, which is a
more complicated usage of this same concept. Continuation passing web
frameworks are a totally different story though, and have been covered
pretty well elsewhere (probably best by Alberto[3], though others may have
different links).
[1]
https://www.fpcomplete.com/user/snoyberg/random-code-snippets/cps-performance-benchmark
[2] Core is a lower-level form that GHC compiles code to before generating
machine code. It gives a very good idea of what optimizations have been
applied. I used the ghc-core tool for this. Gabriel Gonzalez wrote a nice
blog post about this a few years back:
http://www.haskellforall.com/2012/10/hello-core.html
[3] https://www.fpcomplete.com/user/agocorona
On Thu Jan 01 2015 at 6:00:12 AM Cary Cherng <[email protected]> wrote:
> I read (http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style)
> that in some circumstances, CPS can be used to improve performance by
> eliminating certain construction-pattern matching sequences (i.e. a
> function returns a complex structure which the caller will at some
> point deconstruct). And that attoparsec is an example of this.
>
> I don't see exactly how CPS gives rise to concrete examples of
> performance gains. Moreover how does this arise in parsing for example
> with attoparsec as mentioned.
>
>
> I also encountered various web frameworks such as mflow that are based
> on continuations. How a typical http restful system is made into
> something based around continuations is not something that is obvious
> to me. And what is gained from that?
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150101/a31a5abf/attachment-0001.html>
------------------------------
Message: 4
Date: Thu, 1 Jan 2015 02:15:37 -0500 (EST)
From: Jay Sulzberger <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Continuations
Message-ID: <[email protected]>
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
On Wed, 31 Dec 2014, Cary Cherng <[email protected]> wrote:
> I read (http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style)
> that in some circumstances, CPS can be used to improve performance by
> eliminating certain construction-pattern matching sequences (i.e. a
> function returns a complex structure which the caller will at some
> point deconstruct). And that attoparsec is an example of this.
>
> I don't see exactly how CPS gives rise to concrete examples of
> performance gains. Moreover how does this arise in parsing for example
> with attoparsec as mentioned.
>
>
> I also encountered various web frameworks such as mflow that are based
> on continuations. How a typical http restful system is made into
> something based around continuations is not something that is obvious
> to me. And what is gained from that?
I just found this delightful article by John C. Reynolds:
The Discoveries of Continuations
http://www.math.bas.bg/bantchev/place/iswim/conti-disco.pdf
oo--JS.
------------------------------
Message: 5
Date: Thu, 1 Jan 2015 17:08:40 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Continuations
Message-ID:
<capy+zdre3bjbmvsxuayhna_qebq57b4c1io0mqdha9jzbtr...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Thu, Jan 1, 2015 at 11:00 AM, Cary Cherng <[email protected]> wrote:
> I don't see exactly how CPS gives rise to concrete examples of
> performance gains.
>
If you look at the "Reflection without Remorse" paper, you'll see
performance gains painstakingly described for DLists / difference lists of
type [a] -> [a].
The authors see such gains as an application of CPS, the moral being that
CPS has a broad range of meanings.
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150101/343de290/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 79, Issue 1
****************************************
