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: small question (Bastian Erdn??)
2. Re: small question (Isaac Dupree)
3. Re: small question (Bastian Erdn??)
4. pattern match vs. pure function (Bastian Erdn??)
5. Re: pattern match vs. pure function (Daniel Fischer)
6. Re: pattern match vs. pure function (Bastian Erdn??)
7. Re: pattern match vs. pure function (Brent Yorgey)
8. Re: pattern match vs. pure function (Patrick LeBoutillier)
----------------------------------------------------------------------
Message: 1
Date: Tue, 19 Oct 2010 20:35:44 +0200
From: Bastian Erdn?? <[email protected]>
Subject: Re: [Haskell-beginners] small question
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Oct 19, 2010, at 16:13, Mohamed wrote:
> Hello folks,
>
> just a quickie here and would appreciate any help...
>
> In this expression:
>
>
>
> instance OBSERVATIONS Drinkability WaterWell Volunteer where
> observe (Drinkability waterWell) volunteer = volunteer {vReport =
> if (odorQuale (perceive (Odor waterWell) volunteer) == True &&
> clarityQuale (perceive (Clarity waterWell) volunteer) == True &&
> fullnessQuale
> (perceive (Fullness waterWell) volunteer) == True) then (if (honesty) then
> "drinkable" else "undrinkable") else (if (honesty) then "undrinkable" else
> "drinkable")}
I suppose this could also be written
instance OBSERVATIONS Drinkability WaterWell Volunteer where
observe (Drinkability waterWell) volunteer =
volunteer { vReport = drinkability } where
drinkability = undrinkableIf $ honesty volunteer `xor`
odorQuale (perceive (Odor waterWell) volunteer) &&
clarityQuale (perceive (Clarity waterWell) volunteer) &&
fullnessQuale (perceive (Fullness waterWell) volunteer)
undrinkableIf True = "undrinkable"
undrinkableIf False = "drinkable"
xor False = id
xor True = not
infixr 2 xor
if I didn't make a mistake. It's maybe a little bit more readable.
Btw. How would I rewrite this in applicative style? I came up with something
like
drinkability = undrinkableIf $ xor . honesty
<*> ( (&&) . odorQuale . (perceive $ Odor waterWell)
<*> (&&) . clarityQuale . (perceive $ Clarity waterWell)
<*> fullnessQuale . (perceive $ Fullness waterWell) ) $ volunteer
(not sure it would still compile). However, seems not that readable anymore.
Is it not recommended to use applicative style with binary infix operators? Or
is there a way to make them readable again?
Regards,
Bastian
------------------------------
Message: 2
Date: Tue, 19 Oct 2010 16:10:03 -0400
From: Isaac Dupree <[email protected]>
Subject: Re: [Haskell-beginners] small question
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
On 10/19/10 14:35, Bastian Erdnüß wrote:
> xor False = id
> xor True = not
> infixr 2 xor
Also, exclusive-or on Bool can be written as /= (the first boolean is
not equal to the second boolean), which makes sense to use because /= is
a standard function.
-Isaac
------------------------------
Message: 3
Date: Tue, 19 Oct 2010 22:44:00 +0200
From: Bastian Erdn?? <[email protected]>
Subject: Re: [Haskell-beginners] small question
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=iso-8859-1
On Oct 19, 2010, at 22:10, Isaac Dupree wrote:
> On 10/19/10 14:35, Bastian Erdnüß wrote:
>> xor False = id
>> xor True = not
>> infixr 2 xor
>
> Also, exclusive-or on Bool can be written as /= (the first boolean is not
> equal to the second boolean), which makes sense to use because /= is a
> standard function.
Cool. Never thought of it that way. Then it turns out to be even more easy:
instance OBSERVATIONS Drinkability WaterWell Volunteer where
observe (Drinkability waterWell) volunteer =
volunteer { vReport = drinkability } where
drinkability = drinkableIf $ claimedAppereance == honesty volunteer
claimedAppereance =
odorQuale (perceive (Odor waterWell) volunteer) &&
clarityQuale (perceive (Clarity waterWell) volunteer) &&
fullnessQuale (perceive (Fullness waterWell) volunteer)
drinkableIf True = "drinkable"
drinkableIf False = "undrinkable"
Regards,
Bastian
------------------------------
Message: 4
Date: Wed, 20 Oct 2010 01:23:49 +0200
From: Bastian Erdn?? <[email protected]>
Subject: [Haskell-beginners] pattern match vs. pure function
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Suppose I would want to write a function rmap that acts like
rmap [f,g,h] x == [f x, g x, h x]
Do I gain any advantage or disadvantage (beside readability) from using
rmap = flip $ map . flip id
over
rmap [] _ = []
rmap (f:fs) x = f x : rmap fs x
?
I could imagine Haskell can optimize the first version better since it refers
to the built in map function. But beside that, does Haskell struggle with the
combinatory stuff in the first version? Or does it get optimized away? And
how "expensive" are pattern matches on the other side, anyway?
Thanks for reading,
Bastian
------------------------------
Message: 5
Date: Wed, 20 Oct 2010 02:23:16 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] pattern match vs. pure function
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Wednesday 20 October 2010 01:23:49, Bastian Erdnüß wrote:
> Suppose I would want to write a function rmap that acts like
>
> rmap [f,g,h] x == [f x, g x, h x]
>
> Do I gain any advantage or disadvantage (beside readability) from using
>
> rmap = flip $ map . flip id
>
> over
>
> rmap [] _ = []
> rmap (f:fs) x = f x : rmap fs x
>
> ?
>
> I could imagine Haskell can optimize the first version better since it
> refers to the built in map function. But beside that, does Haskell
> struggle with the combinatory stuff in the first version? Or does it
> get optimized away?
Well, you can ask GHC what it does with the definitions.
Let's compile
module RMap where
rmap :: [a -> b] -> a -> [b]
rmap = flip $ map . flip id
recmap :: [a -> b] -> a -> [b]
recmap [] _ = []
recmap (f:fs) x = f x : recmap fs x
and look at the generated Core (obtained via -ddump-simpl).
The @ x_yz things are type annotations, otherwise Core is pretty close to
Haskell. It takes a bit to get used to reading Core, but it's not that
difficult (as long as the functions are short).
First, without optimisations:
==================== Tidy Core ====================
Rec {
RMap.recmap :: forall a_adg b_adh.
[a_adg -> b_adh] -> a_adg -> [b_adh]
GblId
[Arity 2
NoCafRefs]
RMap.recmap =
\ (@ a_adA)
(@ b_adB)
(ds_dee :: [a_adA -> b_adB])
(ds1_def :: a_adA) ->
case ds_dee of _ {
[] -> GHC.Types.[] @ b_adB;
: f_adk fs_adl ->
GHC.Types.:
@ b_adB
(f_adk ds1_def)
(RMap.recmap @ a_adA @ b_adB fs_adl ds1_def)
}
end Rec }
RMap.rmap :: forall a_adi b_adj.
[a_adi -> b_adj] -> a_adi -> [b_adj]
GblId
[]
RMap.rmap =
\ (@ a_adE) (@ b_adF) ->
GHC.Base.$
@ (a_adE -> [a_adE -> b_adF] -> [b_adF])
@ ([a_adE -> b_adF] -> a_adE -> [b_adF])
(GHC.Base.flip @ a_adE @ [a_adE -> b_adF] @ [b_adF])
(GHC.Base..
@ ((a_adE -> b_adF) -> b_adF)
@ ([a_adE -> b_adF] -> [b_adF])
@ a_adE
(GHC.Base.map @ (a_adE -> b_adF) @ b_adF)
(GHC.Base.flip
@ (a_adE -> b_adF)
@ a_adE
@ b_adF
(GHC.Base.id @ (a_adE -> b_adF))))
-- both are pretty exactly the code written in Haskell.
The explicit recursion recmap is small and efficient, it looks at the list
whether there are still functions left, if so, apply the first of those to
the value and recur. No cruft here.
The other one, flip $ map . flip id is, well it's small too, but it's
horrible to look at (all those @s). Every time you invoke that function,
you call flip twice, ($), map, (.) and id. If you use the function on short
lists, those calls generate significant overhead, but for long lists that
doesn't matter.
Now with optimisations. It doesn't matter whether you use -O1 or -O2, both
produce exactly the same Core for both functions.
And, for recmap, they produce exactly the same Core as -O0 did.
So, recmap is pretty good code, GHC doesn't know how to improve it.
rmap on the other hand changed:
RMap.rmap :: forall a_adi b_adj.
[a_adi -> b_adj] -> a_adi -> [b_adj]
GblId
[Arity 2
NoCafRefs
Str: DmdType SL]
RMap.rmap =
\ (@ a_adE)
(@ b_adF)
(x_aeq :: [a_adE -> b_adF])
(y_aer :: a_adE) ->
GHC.Base.map
@ (a_adE -> b_adF)
@ b_adF
(\ (y1_XeE :: a_adE -> b_adF) -> y1_XeE y_aer)
x_aeq
There, that looks much better than before (and for short lists, it performs
much better, but for long lists, the difference should be negligible).
flip, ($) and (.) have been inlined and eliminated, what we get is
rmap fs x = map (\f -> f x) fs
, which is really nice. In fact, it's even nicer than what we got for
recmap, because the compiler knows map, there are rewrite rules, which can
produce much better code when the function is used, for example, it's
possible that the list of functions is completely eliminated and a use is
rewritten to a direct loop instead of allocating a list cell for each
function in the list. And it can profit from the rule
map f . map g = map (f . g)
which is much harder to detect for the direct recursion.
> And how "expensive" are pattern matches on the other side, anyway?
Depends on the pattern, of course. Matching "oh" against [] is much cheaper
than matching "This is an expensive car" against
'T':'h':'i':'s':' ':'a':'n':' ':'e':'x':'p':'e':'n':'s':'i':'v':'e':'
':'p':'a':'t':'t':'e':'r':'n':' ':'m':'a':'t':'c':'h':_
But generally, pattern matching is quite cheap. The (well, one) advantage
of higher order functions like map is that they're easier to optimise when
they're used, given that somebody has taught the compiler how.
>
> Thanks for reading,
> Bastian
------------------------------
Message: 6
Date: Wed, 20 Oct 2010 09:10:03 +0200
From: Bastian Erdn?? <[email protected]>
Subject: Re: [Haskell-beginners] pattern match vs. pure function
To: Daniel Fischer <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset=iso-8859-1
On Oct 20, 2010, at 2:23, Daniel Fischer wrote:
> On Wednesday 20 October 2010 01:23:49, Bastian Erdnüß wrote:
>> Suppose I would want to write a function rmap that acts like
>>
>> rmap [f,g,h] x == [f x, g x, h x]
>>
>> Do I gain any advantage or disadvantage (beside readability) from using
>>
>> rmap = flip $ map . flip id
>>
>> over
>>
>> rmap [] _ = []
>> rmap (f:fs) x = f x : rmap fs x
>>
>> ?
>>
>> I could imagine Haskell can optimize the first version better since it
>> refers to the built in map function. But beside that, does Haskell
>> struggle with the combinatory stuff in the first version? Or does it
>> get optimized away?
>
> Well, you can ask GHC what it does with the definitions.
> Let's compile
>
> module RMap where
>
> rmap :: [a -> b] -> a -> [b]
> rmap = flip $ map . flip id
>
> recmap :: [a -> b] -> a -> [b]
> recmap [] _ = []
> recmap (f:fs) x = f x : recmap fs x
>
> and look at the generated Core (obtained via -ddump-simpl).
Cool. Didn't know that.
> The @ x_yz things are type annotations, otherwise Core is pretty close to
> Haskell. It takes a bit to get used to reading Core, but it's not that
> difficult (as long as the functions are short).
I see. Well, still better then my hand writing ;-)
> First, without optimisations:
>
> [some good explinations]
Thanks!
> Now with optimisations. [...]
>
> There, that looks much better than before (and for short lists, it performs
> much better, but for long lists, the difference should be negligible).
> flip, ($) and (.) have been inlined and eliminated, what we get is
>
> rmap fs x = map (\f -> f x) fs
>
> , which is really nice. In fact, it's even nicer than what we got for
> recmap, because the compiler knows map, there are rewrite rules, which can
> produce much better code when the function is used, for example, it's
> possible that the list of functions is completely eliminated and a use is
> rewritten to a direct loop instead of allocating a list cell for each
> function in the list. And it can profit from the rule
>
> map f . map g = map (f . g)
>
> which is much harder to detect for the direct recursion.
Good news, seems like Haskell has no problem with combinators. As I hoped I
could expect.
>> And how "expensive" are pattern matches on the other side, anyway?
>
> Depends on the pattern, of course. Matching "oh" against [] is much cheaper
> than matching "This is an expensive car" against
>
> 'T':'h':'i':'s':' ':'a':'n':' ':'e':'x':'p':'e':'n':'s':'i':'v':'e':'
> ':'p':'a':'t':'t':'e':'r':'n':' ':'m':'a':'t':'c':'h':_
>
> But generally, pattern matching is quite cheap. The (well, one) advantage
> of higher order functions like map is that they're easier to optimise when
> they're used, given that somebody has taught the compiler how.
I understand.
Many thanks again for pointing out how I can test such things myself with
-ddump-simple.
Cheers,
Bastian
------------------------------
Message: 7
Date: Wed, 20 Oct 2010 09:14:04 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] pattern match vs. pure function
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=iso-8859-1
On Wed, Oct 20, 2010 at 01:23:49AM +0200, Bastian Erdnüß wrote:
> Suppose I would want to write a function rmap that acts like
>
> rmap [f,g,h] x == [f x, g x, h x]
>
> Do I gain any advantage or disadvantage (beside readability) from using
>
> rmap = flip $ map . flip id
>
> over
>
> rmap [] _ = []
> rmap (f:fs) x = f x : rmap fs x
>
> ?
By the way, I would write rmap as
rmap fs x = map ($x) fs
which is (in my opinion) many times more readable than flip $ map
. flip id. In this case there's no particular advantage to a
points-free definition. But using an existing recursive combinator
(map) is a big win over writing out the recursion explicitly.
> I could imagine Haskell can optimize the first version better since
> it refers to the built in map function. But beside that, does
> Haskell struggle with the combinatory stuff in the first version?
> Or does it get optimized away? And how "expensive" are pattern
> matches on the other side, anyway?
It's a fair question, and Daniel has already given a detailed answer.
But honestly, I don't think this is the sort of thing you should
really be worrying about. Write your programs in the most natural,
elegant way you can think of, and trust that the compiler will try
very hard to turn it into efficient code. If it later turns out to be
too slow and profiling seems to indicate there's room for improvement,
THEN you can start worrying about this sort of thing.
-Brent
------------------------------
Message: 8
Date: Wed, 20 Oct 2010 10:04:41 -0400
From: Patrick LeBoutillier <[email protected]>
Subject: Re: [Haskell-beginners] pattern match vs. pure function
To: Brent Yorgey <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi,
On Wed, Oct 20, 2010 at 9:14 AM, Brent Yorgey <[email protected]> wrote:
> On Wed, Oct 20, 2010 at 01:23:49AM +0200, Bastian Erdnüß wrote:
>> Suppose I would want to write a function rmap that acts like
>>
>> rmap [f,g,h] x == [f x, g x, h x]
>>
>> Do I gain any advantage or disadvantage (beside readability) from using
>>
>> rmap = flip $ map . flip id
>>
A newbie question about this. I can figure out the type of "flip ($)"
and I can work it
from ghci:
Prelude> :t flip
flip :: (a -> b -> c) -> b -> a -> c
Prelude> :t ($)
($) :: (a -> b) -> a -> b
Prelude> :t flip ($)
flip ($) :: b -> (b -> b1) -> b1
but I cannot understand how "flip id" is equivalent:
Prelude> :t flip
flip :: (a -> b -> c) -> b -> a -> c
Prelude> :t id
id :: a -> a
Prelude> :t flip id
flip id :: b -> (b -> c) -> c
How does one get the type of "flip id" by applying "flip" to "id"?
Thanks,
Patrick
>> over
>>
>> rmap [] _ = []
>> rmap (f:fs) x = f x : rmap fs x
>>
>> ?
>
> By the way, I would write rmap as
>
> rmap fs x = map ($x) fs
>
> which is (in my opinion) many times more readable than flip $ map
> . flip id. In this case there's no particular advantage to a
> points-free definition. But using an existing recursive combinator
> (map) is a big win over writing out the recursion explicitly.
>
>> I could imagine Haskell can optimize the first version better since
>> it refers to the built in map function. But beside that, does
>> Haskell struggle with the combinatory stuff in the first version?
>> Or does it get optimized away? And how "expensive" are pattern
>> matches on the other side, anyway?
>
> It's a fair question, and Daniel has already given a detailed answer.
> But honestly, I don't think this is the sort of thing you should
> really be worrying about. Write your programs in the most natural,
> elegant way you can think of, and trust that the compiler will try
> very hard to turn it into efficient code. If it later turns out to be
> too slow and profiling seems to indicate there's room for improvement,
> THEN you can start worrying about this sort of thing.
>
> -Brent
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
--
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 28, Issue 32
*****************************************