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: Type classes and synonyms (Brent Yorgey)
2. Re: Type classes and synonyms (Brandon S. Allbery KF8NH)
3. Re: Type classes and synonyms (pbrowne)
4. Show how the evaluation works (John Moore)
5. Re: Show how the evaluation works (Stephen Tetley)
6. Re: Show how the evaluation works (Daniel Fischer)
7. Re: Type classes and synonyms (Isaac Dupree)
8. Re: Type classes and synonyms (Brent Yorgey)
----------------------------------------------------------------------
Message: 1
Date: Sun, 22 Nov 2009 10:42:38 -0500
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
On Sun, Nov 22, 2009 at 03:32:07PM +0000, pbrowne wrote:
>
> On Sat, Nov 21, 2009 at 21:08 Felipe Lessa wrote:
> > Most definitions, if not all, are just the corresponding free theorems
> > (meaning roughly that the definition follows from the type
> > because that's the only definition that doesn't have
> > undefined's).
>
> Question: Is it correct to paraphrase Felipe's description as follows:
> In Haskell the *term theorems for free* means roughly that the
> definition of a class, instance or a function follows from the supplied
> types because they are the only types that donât have undefined argumens
> or undefined return types.
That is a good way to paraphrase Felipe's description --- but I don't
think Felipe's terminology is correct. Many types do indeed have only
a small number, or even only one, possible "interesting" implementation
that does not involve undefined anywhere. However, this is not what
is meant by "free theorems". A "free theorem" is a *property* which
is satisfied by any function with a particular type. For example, any
function with the type
foo :: [a] -> Maybe a
necessarily satisfies
foo (map f xs) = fmap f (foo xs)
(or, in points-free form,
foo . map f = fmap f . foo )
for any list xs and function f, no matter what the implementation of
foo (as long as it does not involve undefined or unsafePerformIO or
any "cheating" of that sort).
-Brent
------------------------------
Message: 2
Date: Sun, 22 Nov 2009 10:45:04 -0500
From: "Brandon S. Allbery KF8NH" <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: pbrowne <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="windows-1252"
On Nov 22, 2009, at 10:32 , pbrowne wrote:
> On Sat, Nov 21, 2009 at 21:08 Felipe Lessa wrote:
>> Most definitions, if not all, are just the corresponding free
>> theorems
>> (meaning roughly that the definition follows from the type
>> because that's the only definition that doesn't have
>> undefined's).
>
> Question: Is it correct to paraphrase Felipe's description as follows:
> In Haskell the *term theorems for free* means roughly that the
> definition of a class, instance or a function follows from the
> supplied
> types because they are the only types that dont have undefined
> argumens
> or undefined return types.
Pretty much. It's not specific to Haskell, either; it's a result of
the Curry-Howard correspondence between programs and mathematical
proofs.
http://homepages.inf.ed.ac.uk/wadler/papers/free/free.ps is the
canonical paper on deriving free theorems from Hindley-Milner type
systems.
--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [email protected]
system administrator [openafs,heimdal,too many hats] [email protected]
electrical and computer engineering, carnegie mellon university KF8NH
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 195 bytes
Desc: This is a digitally signed message part
Url :
http://www.haskell.org/pipermail/beginners/attachments/20091122/3964ba3f/PGP-0001.bin
------------------------------
Message: 3
Date: Sun, 22 Nov 2009 16:12:29 +0000
From: pbrowne <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: Brent Yorgey <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
On Sun, Nov 22, 2009 at 03:32:07PM +0000, Brent Yorgey wrote:
> A "free theorem" is a *property* which
> is satisfied by any function with a particular type. For example, any
> function with the type
>
> foo :: [a] -> Maybe a
>
> necessarily satisfies
>
> foo (map f xs) = fmap f (foo xs)
A theorem is a statement which has been proved on the basis of
previously established theorems or axiom. So, should the definition of
the function not satisfy the signature? I may be confusing terminology
here. I am coming of an OBJ2/Maude/CafeOBJ background to Haskell. In
CafeOBJ a *property* of an operation could, for example, be
associativity. I am having difficulty in adjusting to Haskells level of
formality.
>> In Haskell the *theorems for free* means roughly that the
>> definition of a class, instance or a function follows from the supplied
>> types because they are the only types that donât have undefined argumens
>> or undefined return types.
Question: Is my generalization of applying the "free theorem" concept to
classes and instances correct?
Pat
------------------------------
Message: 4
Date: Sun, 22 Nov 2009 16:17:46 +0000
From: John Moore <[email protected]>
Subject: [Haskell-beginners] Show how the evaluation works
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Hi All,
I'm trying to work out how to show the steps in evaluating "How the function
is calculated". In other words I want this program to actually print out the
steps. For e.g. eval (Multiply(Add(Val 10) (Val 20)) (Val 3) Which is add
10+20 and multiply by 3 = 90
The program then produces( Prints out) something like
working: eval (Multiply(Add(Val 10) (Val 20)) (Val 3)
working Add(Val10) (Val 20)
answer 1 Val 30
answer 2 Val 90
This is what I have so far but it wont even do the calculations. Any help
appreciated.
data Expression = Val Float
| Add Expression Expression
| Subtract Expression Expression
| Multiply Expression Expression
| Divide Expression Expression
deriving Show
eval :: Expression -> Float
eval (Val x) = x
eval (Add x y) = eval x + eval y
eval (Multiply x y) = eval x * eval y
eval (Subtract x y) = eval x - eval y
eval (Divide x y) = eval x / eval y
John
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20091122/5ede682c/attachment-0001.html
------------------------------
Message: 5
Date: Sun, 22 Nov 2009 16:45:07 +0000
From: Stephen Tetley <[email protected]>
Subject: Re: [Haskell-beginners] Show how the evaluation works
To: John Moore <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi John
You need some more /machinery/ in your evaluator.
One possibility is to make it a monadic evaluator - you could then
choose to use IO and print things as you go, or a writer monad which
'collects' (think logging) as evaluation progresses. The at the end
you'd show both the log and the answer.
The writer monad has a run function, which you would need to run the
extended evaluator with
runWriter :: Writer w a -> (a, w)
The result of runWriter is a pair of a (the answer) and w (the log).
Writer is more general than just logging, but in this instance logging
is close to what you might want.
Best wishes
Stephen
2009/11/22 John Moore <[email protected]>:
> Hi All,
>
> I'm trying to work out how to show the steps in evaluating "How the function
> is calculated". In other words I want this program to actually print out the
> steps. For e.g. eval (Multiply(Add(Val 10) (Val 20)) (Val 3) Which is add
> 10+20 and multiply by 3 = 90
>
> The program then produces( Prints out) something like
>
> working: eval (Multiply(Add(Val 10) (Val 20)) (Val 3)
> working Add(Val10) (Val 20)
> answer 1 Val 30
> answer 2 Val 90
>
> This is what I have so far but it wont even do the calculations. Any help
> appreciated.
>
> data Expression = Val Float
> | Add Expression Expression
> | Subtract Expression Expression
> | Multiply Expression Expression
> | Divide Expression Expression
> deriving Show
> eval :: Expression -> Float
> eval (Val x) = x
> eval (Add x y) = eval x + eval y
> eval (Multiply x y) = eval x * eval y
> eval (Subtract x y) = eval x - eval y
> eval (Divide x y) = eval x / eval y
>
>
>
> John
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
------------------------------
Message: 6
Date: Sun, 22 Nov 2009 17:54:16 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Show how the evaluation works
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-15"
Am Sonntag 22 November 2009 17:17:46 schrieb John Moore:
> Hi All,
>
> I'm trying to work out how to show the steps in evaluating "How the
> function is calculated". In other words I want this program to actually
> print out the steps. For e.g. eval (Multiply(Add(Val 10) (Val 20)) (Val 3)
> Which is add 10+20 and multiply by 3 = 90
>
> The program then produces( Prints out) something like
>
> working: eval (Multiply(Add(Val 10) (Val 20)) (Val 3)
> working Add(Val10) (Val 20)
> answer 1 Val 30
> answer 2 Val 90
>
> This is what I have so far but it wont even do the calculations. Any help
> appreciated.
>
> data Expression = Val Float
>
> | Add Expression Expression
> | Subtract Expression Expression
> | Multiply Expression Expression
> | Divide Expression Expression
>
> deriving Show
> eval :: Expression -> Float
> eval (Val x) = x
> eval (Add x y) = eval x + eval y
> eval (Multiply x y) = eval x * eval y
> eval (Subtract x y) = eval x - eval y
> eval (Divide x y) = eval x / eval y
If you want to have the evaluation steps printed, you must do it in IO (after
all, your
programme will be performing IO)
evalIO :: Expression -> IO Float
evalIO (Val x) = do
putStrLn $ "Plain value " ++ show x
return x
evalIO (Add x y) = do
vx <- evalIO x
vy <- evalIO y
putStrLn $ "Add " ++ show vx ++ " and " ++ show vy
return (vx+vy)
...
You can chose other formatting, maybe display the entire expression before
evaluating the
subexpressions, indent evaluation printout of subexpressions (needs an Int
parameter
counting how many levels below the top you are for indentation), ...
One thing is that by putting it in IO, *you* specify the evaluation order.
By itself, faced with
eval (Add x y) = eval x + eval y
the system may evaluate either subexpression first.
You can give the system that freedom back by using Debug.Trace instead of IO,
but then
there is a nonzero probability that the output of different evaluations becomes
entangled
(it may evaluate part of x first, then some part of y, more of x,...).
>
>
>
> John
------------------------------
Message: 7
Date: Sun, 22 Nov 2009 12:14:30 -0500
From: Isaac Dupree <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Stephen Tetley wrote:
> 2009/11/22 Isaac Dupree <[email protected]>:
>> Sorry to take offense :-) maybe I was being too modest?
>>
>> It seems Arrows are a necessary abstraction for a couple very particular
>> world-views/paradigms, and don't fit very well with a lot of other stuff.
>>
>
>
>
> Hello All
>
> I wouldn't go quite as far as saying Arrows are misfits, but in
> Isaac's defence, if all you have are pure functions, then arrows are
> just a wee bit, erm, boring.
:-)
there are a few combinators in Arrow that would be nice to have for
functions, without even that Arrow generalization, as people have noted
now and then. I used to use them sometimes, but then I decided that it
was a bit too confusing to the reader to involve a type-class (Arrow)
that wasn't very relevant (and not ubiquitously well-known), even if a
version with explicit lambdas is a bit longer.
------------------------------
Message: 8
Date: Sun, 22 Nov 2009 12:25:36 -0500
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
On Sun, Nov 22, 2009 at 04:12:29PM +0000, pbrowne wrote:
> On Sun, Nov 22, 2009 at 03:32:07PM +0000, Brent Yorgey wrote:
> > A "free theorem" is a *property* which
> > is satisfied by any function with a particular type. For example, any
> > function with the type
> >
> > foo :: [a] -> Maybe a
> >
> > necessarily satisfies
> >
> > foo (map f xs) = fmap f (foo xs)
>
>
> A theorem is a statement which has been proved on the basis of
> previously established theorems or axiom. So, should the definition of
> the function not satisfy the signature? I may be confusing terminology
> here. I am coming of an OBJ2/Maude/CafeOBJ background to Haskell. In
> CafeOBJ a *property* of an operation could, for example, be
> associativity. I am having difficulty in adjusting to Haskells level of
> formality.
I'm not quite sure what you're asking here. My point is just that a
"free theorem" will be of the form
"Any function f of type T, *no matter how f is implemented*, will
always satisfy the following property:
blah blah f blah = blah f blah
"
This has nothing to do with whether or not there is only one possible
implementation of f that does not involve undefined, which is a
different phenomenon.
>
> >> In Haskell the *theorems for free* means roughly that the
> >> definition of a class, instance or a function follows from the supplied
> >> types because they are the only types that donât have undefined argumens
> >> or undefined return types.
>
> Question: Is my generalization of applying the "free theorem" concept to
> classes and instances correct?
Classes don't have types, so I'm not sure what you mean by including
classes. Generalizing to instances makes sense; type class instances
are just composed of a list of functions. However, again, this notion
of there sometimes being only one possible implementation of a
particular type has nothing to do with the concept of "free
theorems". (At least, it has not much to do with it that I am aware
of.)
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 17, Issue 24
*****************************************
