Re: [Haskell-cafe] fastest Fibonacci numbers in the West
Am Donnerstag, 27. Januar 2005 06:08 schrieb William Lee Irwin III: >> Inspired by a discussion on freenode #haskell, I tried to write the >> fastest Fibonacci number function possible, i.e. given a natural >> number input n to compute F_n. >> For the moment, mlton-generated binaries crash computing fib (10^8-1), >> and there is a 6:1 speed difference for fib (10^7-1) between the two, >> where mlton-generated binaries take just under 1 minute, and ghc- >> generated binaries take just under 6 minutes. On Thu, Jan 27, 2005 at 03:26:39PM +0100, Daniel Fischer wrote: > Obviously, your machine is significantly faster than mine. > On mine, fib (10^6) takes a little under two minutes, fib (10^7-1) I ^C-ed ~/tmp/fib $(( 10**6 - 1 )) 211.91s user 1.13s system 83% cpu 4:14.96 total In general the printed results and data structures are expected to be in a range where asymptotic behavior dominates. 10^5-1 seems to be the break-even point where more advanced algorithms in Haskell start overtaking naive implementations in lighter-weight runtime systems. This doesn't help much when usefully-advanced languages have sufficiently lightweight runtime systems. I'd almost expect the overhead of printing the result to dominate all this, but somehow it doesn't appear to be the deciding factor, perhaps because they all call gmp to do it. In the range where asymptotic behavior is expected to dominate, the numbers are huge data structures, and having more of them simultaneously live or using more arbitrary-precision temporaries is painful. On Thu, Jan 27, 2005 at 03:26:39PM +0100, Daniel Fischer wrote: > after twenty. > I think ,more readable than > unfoldl f x = case f x of > Nothing -> [] > divs 0 = Nothing > divs k = Just (uncurry (flip (,)) (k `divMod` 2)) > would be > unfoldl f x = case f x of > Nothing -> [] > divs 0 = Nothing > divs k = Just (n `quotRem` 2) > -- this has no influence on performance, since it's optimized anyway. unfoldl was intended to match unfoldr's calling convention verbatim, but produce a list in the reverse order, not really to be easy-to-use in this specific problem. Am Donnerstag, 27. Januar 2005 06:08 schrieb William Lee Irwin III: >> Anyway, thoughts on how to improve all this from the programmer's >> point of view, or otherwise explaining what's going on or ameliorating >> whatever effect is at work here would be appreciated. On Thu, Jan 27, 2005 at 03:26:39PM +0100, Daniel Fischer wrote: > I thought, I'd do it in the ring of integers in Q(sqrt(5)), code attached, > this was a whiff faster for n = 70 on my machine, a whiff slower > for n = 10^6 -- any idea how that may come? I suspect the divide-and-conquer scheme for exponentiation doesn't do bitreversal, which eliminates various redundant computations. -- wli ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] field record update syntax
On Thu, Jan 27, 2005 at 12:59:50PM -0500, S. Alexander Jacobson wrote:
> I have a lot of code of the form
>
> foo {bar = fn $ bar foo}
>
> Is there a more concise syntax? I am thinking
> the record equivalent of C's foo+=5...
>
you can use DrIFT to automatically create
bar_u to update a field and
bar_s to set a field.
They also behave nicer than the built in syntax as they pass through
constructors without the given field rather than return bottom.
John
--
John Meacham - ârepetae.netâjohnâ
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: Answers to Exercises in Craft of FP
Chris, I'm not sure that I understand your argument. How about this scenario, which is what I do: Students are assigned problems, without solutions. They are given some time to work them out and turn them in. Then they are given the solutions, most of which I go over in class. This does not require posting solutions ahead of time, or in a public place, it still allows the "autonomous" student to do the work on his or her own (although constrained by a particular time-frame), and it permits the student to see the solutions in the end. -Paul Christian Hofer wrote: Dear Hamilton, I think we just have a different framing of the problem. You are confronted with the laziness of students and want to teach them something anyway. By that you are forced to disrespect the autonomy of students who are intrinsically motivated (e.g. by giving bonus points on exercises). I on the other hand am a great fan of the old German university system, which they are currently about to abolish in the so-called "Bologna Process". The idea is to just treat students as if they were autonomous. Most students fail in the exams in their first year, because they are not used to solving exercises when nobody forces them to do it (s.th. they should of course already have learned in school). Those students that don't recover don't belong to university. But most students learn from this negative experience, that they have to work on their own. And that is more important to learn on university than the details of a certain programming paradigm... It's nice that you offer me your exercises with solutions. But I am afraid that does not really help me, because I want to do (and am actually doing) the exercises in the books that I read (because that is the way to get a better understanding). Thus what I would need are the solutions to those exercises. Regards, Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Professor Paul Hudak Chair, Dept of Computer Science Office: (203) 432-1235 Yale University FAX:(203) 432-0593 P.O. Box 208285 email: [EMAIL PROTECTED] New Haven, CT 06520-8285 WWW:www.cs.yale.edu/~hudak ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] RE: Answers to Exercises in Craft of FP
This should have been sent to haskell-cafe... Am 27.01.2005 um 21:28 schrieb Paul Hudak: Chris, I'm not sure that I understand your argument. How about this scenario, which is what I do: Students are assigned problems, without solutions. They are given some time to work them out and turn them in. Then they are given the solutions, most of which I go over in class. That is perfectly alright with me. The problem that we are discussing is that it would be helpful to have the solutions to the exercises for a book that I buy for studying on my own. And this is where I learn most from. But most of those books (including the Haskell School of Expression) do not include solutions. In contrast, Pierce's Types and Programming Languages helps the reader by giving at least solutions to the most important exercises. And it is just nice to check, if you have understood the problem correctly and whether there is a more elegant solution. Regards, Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: Answers to Exercises in Craft of FP
Christian Hofer <[EMAIL PROTECTED]> writes: >> That is perfectly alright with me. The problem that we are >> discussing is that it would be helpful to have the solutions to the >> exercises for a book that I buy for studying on my own. How about: 1) Solve the excercises, and publish the solutions yourself. Even if teachers and authors won't be happy about it, they can't really stop you. 2) Use this list. If you have trouble with a particular excercise, post your current effort, and I'm sure people will be able to point you in the right direction. -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] wierd type errros with MPTCs
The kind error seems fair enough. GHC looks at the class decl, and
decides that indexVal is of kind *. Then the instance declaration uses
it with kind (*->*). You may say that it should look at the instance
decl too, before deciding kinds, but the instance decl might be in
another file.
Uncommenting insertIndex allows the compiler to see that indexVal must
be of kind (*->*), since it's applied to item in the type of
insertIndex. So the compiler does do this much lookahead; the class ops
can't be in another module.
In GHC you can say
class Table table (indexVal :: * -> *) where ...
if you like, to make it 100% clear.
When you declare a default method, GHC makes up a definition like this:
$dmunion :: Table table indexVal => table item -> table item ->
table item
$dmunion t1 t2 = t1
("dm" for default method)
Then, in the instance decl, if you don't give a declaration for union,
GHC makes one up, as if you had written
instance Table DBTable IVal where
union = $dmunion
Now you can see where the error arises. The call to $dmunion gives the
constraint (Table DBTable ??) with no way for it to figure out what the
?? is. The type of $dmunion is ambiguous in fact.
Now, I agree that the error message, mentioning $dmunion, is rather
unhelpful. But I can't see an easy way to improve it. Meanwhile, I
hope this helps you make progress.
Simon
| -Original Message-
| From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of S.
| Alexander Jacobson
| Sent: 27 January 2005 17:53
| To: haskell-cafe@haskell.org
| Subject: [Haskell-cafe] wierd type errros with MPTCs
|
| This code gives me a Kind error because IVal isn't
| applied to enough type arguments.
|
|import qualified Set
|
|class Table table indexVal | indexVal->table where
|--insertIndex::item->indexVal item -> table item ->table
item
|union::table item -> table item -> table item
|--union t1 t2 = t1
|
|data DBTable item = DBTable
|data IVal item = Name item
|
|instance Table DBTable (IVal ) where
|
| Weirdly, when I uncomment the insertIndex
| function, things work. But, if I then uncomment
| the default implementation of union, I get:
|
|No instance for (Table DBTable indexVal)
| arising from use of `Main.$dmunion' at example.hs:13
|In the definition of `union': union = Main.$dmunion
|In the definition for method `union'
|In the instance declaration for `Table DBTable IVal'
|
| I don't know what this error even means. But it
| goes away if I put the union implementation in the
| instance rather than in the class.
|
| Bot these error messages seem unreasonable. Can
| someone clarify?
|
| Note: I am using GHC 6.2.2
|
| -Alex-
|
|
| __
| S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com
| ___
| Haskell-Cafe mailing list
| Haskell-Cafe@haskell.org
| http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] mathematical notation and functional programming
Over the past years I became more and more aware that common mathematical notation is full of inaccuracies, abuses and stupidity. I wonder if mathematical notation is subject of a mathematical branch and whether there are papers about this topic, e.g. how one can improve common mathematical notation with the knowledge of functional languages. Things I'm unhappy about are for instance f(x) \in L(\R) where f \in L(\R) is meant F(x) = \int f(x) \dif x where x shouldn't be visible outside the integral O(n) which should be O(\n -> n) (a remark by Simon Thompson in The Craft of Functional Programming) a < b < c which is a short-cut of a < b \land b < c f(.) which means \x -> f x or just f All of these examples expose a common misunderstanding of functions, so I assume that the pioneers of functional programming also must have worried about common mathematical notation. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] File path programme
On Thu, 27 Jan 2005 16:31:21 -0500, robert dockins <[EMAIL PROTECTED]> wrote: > > I don't pretend to fully understand various unicode standard but it > > seems to me that these problems are deeper than file path library. The > > equation (decode . encode) > > /= id seems confusing for me. Can you give me an example when this > > happen? > > I am pretty sure that ISO 2022 encoded strings can have multiple ways to > express the same unicode glyphs. This means that any sensible relation > between IS0 2022 strings and unicode strings maps more than one ISO 2022 > string onto the same unicode string. The inverse is therefore not a > function. To make it a function one of the possibly several encodings > of the unicode string will have to be chosen. So you have a ISO 2022 > string A which is decoded to a unicode string U. We reencode U to an > ISO 2022 string B. It may be that A /= B. That is the problem. > > The various UTF encodings do not have this particular problem; if a UTF > string is valid, then it is a unique representation of a unicode string. > However, decoding is still a partial function and can fail. > > A discussion about this problem floated around on this list several > months ago. > > > What can we do when the file name is passed as command line > > argument to program? We need to convert String to FilePath after all. > > Then we can parse the unicode and hope that nothing bad happens; the > majority of the time, we will be OK. Or we can make the RTS allow > access to the raw bytes of the program arguments, env variables, etc, > and actually do the right thing. This means that all unicode languages, I have used before (Java,C#), are broken too. In this case I agree that special data type might be better. The development of the new FilePath should come together with the new unicode aware I/O library. I agree with David Roundy that the internal representation of FilePath should be compact as mush as posible. PackedString uses UArray Int Char to store strings and we can use UArray Int Word8 or even ByteArray#. Under Windows nearly all API functions have two versions: ANSI and Unicode (16-bit). Under WinNT+ each ANSI function is just a wrapper around its Unicode friend and the wrapper simply converts the passed strings. It was said that paths under Windows are [Word16] while in Posix they are [Word8]. This is true but in order to take advantages of this we need to use the native Windows API in the new I/O library. Another advantage of this is that in such way we can use the native non-blocking I/O under Windows. Cheers, Krasimir ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Typing in haskell and mathematics
Hello,
On Fri, 28 Jan 2005 10:01:33 -0500, Jacques Carette <[EMAIL PROTECTED]> wrote:
> The previous post on record syntax reminded me of some 'problems' I had
> noticed where Haskell and mathematics have a
> (deep) usage mismatch.
It is interesting that my sentiment is exactly the opposite.
Mathematicians (the applied kind, not the pure) tend to be quite
sloppy about their notation relaying _a lot_ on the context and the
fact that people know what they are talking about. I find that this
makes their explanations harder to understand rather than easier.
> First, consider a syntax for other component-wise function application? For
> example, it would be convenient to have
> (f,g) @ (x,y)
> be (f x, g y). In some languages [with dynamic typing], one can even do
> (f,g) (x,y) :-)
I am not sure what you mean, but you can define exactly that (except
for the @ sign which is special syntax already):
(f,g) `ap2` (x,y) = (f x, g y)
> Yes, I am aware that this untypeable in Haskell, because polymorphism is
> straight-jacketed by structural rules.
What do you mean by this:
ap2 :: (a -> b, c - d) -> (a,c) -> (b,d)
But
> in mathematics, it is convenient and extremely common to:
> 1) look at the type a -> b as being a *subtype* of b (though I have never
> seen it phrased that way in print)
I don't think subtyping is what you are thinking of. Perhaps you are referring
to the correspondance between b-expressions with a free a-variable,
and functions a->b. In Haskell we don't have expressions with free
variables as
first class values. There might be some interesting things to work
out for such beasts.
> 2) to consider every 'natural transformation' available and use it (tuples of
> functions <-> obvious function on
> tuples)
Are you suggesting that natural transformations should be applied automatically?
There are many problems with this: which operations should happen
automatically?
Type inference (if it works at all) will be hard to do, but perhaps
these are technical details.
Fundamentally the "sloppy" math notation assumes that what the author
wrote is correct and should simply be given "the obvious" meaning.
This is pretty much the idea with dynamic typing. I find the
restrictions of static typing very convenient (well most of the time
:-) as they capture "stupid' errors.
>
> Seeing a -> b as a subtype of b allows one to take any function f : b -> b ->
> c (like + ) and 'lift' it to
> ff : (a -> b) -> (a -> b) -> (a -> c)
> via the obvious definition
> ff g h = \x -> f (g x) (h x)
> This is done routinely in mathematics. The meaning of the expression (sin +
> cos) should be immediately obvious. Such
> 'lifting' is used even in first-year calculus courses, but not in Haskell.
Apart from the fact that this does not seem like a good idea,
you can already do things like this in Haskell:
liftOp op f g x = f x `op` f x
This is all you need, especially if you are prepared to stick to the
"usual" mathematical convention of not using curried functions, but
instead using tuples to pass multiple arguments.
>
> The "same" phenomenon is what allows one to 'see' that there is an obvious
> function
> apply_tuple:: (a->b,c->d) -> (a,c) -> (b,d)
> so that
> (f,g) (a,b)
> only has one possible meaning, if the built-in apply function were to be
> overloaded.
There are many interesting things one could do if application was to
be overloaded
but this hardly seems like a motivating example. You can already use
the 'ap2' combinator from above. I can see that it is annoying to
have ap2, ap3, etc.
You can define a generic "ap_n" using dependent types, or using the
encoding tomasz posted, but that hardly seems to be a "deep" problem.
>
> Similarly, there are "obvious" maps
> apply_T :: T (a->b) -> a -> T b
> for any datatype constructor T (as has been noticed by all who do 'generic'
> programming).
Is this really true? Consider:
data T a = T (a -> Int)
What shoud apply_T do?
applyT :: (essentially) ((a -> b) -> Int) -> a -> (b -> Int)
perhaps: applyT (T f) a = T (\b -> f (const b))
but that probably does not behave as you would like it.
Of course you could restrict the datatypes for which apply_T can be derived.
This means that
> [f, g, h] x == [f x, g x, h x]
> but also (in mathematics at least)
> {f, g, h} x == {f x, g x, h x}
> where {} denotes a set, and the equality above is extensional equality, and
> so on.
I agree that it would be nice to automatically derive functions such
as apply_T, etc.
This (as you point out) is the idea of generic programming.
This however does not suggest that we should replace application...
> Note that some computer algebra systems use #1 and #2 above all the time to
> define the operational meaning of a lot of
> syntactic constructs [where I personally extended the use of such rules in
> the implementation & operational semantics
> of Maple]. What hope is there to be able to do something 'similar' in a
> Haskell-like language?
I think it is already possible t
[Haskell-cafe] Re: field record update syntax
John Meacham writes: > you can use DrIFT to automatically create > bar_u to update a field and > bar_s to set a field. That is exactly what I need. Is there, by any chance, a solution that's based on Template Haskell too? Not that I'd have something against DrIFT; I'm just curious to know. Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: mathematical notation and functional programming
Henning Thielemann <[EMAIL PROTECTED]> wrote in article <[EMAIL PROTECTED]> in
gmane.comp.lang.haskell.cafe:
> Over the past years I became more and more aware that common mathematical
> notation is full of inaccuracies, abuses and stupidity. I wonder if
> mathematical notation is subject of a mathematical branch and whether
> there are papers about this topic, e.g. how one can improve common
> mathematical notation with the knowledge of functional languages.
I would like to know too!
But I would hesitate with some of your examples, because they may simply
illustrate that mathematical notation is a language with side effects --
see the third and fifth examples below.
> Things I'm unhappy about are for instance
> f(x) \in L(\R)
>where f \in L(\R) is meant
(I'm not sure what you are referring to here -- is there a specific L
that you have in mind?)
> F(x) = \int f(x) \dif x
>where x shouldn't be visible outside the integral
(Not to mention that F(x) is only determined up to a constant.)
> O(n)
>which should be O(\n -> n) (a remark by Simon Thompson in
>The Craft of Functional Programming)
I'm worried about this analysis, because would O(1) mean O(\n -> 1), and
1/O(n^2) mean 1/O(\n -> n^2)? And what about the equal sign in front of
most uses of big-O notation? I would rather analyze this notation as
O = shift k. exists g. g is an asymptotically bounded function
and k(g(n))
where "shift" is Danvy and Filinski's control operator (paired with
"reset"). This way, we can use (as people do)
reset(f(n) = 2^{-O(n)})
to mean that
exists g. g is an asymptotically bounded function
and f(n) = 2^{-g(n)*n}.
Note that the argument to g is not specified in the original notation,
and neither is the reset explicit. But the parentheses in "O(n)" is now
regarded as mere multiplication (making "O-of-n" a mispronunciation).
With some more trickery underlying the equal sign, one can state
meanings such that "O(n) = O(n^2)" is true but "O(n^2) = O(n)" is false.
> a < b < c
>which is a short-cut of a < b \land b < c
What do you think of [a,b,c] for lists?
> f(.)
>which means \x -> f x or just f
I regard this as reset(f(shift k. k)). Besides, even Haskell has (3+).
> All of these examples expose a common misunderstanding of functions, so I
> assume that the pioneers of functional programming also must have worried
> about common mathematical notation.
But AFAIK, nobody ever promised that the mathematical notation used to
talk about functions must denote functions themselves. To take another
example, even though programs are morphisms, we don't always program
in point-free style. And the English word "nobody" does not denote
anybody!
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
War crimes will be prosecuted. War criminals will be punished. And it
will be no defense to say, "I was just following orders."'
George W. Bush, address to the nation, 2003-03-17
http://www.whitehouse.gov/news/releases/2003/03/20030317-7.html
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Typing in haskell and mathematics
On Fri, 28 Jan 2005, Iavor Diatchki wrote: > Hello, > > On Fri, 28 Jan 2005 10:01:33 -0500, Jacques Carette <[EMAIL PROTECTED]> wrote: > > The previous post on record syntax reminded me of some 'problems' I had > > noticed where Haskell and mathematics have a > > (deep) usage mismatch. > It is interesting that my sentiment is exactly the opposite. > Mathematicians (the applied kind, not the pure) tend to be quite > sloppy about their notation relaying _a lot_ on the context and the > fact that people know what they are talking about. I find that this > makes their explanations harder to understand rather than easier. This seems to be related to what I wrote yesterday http://www.haskell.org/pipermail/haskell-cafe/2005-January/008893.html I've collected some examples of abuse and bad mathematical notation: http://www.math.uni-bremen.de/~thielema/Research/notation.pdf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: mathematical notation and functional programming
On Fri, 28 Jan 2005, Chung-chieh Shan wrote:
> Henning Thielemann <[EMAIL PROTECTED]> wrote in article <[EMAIL PROTECTED]>
> in gmane.comp.lang.haskell.cafe:
> > Over the past years I became more and more aware that common mathematical
> > notation is full of inaccuracies, abuses and stupidity. I wonder if
> > mathematical notation is subject of a mathematical branch and whether
> > there are papers about this topic, e.g. how one can improve common
> > mathematical notation with the knowledge of functional languages.
>
> I would like to know too!
>
> But I would hesitate with some of your examples, because they may simply
> illustrate that mathematical notation is a language with side effects --
> see the third and fifth examples below.
I can't imagine mathematics with side effects, because there is no order
of execution.
> > Things I'm unhappy about are for instance
> > f(x) \in L(\R)
> >where f \in L(\R) is meant
>
> (I'm not sure what you are referring to here -- is there a specific L
> that you have in mind?)
Erm yes, my examples are taken from functional analysis. L(\R) means the
space of Lebesgue integrable functions mapping from \R to \R.
> > F(x) = \int f(x) \dif x
> >where x shouldn't be visible outside the integral
>
> (Not to mention that F(x) is only determined up to a constant.)
right, so \int needs a further parameter for the constant
> > O(n)
> >which should be O(\n -> n) (a remark by Simon Thompson in
> >The Craft of Functional Programming)
>
> I'm worried about this analysis, because would O(1) mean O(\n -> 1), and
> 1/O(n^2) mean 1/O(\n -> n^2)?
O(n^2) means O(\n -> n^2), yes.
People say, it is obvious what O(n^2) means. For me it is obvious that
they probably want to pass a constant function in, because O takes a
function as argument and because I know people often don't distinguish
between constant functions and scalar values. Then O(n) = O(n^2) because
O(n) and O(n^2) denote the set of constant functions. :-)
But what do you mean with 1/O(n^2) ? O(f) is defined as the set of
functions bounded to the upper by f. So 1/O(f) has no meaning at the
first glance. I could interpret it as lifting (1/) to (\f x -> 1 / f x)
(i.e. lifting from scalar reciprocal to the reciprocal of a function) and
then as lifting from a reciprocal of a function to the reciprocal of each
function of a set. Do you mean that?
> And what about the equal sign in front of most uses of big-O notation?
This must be an \in and this prevents us from any trouble.
> I would rather analyze this notation as
>
> O = shift k. exists g. g is an asymptotically bounded function
>and k(g(n))
>
> where "shift" is Danvy and Filinski's control operator (paired with
> "reset"). This way, we can use (as people do)
>
> reset(f(n) = 2^{-O(n)})
>
> to mean that
>
> exists g. g is an asymptotically bounded function
> and f(n) = 2^{-g(n)*n}.
I never heard about shift and reset operators, but they don't seem to be
operators in the sense of higher-order functions.
> With some more trickery underlying the equal sign, one can state
> meanings such that "O(n) = O(n^2)" is true but "O(n^2) = O(n)" is false.
Sticking to the set definition of O we would need no tricks at all:
O(\n -> n) \subset O(\n -> n^2)
and
O(\n -> n) /= O(\n -> n^2)
> > a < b < c
> >which is a short-cut of a < b \land b < c
>
> What do you think of [a,b,c] for lists?
I learnt to dislike separators like commas, because
1. (practical reason) it's harder to reorder lists in a editor
2. (theoretical reason) it's inconsistent since there is always one
separator less than list elements, except when the list is empty. In this
case there are 0 separators instead of -1.
So I think (a:b:c:[]) is the better notation.
> > f(.)
> >which means \x -> f x or just f
>
> I regard this as reset(f(shift k. k)). Besides, even Haskell has (3+).
Hm, (3+) is partial application, a re-ordered notation of ((+) 3), which
is only possible if the omitted value is needed only once. But I see
people writing f(.) + f(.-t) and they don't tell, whether this means
(\x -> f x) + (\x -> f (x-t))
or
(\x -> f x + f (x-t))
In this case for most mathematicians this doesn't matter because in the
above case (+) is silently lifted to the addition of functions.
It seems to me that the dot is somehow more variable than variables, and a
dot-containing expression represents a function where the function
arguments are inserted where the dots are.
> > All of these examples expose a common misunderstanding of functions, so I
> > assume that the pioneers of functional programming also must have worried
> > about common mathematical notation.
>
> But AFAIK, nobody ever promised that the mathematical notation used to
> talk about functions must denote functions themselves.
I found that using a notation respecting the functional idea allows very
clear terms. So I used Haskell notatio
[Haskell-cafe] Nice pedagogical examples of type classes?
My Advanced Programming course is quickly approaching the lectures on type classes, and I am interested in finding a little more (beyond what's in SOE) in the way of examples that illustrate nice uses (especially of more advanced aspects of the class system). I'd be most grateful for pointers to people's favorites. Examples should be reasonably small and depend only on Haskell 98 features. I haven't discussed monads yet, but I'm also interested in good monadic examples for later in the semester. Many thanks, - Benjamin P.S. Suggestions for interesting exercises along these lines are also appreciated! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mathematical notation and functional programming
Well, I don't know about modern works which might appeal to knowledge of FP languages, but there is a well-known, 2-volume work by Cajori: Cajori, F., A History of Mathematical Notations, The Open Court Publishing Company, Chicago, 1929 (Available from Dover). I know it through Ken Iverson (may he rest in peace), the creator of APL. (Dr. Iverson's own notations were not to everyone's taste, but I think they were a bigger influence on Backus and the recent wave of FP than is generally acknowledged.) APL *did* have "implicit maps and zipWiths" in the sense that scalar functions would be automatically extended to vectors (and similarly for higher dimensions). I think my PhD advisor, Satish Thatte, did some work on extending this sort of "notational abuse" to Hindley-Milner systems, but I don't have the citations at hand. OK then, googling on Cajori yields this quote from a math history site: "He almost single-handedly created the history of mathematics as an academic subject in the United States and, particularly with his book on the history of mathematical notation, he is still one of the most quoted historians of mathematics today." More googling on "mathematical notation" reveals that there *are* people concerned about these issues, Steven Wolfram being an easily-recognized example (he refers to Cajori's work). -- Fritz On Jan 27, 2005, at 12:14 PM, Henning Thielemann wrote: I wonder if mathematical notation is subject of a mathematical branch and whether there are papers about this topic, e.g. how one can improve common mathematical notation with the knowledge of functional languages. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: mathematical notation and functional programming
On 2005-01-28T20:16:59+0100, Henning Thielemann wrote: > On Fri, 28 Jan 2005, Chung-chieh Shan wrote: > > But I would hesitate with some of your examples, because they may simply > > illustrate that mathematical notation is a language with side effects -- > > see the third and fifth examples below. > I can't imagine mathematics with side effects, because there is no order > of execution. To clarify, I'm not saying that mathematics may have side effects, but that the language we use to talk about mathematics may have side effects, even control effects with delimited continuations. Shift and reset, and other delimited control operators such as control and prompt (which date earlier than shift and reset), are neat. Given that we are talking about language semantics, you may be interested in my paper at http://www.eecs.harvard.edu/~ccshan/cw2004/cw.pdf (which quickly introduces shift and reset). > > > F(x) = \int f(x) \dif x > > >where x shouldn't be visible outside the integral > > (Not to mention that F(x) is only determined up to a constant.) > right, so \int needs a further parameter for the constant Or you can take integration to return a set of functions, and = as \in. That's not actually how I would ultimately analyze things, but it seems to be a start. > People say, it is obvious what O(n^2) means. For me it is obvious that > they probably want to pass a constant function in, because O takes a > function as argument and because I know people often don't distinguish > between constant functions and scalar values. Then O(n) = O(n^2) because > O(n) and O(n^2) denote the set of constant functions. :-) I am interested in "descriptive mathematical notation" rather than "prescriptive mathematical notation" (these are just my terms), in the sense that I want to first ask people what they take certain existing pieces of mathematical notation to mean, then figure out formal rules that underlie these "obvious" interpretations. > But what do you mean with 1/O(n^2) ? O(f) is defined as the set of > functions bounded to the upper by f. So 1/O(f) has no meaning at the > first glance. I could interpret it as lifting (1/) to (\f x -> 1 / f x) > (i.e. lifting from scalar reciprocal to the reciprocal of a function) and > then as lifting from a reciprocal of a function to the reciprocal of each > function of a set. Do you mean that? Wait a minute -- would you also say that "1+x" has no meaning at the first glance, because "x" is a variable whereas "1" is an integer, so some lifting is called for? > I never heard about shift and reset operators, but they don't seem to be > operators in the sense of higher-order functions. Right; they are control operators in the sense that call/cc is a control operator. > > With some more trickery underlying the equal sign, one can state > > meanings such that "O(n) = O(n^2)" is true but "O(n^2) = O(n)" is false. > Sticking to the set definition of O we would need no tricks at all: > O(\n -> n) \subset O(\n -> n^2) > and > O(\n -> n) /= O(\n -> n^2) By "trickery" I meant taking "=" to not denote equality. So for me, taking "=" to denote the subset relation would count as a trick. > > > f(.) > > >which means \x -> f x or just f > > > > I regard this as reset(f(shift k. k)). Besides, even Haskell has (3+). > > Hm, (3+) is partial application, a re-ordered notation of ((+) 3), which > is only possible if the omitted value is needed only once. But I see > people writing f(.) + f(.-t) and they don't tell, whether this means > (\x -> f x) + (\x -> f (x-t)) > or > (\x -> f x + f (x-t)) > In this case for most mathematicians this doesn't matter because in the > above case (+) is silently lifted to the addition of functions. Yes, so in my mind an environment monad is in effect (so to speak) here, and the difference between the two meanings you pointed out is the difference between liftM2 (+) (liftM f ask) (liftM f (liftM2 (-) ask (return t))) and (+) (liftM f ask) (liftM f (liftM2 (-) ask (return t))) (where import Monad and Control.Monad.Reader :). > > But AFAIK, nobody ever promised that the mathematical notation used to > > talk about functions must denote functions themselves. > I found that using a notation respecting the functional idea allows very > clear terms. So I used Haskell notation above to explain, what common > mathematical terms may mean. But Haskell notation does -not- respect the functional idea. First there's the issue of variables: to respect the functional idea we must program in point-free style. Second there's the issue of types: to respect the (set-theoretic) functional idea we must abolish polymorphism and annotate our lambda abstractions in Church style. Surely we don't want the meaning of our mathematical formulas to depend on the semantics of System F(-omega)! Or, as I would prefer, we could design our notation to be both intuitive and formally tractable, without requiring that the concrete syntax of our language direc
Re: [Haskell-cafe] mathematical notation and functional programming
Also, Walter Noll of Carnegie Mellon Univ. wrote a book, "Finite-Dimensional Spaces"in 1987 which basically presented undergraduate math in a notationally and conceptually unified manner. Some of the notation and terminology was strange, but consistent. Mike Matsko - Original Message - From: Fritz Ruehr <[EMAIL PROTECTED]> Date: Friday, January 28, 2005 3:10 pm Subject: Re: [Haskell-cafe] mathematical notation and functional programming > Well, I don't know about modern works which might appeal to > knowledge > of FP languages, but there is a well-known, 2-volume work by Cajori: > > Cajori, F., A History of Mathematical Notations, The Open > Court > Publishing Company, Chicago, 1929 (Available from Dover). > > I know it through Ken Iverson (may he rest in peace), the creator > of > APL. (Dr. Iverson's own notations were not to everyone's taste, but > I > think they were a bigger influence on Backus and the recent wave of > FP > than is generally acknowledged.) > > APL *did* have "implicit maps and zipWiths" in the sense that > scalar > functions would be automatically extended to vectors (and similarly > for > higher dimensions). I think my PhD advisor, Satish Thatte, did some > work on extending this sort of "notational abuse" to Hindley-Milner > systems, but I don't have the citations at hand. > > OK then, googling on Cajori yields this quote from a math history > site: > "He almost single-handedly created the history of mathematics as > an > academic subject in the United States >and, particularly with his book on the history of mathematical > notation, he is still one of the most quoted >historians of mathematics today." > > More googling on "mathematical notation" reveals that there *are* > people concerned about these issues, Steven Wolfram being an > easily-recognized example (he refers to Cajori's work). > > -- Fritz > > On Jan 27, 2005, at 12:14 PM, Henning Thielemann wrote: > > > I wonder if > > mathematical notation is subject of a mathematical branch and > whether> there are papers about this topic, e.g. how one can > improve common > > mathematical notation with the knowledge of functional languages. > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] File path programme
I don't pretend to fully understand various unicode standard but it seems to me that these problems are deeper than file path library. The equation (decode . encode) /= id seems confusing for me. Can you give me an example when this happen? I am pretty sure that ISO 2022 encoded strings can have multiple ways to express the same unicode glyphs. This means that any sensible relation between IS0 2022 strings and unicode strings maps more than one ISO 2022 string onto the same unicode string. The inverse is therefore not a function. To make it a function one of the possibly several encodings of the unicode string will have to be chosen. So you have a ISO 2022 string A which is decoded to a unicode string U. We reencode U to an ISO 2022 string B. It may be that A /= B. That is the problem. The various UTF encodings do not have this particular problem; if a UTF string is valid, then it is a unique representation of a unicode string. However, decoding is still a partial function and can fail. A discussion about this problem floated around on this list several months ago. > What can we do when the file name is passed as command line > argument to program? We need to convert String to FilePath after all. Then we can parse the unicode and hope that nothing bad happens; the majority of the time, we will be OK. Or we can make the RTS allow access to the raw bytes of the program arguments, env variables, etc, and actually do the right thing. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: mathematical notation and functional programming
Chung-chieh Shan <[EMAIL PROTECTED]> writes: >> O(n) >>which should be O(\n -> n) (a remark by Simon Thompson in >>The Craft of Functional Programming) It's a neat thought, IMHO. I usually try to quantify the variables used, making the equivalent of 'let n = .. in O(n)' > And what about the equal sign in front of most uses of big-O notation? This is a peeve of mine; I've always preferred to view O(n) etc. as sets of functions, so that a particular function can be a *member* of this set. Otherwise, you could have: f=O(n) /\ g=O(n) => f=g :-) > With some more trickery underlying the equal sign, one can state > meanings such that "O(n) = O(n^2)" is true but "O(n^2) = O(n)" is false. I would rather say that O(n) is a subset of O(n^2). >> a < b < c >>which is a short-cut of a < b \land b < c What's the problem with this one? -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mathematical notation and functional programming
> Things I'm unhappy about are for instance > > f(x) \in L(\R) >where f \in L(\R) is meant > > F(x) = \int f(x) \dif x >where x shouldn't be visible outside the integral > > O(n) >which should be O(\n -> n) (a remark by Simon Thompson in >The Craft of Functional Programming) > f(.) >which means \x -> f x or just f All of these are the same notation abuse, "sometimes f x is meant to be interpreted as \x->f x" In some cases it would be really tedious to add the extra lambdas, so the expression used in its definition is used to denote the function itself. > a < b < c >which is a short-cut of a < b \land b < c Both, ambiguity and complex notation, can lead to (human) parsing problems, which is what we are trying to minimise here. J.A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: mathematical notation and functional programming
On Fri, Jan 28, 2005 at 08:16:59PM +0100, Henning Thielemann wrote: > But what do you mean with 1/O(n^2) ? O(f) is defined as the set of > functions bounded to the upper by f. So 1/O(f) has no meaning at the > first glance. I could interpret it as lifting (1/) to (\f x -> 1 / f x) > (i.e. lifting from scalar reciprocal to the reciprocal of a function) and > then as lifting from a reciprocal of a function to the reciprocal of each > function of a set. Do you mean that? My first guess is Omega(1/n^2). -- wli ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Typing in haskell and mathematics
[I have now subscribed to haskell-cafe]
Henning Thielemann <[EMAIL PROTECTED]> wrote:
This seems to be related to what I wrote yesterday
http://www.haskell.org/pipermail/haskell-cafe/2005-January/008893.html
Yes, very much. Except that rather than trying to tell mathematicians that they are *wrong*, I am trying to see which
of their notations I can explain (in a typed way). There will be some 'leftovers', where the notation is simply bad.
I've collected some examples of abuse and bad mathematical notation:
http://www.math.uni-bremen.de/~thielema/Research/notation.pdf
Some of what you point out there is bad notation. Other bits point to some
misunderstanding of the issues.
Starting from your original post:
f(x) \in L(\R)
where f \in L(\R) is meant
F(x) = \int f(x) \dif x
where x shouldn't be visible outside the integral
First, mathematicians like to write f(x) to indicate clearly that they are denoting a function. This is equivalent to
writing down (f \in -> ) with domain/range omitted.
Second, every mathematician knows that \int f(x) \dif x == \int f(y) \dif y (ie alpha conversion), so that combined
with the previous convention, there is no confusion in writing F(x) = \int f(x) \dif x. It is just as well-defined as
(\x.x x) (\x.x x)
which requires alpha-conversion too for proper understanding.
You also write
O(n)
which should be O(\n -> n) (a remark by Simon Thompson in
The Craft of Functional Programming)
but the only reason for this is that computer scientists don't like open terms. Since the argument to O must be a
univariate function with range the Reals, then whatever is written there must *denote* such a function. The term
``n'' can only denote only one such function, \n -> n. So the mathematician's notation is in fact much more pleasing.
However, you have to remember one crucial fact: a set of typographical symbols are meant to *denote* a value, they are
not values in themselves. So there is always a function around which is the ``denotes'' function that is implicitly
applied. Russell's work in the early 1900, "sense and denotation" are worth reading if you want to learn more about
this.
What is definitely confusing is the use of = with O notation. The denotation there is much more complex - and borders
on incorrect.
a < b < c
which is a short-cut of a < b \land b < c
That is plain confusion between the concepts of ``denotation'' and ``value''. Where < is a denotation of a binary
function from bool x bool -> bool, _ < _ < _ is a mixfix denotation of a constraint, which could be denoted in a
long-winded fashion by
p a b c = a
but more accurately by
p a c = \b -> b \in )a,c(
where I am using mathematical notation for the body above.
On your ``notation.pdf'' (link above), you have some other mis-interpretations. On p.10 you seem to think that
Mathematica is a lazy language, when it is in fact an eager language. So your interpretation does not ``make sense''.
Not that your observation is incorrect. In Maple, there are two functions, eval(expr, x=pt) and subs(x=pt, expr)
which do ``similar'' things. But subs is pure textual substitution (ie the CS thing), whereas 2-argument eval means
"evaluate the function that \x -> expr denotes at the point pt" (ie the math thing). The interesting thing is that
"the function that \x -> expr denotes" is allowed to remove (removeable) singularities in its ``denotation'' map.
However,
subs(x=2,'diff'(ln(x),x)) ;
diff(ln(2),2)
where the '' quotes mean to delay evaluation of the underlying function. On
the other hand
eval('diff'(ln(x),x),x=2) ;
eval('diff'(ln(x),x),x=2)
because it makes no sense to evaluate an open term which introduces a
(temporary) binding for one of its variables.
Note that without access to terms, it is not possible to write a function like diff (or derive as you phrase it, or D
as Mathematica calls it). Mathematician's diff looks like it is has signature diff: function -> function, but it in
fact is treated more often as having signature diff: function_denotation -> function_denotation. But you can see a
post by Oleg in December on the haskell list how it is possible (with type classes) in Haskell to automatically pair
up function and function_denotation.
You also seem to assume that set theory is the only axiomatization of mathematics that counts (on p.31). I do not see
functions A -> B as somehow being subsets of powerset(A x B). That to me is one possible 'implementation' of
functions. This identification is just as faulty as the one you point out on p.14 of the naturals not ``really''
being a subset of the rationals. In both cases, there is a natural embedding taking place, but it is not the
identity.
You also have the signature of a number of functions not-quite-right. ``indefinite'' integration does not map
functions to functions, but functions to equivalence classes of functions. Fourier transforms (and other integral
transfo
Re: [Haskell-cafe] Re: field record update syntax
On Fri, Jan 28, 2005 at 02:36:59PM +0100, Peter Simons wrote: > > you can use DrIFT to automatically create > > bar_u to update a field and > > bar_s to set a field. > > That is exactly what I need. Is there, by any chance, a > solution that's based on Template Haskell too? Not that I'd > have something against DrIFT; I'm just curious to know. A project I thought would be neat is to create a common framework so the same deriving rules could work with DrIFT or template haskell. It shouldn't be too tough. you couldn't use the template haskell special syntax though. John -- John Meacham - ârepetae.netâjohnâ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mathematical notation and functional programming
At 9:14 PM +0100 2005/1/27, Henning Thielemann wrote: Over the past years I became more and more aware that common mathematical notation is full of inaccuracies, abuses and stupidity. I wonder if mathematical notation is subject of a mathematical branch and whether there are papers about this topic, e.g. how one can improve common mathematical notation with the knowledge of functional languages. Your distaste for common mathematical notation was shared by Edsger W. Dijkstra. For a sampling of his writings on the subject, visit http://www.cs.utexas.edu/users/EWD/welcome.html and search the transcriptions for "notation". Or use the Advanced Search" facility to pick up other forms such as "notations" and "notational". Things I'm unhappy about are for instance f(x) \in L(\R) where f \in L(\R) is meant F(x) = \int f(x) \dif x where x shouldn't be visible outside the integral O(n) which should be O(\n -> n) (a remark by Simon Thompson in The Craft of Functional Programming) I use lambda notation extensively in the part of my discrete math course that deals with complexity. Works fine. Moreover --anticipating a reply further down the list-- my students learn that O(f) for some function f denotes a set of functions, so that f = O(g), where f and g are functions of the same type, is simply a type error. I seem to recall that Donald Knuth made this point a few decades ago, but old habits die hard. a < b < c which is a short-cut of a < b \land b < c This problem has worse consequences when the operator is (=). By common convention, a = b = c is shorthand for a = b /\ b = c which is a great mistake because it obscures the extremely valuable (for equational reasoning) fact that when a, b, and c are Boolean, (=) is associative. In their textbook, _A Logical Approach to Discrete Math_, Gries and Schneider explain that (=) is conjunctional, and that an operator can't be both conjunctional and associative. Following Dijkstra, they introduce another operator, the equivalence (=) (that should display as a three-bar equality operator). It's defined only for Boolean operands, and it's not conjunctional but associative. f(.) which means \x -> f x or just f All of these examples expose a common misunderstanding of functions, so I assume that the pioneers of functional programming also must have worried about common mathematical notation. As did Dijkstra, who devoted the last part of his career to "the streamlining of mathematical argument". Regards, --Ham ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
