Function composition and currying
Hi, Hopefully this is a simple question. I am wanting to know good ways of using ".", the function composition operator, when dealing with currying functions. Suppose I have the following functions defined: f :: Int -> Int f x = x*x g :: Int -> Int -> Int g a b = a + b If I wish to add 1 and 2 together and then square them I can do: f (g 1 2) = 9 but what if I wish to use function composition in the process? I can't do (f.g) 1 2 because the 2 doesn't get passed in till too late. I could do (f.(g 1)) 2 or even (f.(uncurry g)) (1,2) But what I really want is a function with signature Int -> Int -> Int. The answer is probably: (curry (f.(uncurry g))) 1 2 but this seems awfully messy just to do f (g 1 2). And what if g were a function with three curried arguments? Then uncurry and curry wouldn't apply. What then? Is there a better way? Thanks, Mark. -- Dr Mark H Phillips Research Analyst (Mathematician) AUSTRICS - smarter scheduling solutions - www.austrics.com Level 2, 50 Pirie Street, Adelaide SA 5000, Australia Phone +61 8 8226 9850 Fax +61 8 8231 4821 Email mark@austrics.com.au
I think the cutest way to get what you want here is to define a new operator as follows: (.<) = (.) . (.) (the choice of symbol is supposed to suggest this new form of composition with "two prongs" on the right). Then you can use it as follows, for example: f x = x * x g a b = a + b y = (f .< g) 1 2 I noticed this one day while playing around with a definition like the one you gave, in terms of curry and uncurry, trying to express it in a more points-free style. But Jerzy Karczmarczuk enlightened me as to the full generality possible along these lines (revealing the whole truth under the influence of at least one beer, as I recall). Namely, one can define a sequence of functions (let's use a better notation now, with "c" for composition): c1 = (.) -- good old composition c2 = (.) . (.) -- my (.<) from above c3 = (.) . (.) . (.) c4 = (.) . (.) . (.) . (.) -- etc. Each of these gives an appropriate generalization allowing the composition of a one-argument function with an n-argument one (similar to the notations used in the usual definitions for primitive recursive function). That is to say, the types are as follows (the middle three dots on the second line are an ellipsis, apologies in advance): cn :: (a -> b) -> F(t,n,a) -> F(t,n,b) cn = (.) . ... . (.) -- n occurrences of (.) where the awkward phrase "F(t,n,x)" expands as follows via some imagined macro facility. F(t,n,x) === t1 -> t2 -> ... -> tn -> x (I use a Phi operator, a la type- theoretic Sigma or Pi, when I write these things out in the privacy of my own home.) By the way, there is in general a real need to be able to abstract over these n's, e.g. for zip and relatives as well. I tried unsuccessfully to do this for my dissertation, Mark Tullsen did a much better job in his, and various other people have explored other ways (I imagine that Conor McBride could show us how the use of full dependent types would solve the problem once and for all, perhaps in his Epigram language). Of course, what we really want to do is to express this as a fold of composition over a dynamically generated list of compositions, i.e.: c n = foldr (.) id (take n (repeat (.))) But I think giving this a nice general type, where n is a run-time argument and the replicated (.)s have distinct but related types, is quite difficult. -- Fritz Ruehr
Hi,
Hopefully this is a simple question. I am wanting to know good ways of using ".", the function composition operator, when dealing with currying functions.
Suppose I have the following functions defined:
f :: Int -> Int f x = x*x
g :: Int -> Int -> Int g a b = a + b
...
But what I really want is a function with signature Int -> Int -> Int. The answer is probably:
(curry (f.(uncurry g))) 1 2
but this seems awfully messy just to do f (g 1 2).
And what if g were a function with three curried arguments? Then uncurry and curry wouldn't apply. What then?
Is there a better way?
Thanks,
Mark.
-- Dr Mark H Phillips Research Analyst (Mathematician)
AUSTRICS - smarter scheduling solutions - www.austrics.com
Level 2, 50 Pirie Street, Adelaide SA 5000, Australia Phone +61 8 8226 9850 Fax +61 8 8231 4821 Email mark@austrics.com.au
K. Fritz Ruehr writes: : | But Jerzy Karczmarczuk enlightened me as to the full generality possible | along these lines (revealing the whole truth under the influence of at | least one beer, as I recall). Namely, one can define a sequence of | functions (let's use a better notation now, with "c" for composition): | | c1 = (.) -- good old composition | | c2 = (.) . (.) -- my (.<) from above | | c3 = (.) . (.) . (.) | | c4 = (.) . (.) . (.) . (.) | | -- etc. Nice! There's also c0 = ($) which is clearer if you use 'non-pointfree' notation ... c2 f g x y = f (g x y) c1 f g x = f (g x) c0 f g = f g - Tom
Tom Pledger wrote:
K. Fritz Ruehr writes: : | But Jerzy Karczmarczuk enlightened me as to the full generality possible | along these lines (revealing the whole truth under the influence of at | least one beer, as I recall). Namely, one can define a sequence of | functions (let's use a better notation now, with "c" for composition): | | c1 = (.) -- good old composition | c2 = (.) . (.) -- my (.<) from above | c3 = (.) . (.) . (.) | c4 = (.) . (.) . (.) . (.) | -- etc.
Nice!
There's also
c0 = ($)
which is clearer if you use 'non-pointfree' notation
... c2 f g x y = f (g x y) c1 f g x = f (g x) c0 f g = f g
- Tom
Note also that chains of these operators can be used in a somewhat readable way. For example, suppose we have: f1 :: Int -> Int f2 :: Int -> Int -> Int f3 :: Int -> Int -> Int -> Int f :: Int -> Int -> Int -> Int -> Int f1 x = -x f2 x y = x - y f3 x y z = x * (y - z) f a b c d = f2 (f1 (f3 a b c)) d We can define `f` in a point-free style: f = f2 `c1` f1 `c3` f3 Each function in the composition, from innermost (rightmost) to outermost (leftmost), takes the intermediate result so far (or, for the innermost function, the first argument) plus zero or more additional arguments from those that remain, as determined by the composition operator to its left. Note that the composition operators need to be left-associative (as they are by default) for this to work. -- Dean
On Wed, 16 Jul 2003, K. Fritz Ruehr wrote:
I think the cutest way to get what you want here is to define a new ^^^^^^ operator as follows:
(.<) = (.) . (.)
Indeed this is cute - but let me add a general comment here: in my code, I don't define any operators at all (only functions). I do think that self-defined operators make a programm less readable. All you get is a short cryptic sequence of non-alphanumeric characters. No-one would want to export functions named f, g, f1, fg, f' etc., so why should this be any better with operators? A similar discussion sometimes surfaces in mathematics - where they have "user-defined" operators all over the place, and especially so since LaTeX. But it's not enough if you can write down something, you also have to talk about it - so a standard test is to imagine you have to read out a formula (in mathematics) or a program text (in Haskell) to someone over the phone. And what's absolutely horrible (IMHO) is to allow the user to declare arbitrary precedence and associativity for his creations. This requires that the source text of the defining module be there, only to parse (i. e., build the syntax tree of) a program that uses it. And - the corresponding definitions in the standard seem rather ad-hoc: we have a funny expression grammar http://haskell.org/onlinereport/exps.html, with arbitrary restrictions (why just ten precendence levels?) I could live with Haskell's predefined operators (arithmetics, comparisons, bool-ops, (:), (++), (!), (!!), (.), ($)). I often use them, and I sometimes overload them (arithmetics, comparisons), but nothing more. (This is the design of Ada - there are operators, you can overload them, but you cannot change their precedence, or add new ones - so you can always parse a program text.) Anyway, this was just for the record (I'm a happy Haskell user, I just ignore some of its features :-), so back to real work now. -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/209 --
On Thursday, 2003-07-17, 09:08, CEST, Johannes Waldmann wrote:
[...]
in my code, I don't define any operators at all (only functions). I do think that self-defined operators make a programm less readable. All you get is a A short cryptic sequence of non-alphanumeric characters.
I think, that in some situations using operators makes a program more readable. For instance, if we wouldn't have special list syntax, we could still write something like 1 : 2 : 3 : 4 : []. Without operators we would get 1 `cons` 2 `cons` 3 `cons` 4 `cons` [] (uhh, much harder to type) or even cons 1 $ cons 2 $ cons 3 $ cons 4 $ [] or cons 1 (cons 2 (cons 3 (cons 4 []))) which doesn't look much like [1,2,3,4]. I think that similar situations exist with user-defined functions/operators.
No-one would want to export functions named f, g, f1, fg, f' etc., so why should this be any better with operators?
Ok, that's a point I never thought of.
A similar discussion sometimes surfaces in mathematics - where they have "user-defined" operators all over the place, and especially so since LaTeX.
Well, for the most part, LaTeX only provides common operators. One problem, I came across some weeks ago, is that it is *not* possible to define his/her own operators (or, at least, that Lamport's "LaTeX - A Document Preparation System" doesn't tell you how you can define them).
But it's not enough if you can write down something, you also have to talk about it - so a standard test is to imagine you have to read out a formula (in mathematics) or a program text (in Haskell) to someone over the phone.
Yes, this is a problem. But it can be solved by assigning a "pronounciation" to an operator like it's done in standard mathematics.
And what's absolutely horrible (IMHO) is to allow the user to declare arbitrary precedence and associativity for his creations. This requires that the source text of the defining module be there, only to parse (i. e., build the syntax tree of) a program that uses it.
Maybe the infix declarations should have to be separated from the rest of the code?
And - the corresponding definitions in the standard seem rather ad-hoc: we have a funny expression grammar http://haskell.org/onlinereport/exps.html, with arbitrary restrictions (why just ten precendence levels?)
Yes, something more sophisticated would be nice.
I could live with Haskell's predefined operators (arithmetics, comparisons, bool-ops, (:), (++), (!), (!!), (.), ($)). I often use them, and I sometimes overload them (arithmetics, comparisons), but nothing more. (This is the design of Ada - there are operators, you can overload them, but you cannot change their precedence, or add new ones - so you can always parse a program text.)
I dislike, having a fixed set of operators with each having a fixed precedence. I would say: "Either no operators at all or a facility for defining operators which is complex enough to allow the definition of the standard operators." One thing of Haskell, I really like, is that only very few things are hard-wired into the compiler/interpreter.
Anyway, this was just for the record (I'm a happy Haskell user, I just ignore some of its features :-), so back to real work now.
Wolfgang
Well, for the most part, LaTeX only provides common operators. One problem, I came across some weeks ago, is that it is *not* possible to define his/her own operators (or, at least, that Lamport's "LaTeX - A Document Preparation System" doesn't tell you how you can define them).
It's actually fairly easy. There are several ways to do it. A simple hacky way to do it is the following: * Draw a little picture of your operator in your favorite drawing package. * Save this picture as an EPS drawing * define a new command that inserts this eps drawing, possibly scaling it appropriately. E.g. \newcommand{\myop}{\scalebox{0.1}{operators/myop.eps}} * Then just use \myop like any other operator in math mode. What this hack won't do is automatically change the size of the operator if the maths is in a subscript. There is probably an easy way to do this, but I haven't worked it out. A more elegant way to do it is to define a new postscript font (not hard if you have the correct software) and then define your operator macro to insert the relevant character. Hope this is useful to someone. -Rob
On Thursday, 2003-07-17, 16:07, CEST, Robert Ennals wrote:
Well, for the most part, LaTeX only provides common operators. One problem, I came across some weeks ago, is that it is *not* possible to define his/her own operators (or, at least, that Lamport's "LaTeX - A Document Preparation System" doesn't tell you how you can define them).
It's actually fairly easy. There are several ways to do it. A simple hacky way to do it is the following:
* Draw a little picture of your operator in your favorite drawing package.
* Save this picture as an EPS drawing
* define a new command that inserts this eps drawing, possibly scaling it appropriately. E.g.
\newcommand{\myop}{\scalebox{0.1}{operators/myop.eps}}
* Then just use \myop like any other operator in math mode.
What this hack won't do is automatically change the size of the operator if the maths is in a subscript. There is probably an easy way to do this, but I haven't worked it out.
A more elegant way to do it is to define a new postscript font (not hard if you have the correct software) and then define your operator macro to insert the relevant character.
Hello, I think, in both cases you don't define an *operator*. LaTeX probably won't use the correct spacing around the symbol. A related problem is that I cannot see a way to define a new "log-like function" (as Lamport names them), i.e., a function with a name consisting of several letters which have to be set in upright font with no spaces between them. Examples are log, min, max, sin, cos and tan.
[...]
Wolfgang
Wolfgang Jeltsch wrote:
A related problem is that I cannot see a way to define a new "log-like function" (as Lamport names them), i.e., a function with a name consisting of several letters which have to be set in upright font with no spaces between them. Examples are log, min, max, sin, cos and tan.
Check out the AMS-LaTeX package. I think it has a macro to solve this. It also includes a zillion new symbols/operators. http://www.ams.org/tex/amslatex.html If you have TeTeX installed as your TeX system, then it should be included. -- Matthew Donadio (m.p.donadio@ieee.org)
Wolfgang writes:
I think, in both cases you don't define an *operator*. LaTeX probably won't use the correct spacing around the symbol.
A related problem is that I cannot see a way to define a new "log-like function" (as Lamport names them), i.e., a function with a name consisting of several letters which have to be set in upright font with no spaces between them. Examples are log, min, max, sin, cos and tan.
This is off-topic, but I think you want to look at the \mathop, \mathbin, \mathrel, \mathord, etc commands. These declare anything as the appropriate math category, and so give the right spacing. Perhaps this should move to the Haskell Cafe? --KW 8-) -- Keith Wansbrough <kw217@cl.cam.ac.uk> http://www.cl.cam.ac.uk/users/kw217/ University of Cambridge Computer Laboratory.
Wolfgang Jeltsch wrote:
On Thursday, 2003-07-17, 09:08, CEST, Johannes Waldmann wrote:
A similar discussion sometimes surfaces in mathematics - where they have "user-defined" operators all over the place, and especially so since LaTeX.
Well, for the most part, LaTeX only provides common operators. One problem, I came across some weeks ago, is that it is *not* possible to define his/her own operators (or, at least, that Lamport's "LaTeX - A Document Preparation System" doesn't tell you how you can define them).
I am sorry, but it is simply a countertruth. You can define \mathop with all the \limits, \nolimits etc. properties. You have \mathchardef's etc. How do you think the AMS package has been constructed? Everything is written in a standard way, your liberty to create the most disgusting operators is unlimited. Some Haskell-related papers dealing with lenses, bananas and barbed-wires exploited already this possibility. /// in another posting,commenting the "graphical" ways to make operator-like icons, from posting by Robert Ennals///
I think, in both cases you don't define an *operator*. LaTeX probably won't use the correct spacing around the symbol.
A related problem is that I cannot see a way to define a new "log-like function" (as Lamport names them), i.e., a function with a name consisting of several letters which have to be set in upright font with no spaces between them. Examples are log, min, max, sin, cos and tan.
What's wrong with $ ... \mathrm{brumble}(2\cdot x) ...$ ? How do you think, the existing "standard ones" have been manufactured? \def \arctan {\mathop {\rm Arctan}} You can also put \hbox'es inside a math environment, which will prevent the automatic choice of \mathitalic. Read something about families, about \mathchardef, and about such options as \displaystyle \scriptstyle, etc., in order to choose automatically the correct size of the math. fonts. Also read something about big operators useful to define objects like sum, product, etc. Cheer up. YOU CAN DO EVERYTHING YOU WISH, and much more. Jerzy Karczmarczuk Jerzy Karczmarczuk
Johannes Waldmann wrote:
I do think that self-defined operators make a programm less readable.
I quite like most combinators from the pretty-printer or parsing libraries!
And what's absolutely horrible (IMHO) is to allow the user to declare arbitrary precedence and associativity for his creations. This requires that the source text of the defining module be there, only to parse (i. e., build the syntax tree of) a program that uses it.
The parser does not look into imported modules. Refined expressions trees are setup later (before type analysis).
And - the corresponding definitions in the standard seem rather ad-hoc: we have a funny expression grammar http://haskell.org/onlinereport/exps.html, with arbitrary restrictions (why just ten precendence levels?)
Maybe only the numbering is nonsense, but surely you want to have differently strong binding infix operations in order to write i.e. polynoms without parens.
I could live with Haskell's predefined operators (arithmetics, comparisons, bool-ops, (:), (++), (!), (!!), (.), ($)).
Why do you outrule other useful libraries (see above). In fact ($) is quite cryptic (for a non-Haskeller). An what should the difference be between (!!) and (!)? (I know it's the type.) In fact. I would like to reuse (sometimes) a predefined operator for another purposes (not easily covered by type class overloading and without hiding or qualifying prelude operators). Example: multiply a scalar with a vector. Without operators, formulae may become really horribly long.
I often use them, and I sometimes overload them (arithmetics, comparisons), but nothing more. (This is the design of Ada - there are operators, you can overload them, but you cannot change their precedence, or add new ones - so you can always parse a program text.)
Ada has true ad-hoc overloading, though.
Anyway, this was just for the record (I'm a happy Haskell user, I just ignore some of its features :-), so back to real work now.
I fully agree with these too lines. Christian
G'day all. On Thu, Jul 17, 2003 at 05:21:47PM +0200, Christian Maeder wrote:
Why do you outrule other useful libraries (see above). In fact ($) is quite cryptic (for a non-Haskeller).
Actually this gives me a perfect opportunity to rant a bit. :-) ($) is a wart, even for a Haskeller. It has the correct meaning and the correct precedence, but it has the wrong associativity. "Normal" application is left-associative. There's no reason why ($) shouldn't be either. Of course, sometimes you want right-associative apply, but there's already a simple way to do this. If you want to write: f (g (h (i x))) you can use this: f . g . h . i $ x But there is no way to write this parenthesis-free: f (g x) (h y) (i z) Now it's arguable that this is clearer with the parentheses, and I would agree with that. However, consider the situation with ($!). When you use strict-apply, you intend that one or more of the arguments to some function is/are to be strictly evaluated. Making ($!) right-associative only gives you _exactly_ one, and it's always the rightmost one, which gives it a 1-in-n chance of being right for a function of n arguments. In the above example, for instance: f (g x) (h y) (i z) Suppose you want (h y) to be strictly evaluated. I argue that some variation on this: f (g x) $! (h y) $ (i z) even with the parentheses is far more readable than the current alternatives. While it makes sense that ($!) should have the same associativity as ($), I can't for the life of me figure out why ($) is right-associative. There's probably a terribly good reason. Does anyone know what it is? Cheers, Andrew Bromage
On 2003-07-17 at 09:08+0200 Johannes Waldmann wrote:
On Wed, 16 Jul 2003, K. Fritz Ruehr wrote:
I think the cutest way to get what you want here is to define a new ^^^^^^ operator as follows:
(.<) = (.) . (.)
Indeed this is cute - but let me add a general comment here: in my code, I don't define any operators at all (only functions). I do think that self-defined operators make a programm less readable.
While I agree with that, I think that the language needs "user"-defined operators for libraries; it's a matter of defining them rarely and getting them widely accepted. I'm even tempted to suggest that the language ought to restrict their use to gurus. Someone mentioned multiplying by a scalar. I think this is a good application, but what we need is to agree (somehow) on the symbol used. I've used (*.) and (.*), with the dot being on the side the scalar is on (on the grounds that . is a scalar product elsewhere), but without wide agreement I agree that this sort of thing reduces readability, because while I can read these programmes, it's harder for everyone else. Jón -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk
G'day all. On Thu, Jul 17, 2003 at 04:46:13PM +0100, Jon Fairbairn wrote:
Someone mentioned multiplying by a scalar. I think this is a good application, but what we need is to agree (somehow) on the symbol used. I've used (*.) and (.*), with the dot being on the side the scalar is on (on the grounds that . is a scalar product elsewhere), but without wide agreement I agree that this sort of thing reduces readability, because while I can read these programmes, it's harder for everyone else.
Yuck. :-) I've run into the same problem with affine algebra, which has two types, the Point and the Vector, where a Vector is the difference between two Points: Vector + Vector = Vector Vector + Point = Point Point + Vector = Point Point + Point is an error Vector - Vector = Vector Point - Vector = Point Vector - Point = Point -- (this rule is a bit controversial) Point - Point = Vector It's not obvious what to call the operators here. One solution might be to relax the rules about how the types of operators are resolved. At the moment, you can define function names from different modules and all you need to do is qualify them when you use them. It's a little odd that you can't do something similar with operators, though no succinct syntax leaps to mind. Of course you could always allow overloading _without_ requiring module qualification (unless the overloading can't be resolved using type information). It'd make type checking NP-hard, but I seem to recall that it's already more complex than that. Cheers, Andrew Bromage
On Fri, Jul 18, 2003 at 11:39:48AM +1000, Andrew J Bromage wrote:
Someone mentioned multiplying by a scalar. I think this is a good application, but what we need is to agree (somehow) on the symbol used. I've used (*.) and (.*), with the dot being on the side the scalar is on (on the grounds that . is a scalar product elsewhere), but without wide agreement I agree that this sort of thing reduces readability, because while I can read these programmes, it's harder for everyone else.
Yuck. :-)
What's wrong with that solution? You might hope for something better, but it seems like it would work for, e.g., your situation below. Here are my concrete suggestions, using a variant of this notation; however, I mark the side that does _not_ have the scalar, on the grounds that scalar * scalar should be the original operator, and use '*>' or '<*' to do it.
I've run into the same problem with affine algebra, which has two types, the Point and the Vector, where a Vector is the difference between two Points:
Vector + Vector = Vector v1 + v2 = v3 Vector + Point = Point v1 +> p1 = p2 Point + Vector = Point p1 <+ v1 = p2 Point + Point is an error
Vector - Vector = Vector v1 - v2 = v3 Point - Vector = Point p1 <- v1 = p2 Vector - Point = Point -- (this rule is a bit controversial) This one is obviously an error. Add Point to both sides to get the error that you noted above. Point - Point = Vector p1 <-> p2 = v1
The other potential solution is to use an 'Additive' class class Additive a b c | a b -> c, c a -> b, c b -> a where (+) :: a -> b -> c class (Additive c b a) => Subtractive a b c where (-) :: a -> b -> c
One solution might be to relax the rules about how the types of operators are resolved. At the moment, you can define function names from different modules and all you need to do is qualify them when you use them. It's a little odd that you can't do something similar with operators, though no succinct syntax leaps to mind.
But you can use qualified names for operators! It just looks incredibly ugly. But you could write, say, 1 Float.+ 2 Peace, Dylan
G'day all. On Fri, Jul 18, 2003 at 04:08:25AM -0400, Dylan Thurston wrote:
What's wrong with that solution?
Working with these operators, I would spend a significant amount of time getting the '<' and '>' notations right rather than writing code. I don't like that. For example, using the suggested notation:
v1 + v2 = v3 v1 +> p1 = p2 p1 <+ v1 = p2
Quickly, without thinking too much, where do the '<' and '>' signs go here? p1 + v1 + v2 v1 + v2 + p1 v1 + p1 + v2
p1 <- v1 = p2
I'm pretty sure that's a syntax error. If not, it probably should be.
Vector - Point = Point -- (this rule is a bit controversial) This one is obviously an error. Add Point to both sides to get the error that you noted above.
It depends. If you allow the parity inversion operator -Point, then this operation makes a certain amount of sense. Some implementations (e.g. RenderMan) allow it, some don't. (But then, RenderMan defines Point + Bivector = Point. Clifford algebraists may now run screaming.)
The other potential solution is to use an 'Additive' class
class Additive a b c | a b -> c, c a -> b, c b -> a where (+) :: a -> b -> c class (Additive c b a) => Subtractive a b c where (-) :: a -> b -> c
Actually, that's not bad at all. It's certainly better than my previous suggestion of only putting a b -> c on "Additive" typeclass. Cheers, Andrew Bromage
On Sat, Jul 19, 2003 at 02:06:44PM +1000, Andrew J Bromage wrote:
G'day all.
On Fri, Jul 18, 2003 at 04:08:25AM -0400, Dylan Thurston wrote:
What's wrong with that solution?
Working with these operators, I would spend a significant amount of time getting the '<' and '>' notations right rather than writing code. I don't like that.
For example, using the suggested notation:
v1 + v2 = v3 v1 +> p1 = p2 p1 <+ v1 = p2
Quickly, without thinking too much, where do the '<' and '>' signs go here?
p1 + v1 + v2 v1 + v2 + p1 v1 + p1 + v2
Easy: p1 <+ (v1 + v2) or (p1 <+ v1) <+ v2 (v1 + v2) +> p1 v1 +> p1 <+ v2 The parens are slightly annoying (and to drop them I'd have to remember that the associativity of the operators), but they're mathematically clear. It's maybe easiest to think in terms of group theory with an action on a set: you're just distinguishing between the multiplication of group elements and the actual action. This distinction is not usually reflected in the notation, but it's really not such a hardship.
p1 <- v1 = p2
I'm pretty sure that's a syntax error. If not, it probably should be.
Oh, I missed that. Yes.
Vector - Point = Point -- (this rule is a bit controversial) This one is obviously an error. Add Point to both sides to get the error that you noted above.
It depends. If you allow the parity inversion operator -Point, then this operation makes a certain amount of sense. Some implementations (e.g. RenderMan) allow it, some don't.
But if you have -Point, then you have a 0 Point, and there's no distinction between Points and Vectors at all!
(But then, RenderMan defines Point + Bivector = Point. Clifford algebraists may now run screaming.)
I tried to think about what that should mean, and did not succeed. What is this operation?
The other potential solution is to use an 'Additive' class
class Additive a b c | a b -> c, c a -> b, c b -> a where (+) :: a -> b -> c class (Additive c b a) => Subtractive a b c where (-) :: a -> b -> c
Actually, that's not bad at all. It's certainly better than my previous suggestion of only putting a b -> c on "Additive" typeclass.
As I recall, the extra functional dependencies don't help very much in practice with the ambiguities previously noted. But you should try it for yourself. Peace, Dylan
On Saturday, 2003-07-19, 07:52, CEST, Dylan Thurston wrote:
[...]
But if you have -Point, then you have a 0 Point, and there's no distinction between Points and Vectors at all!
Yes, I always thought (and still think) that the (main) difference between points in affine geometry and radius vectors is that the former don't have an origin.
[...]
Wolfgang
G'day all. On Sat, Jul 19, 2003 at 01:52:32AM -0400, Dylan Thurston wrote:
It's maybe easiest to think in terms of group theory with an action on a set: you're just distinguishing between the multiplication of group elements and the actual action. This distinction is not usually reflected in the notation, but it's really not such a hardship.
I think that's where we differ.
But if you have -Point, then you have a 0 Point, and there's no distinction between Points and Vectors at all!
Yes there is. Points and Vectors transform differently when you change basis, plus the system catches certain kinds of programmer error (such as adding a Point to a Point). That you can elude the type system if you deliberately choose to is a different issue. Even most Haskell implementations let you do that.
I tried to think about what that should mean, and did not succeed. What is this operation?
Point + Bivector is used as a shorthand for Point + dual(Bivector). In Clifford Algebra, of course, everything should probably be embedded as a Multivector but, once again, this defeats the purpose of the exercise. Giving an error a legitimate meaning doesn't always help the programmer. Cheers, Andrew Bromage
Andrew J Bromage wrote:
Of course you could always allow overloading _without_ requiring module qualification (unless the overloading can't be resolved using type information). It'd make type checking NP-hard, but I seem to recall that it's already more complex than that.
Mere overload resolution (over monomorphic types) is not NP-hard. (This is only a common misconception.) Operators with function profiles can be viewed as context free grammar productions where the types are non-terminals. Overlaod resolution, like for ADA, corresponds then to the word problem for context free grammars that can be solved (by Earley's algorithm) in O(n^3) with n being the input length, ie. the length of an expression. (Although for overload resoultion the dominating input will be the number of productions.) Surely the number of ambiguous expression may grow exponentially (like in Isabelle, as far as I know) but you do not need to compute all these. Overload resolution in conjunction with polymorphism surely remains NP hard due to the "let". Furthermore, usually unification alone (know to be linear in theory) is implemented in a way that can cause "explosion". So I doubt, that overload resolution should be blamed if front-ends become really slow. Christian
G'day all. On Fri, Jul 18, 2003 at 11:08:16AM +0200, Christian Maeder wrote:
Mere overload resolution (over monomorphic types) is not NP-hard. (This is only a common misconception.)
No, but as you note below, the "interesting" cases are. Most of the more interesting number-like types are polymorphic (e.g. Complex, Ratio).
Overload resolution in conjunction with polymorphism surely remains NP hard due to the "let". Furthermore, usually unification alone (know to be linear in theory) is implemented in a way that can cause "explosion".
So I doubt, that overload resolution should be blamed if front-ends become really slow.
The question is not "is it theoretically slow?" The question is "are you ever likely to see the worst-case behaviour if you're not actively looking for it, or otherwise doing something dubious?" Remember that the situation we're looking at is that there are a small number of operators (e.g. those which work on number-like types) which people want to heavily overload. A program which used a mixture of these types could easily tickle exponential behaviour quite quickly if the programmer is not careful. Plus, what would cause this behaviour is not their _use_ as such, but rather the number of modules imported which have these overloaded operators defined. Cheers, Andrew Bromage
Mere overload resolution (over monomorphic types) is not NP-hard. (This is only a common misconception.)
I can only repeat my above sentence.
No, but as you note below, the "interesting" cases are. Most of the more interesting number-like types are polymorphic (e.g. Complex, Ratio).
This kind of overloading is no cause for exponentiell behaviour, if it's either solved by type class overloading or by monomorphic overload resolution. (Only let-polymorphism is "hard".)
The question is not "is it theoretically slow?" The question is "are you ever likely to see the worst-case behaviour if you're not actively looking for it, or otherwise doing something dubious?"
I agree with this statement, in fact this argument was used to employ an exponentiell algorithm (I think Cormacks's algorithm in ADA, below) that is fast in practice.
Remember that the situation we're looking at is that there are a small number of operators (e.g. those which work on number-like types) which people want to heavily overload. A program which used a mixture of these types could easily tickle exponential behaviour quite quickly if the programmer is not careful. Plus, what would cause this behaviour is not their _use_ as such, but rather the number of modules imported which have these overloaded operators defined.
Again, this standard case is no problem for overload resolution (unless implemented too naively.) Cormack's algorithm will solve such cases fast by feeding in the expected result type. Some books on compilers explain overload resolution by (two, set-valued) attributes. Such an algorithm is also not exponentiell! I admit the combination of overload resolution and polymorphism is not simple, but Haskell has solved it in a certain way with type classes! Cheers Christian See: T.Pennello, F.DeRemer, and R.Meyers: A simplified Operator Identification Scheme for ADA, 1980 (ACM SIGPLAN Notices 15(7-8):82-87
G'day all. On Mon, Jul 21, 2003 at 01:07:39PM +0200, Christian Maeder wrote:
Mere overload resolution (over monomorphic types) is not NP-hard. (This is only a common misconception.)
I can only repeat my above sentence.
I'm a firm believer in the maxim that the best way to find information on the net is to post wrong information. :-) As a matter of interest, is there a known worst-case complexity for the precomputation required by Earley's algorithm to handle arbitrary CFGs?
This kind of overloading is no cause for exponentiell behaviour, if it's either solved by type class overloading or by monomorphic overload resolution. (Only let-polymorphism is "hard".)
I don't believe that expected-case O(N^3) behaviour counts as "not hard", even if it's not exponential. These things have a way of biting you when you least expect it.
From an economic point of view, programmer time is very expensive. Much more so than machine time. A few seconds spent resolving overloading on a large program is a few seconds that the programmer is effectively stalled. Plus, these things add up. A short time plus a short time is not necessarily a short time.
Another economic issue to consider is that the time spent compiling a program over its life is often quadratic in the final size of the program. One necessary requirement for tractible software development is low constant factors. (This, of course, assumes that the program grows linearly over its life and the machines used to compile on are not upgraded over that time. In commercial development, it's generally considered good practice to freeze the hardware/compiler/OS combination throughout the maintenance period of a specific software release. This assumption may not hold in some development environments, such as in open source development.)
I admit the combination of overload resolution and polymorphism is not simple, but Haskell has solved it in a certain way with type classes!
I think we agree that Haskell's type class scheme is an extremely good mechanism for the problem of overloading. However, mechanism is not the same as policy. The issue that we have before us is that the current numeric type class hierarchy is too coarse-grained for people developing richer varieties of numeric types. There are problems with making it too fine-grained, as well. Until we find the "sweet spot", the problem is not solved. Cheers, Andrew Bromage
Andrew J Bromage wrote:
As a matter of interest, is there a known worst-case complexity for the precomputation required by Earley's algorithm to handle arbitrary CFGs?
Earley's algorithm handles exactly arbitrary (in particular ambiguous) CFGs without precomputation. see i.e. Aho,Ullman, "The Theory of Parsing, Translation, and Compiling" Vol.1, 1972
I don't believe that expected-case O(N^3) behaviour counts as "not hard", even if it's not exponential. These things have a way of biting you when you least expect it.
Right, this (worst-case) behaviour may be bad, but that can only be (and partly was already) answered in practice. (A constant factor or constant overhead for precomputations can spoil anything.) Christian
How about... h a = f . g a or... f $ g 1 2
f :: Int -> Int f x = x*x
g :: Int -> Int -> Int g a b = a + b
...
But what I really want is a function with signature Int -> Int -> Int.
-- Brett Letner Galois Connections, Inc. http://www.galois.com mailto:bletner@galois.com phone:(503)626-6616 ext.110
K. Fritz Ruehr (Wed, Jul 16, 2003 at 11:19:55PM -0700): c0 = ($) -- application
c1 = (.) -- good old composition
c2 = (.) . (.) -- my (.<) from above
c3 = (.) . (.) . (.)
c4 = (.) . (.) . (.) . (.)
-- etc.
Each of these gives an appropriate generalization allowing the composition of a one-argument function with an n-argument one (similar to the notations used in the usual definitions for primitive recursive function). That is to say, the types are as follows (the middle three dots on the second line are an ellipsis, apologies in advance):
cn :: (a -> b) -> F(t,n,a) -> F(t,n,b)
cn = (.) . ... . (.) -- n occurrences of (.)
where the awkward phrase "F(t,n,x)" expands as follows via some imagined macro facility.
F(t,n,x) === t1 -> t2 -> ... -> tn -> x
Of course, what we really want to do is to express this as a fold of composition over a dynamically generated list of compositions, i.e.:
c n = foldr (.) id (take n (repeat (.)))
But I think giving this a nice general type, where n is a run-time argument and the replicated (.)s have distinct but related types, is quite difficult.
Such an abstraction would not only be good for functions but also for tuples. t 0 = () -- void t 1 = t1 -- singleton t 2 = (t1,t2) -- tuple t 3 = (t1,t2,t3) -- triple t n = (t1,...,tn) -- n-tuple or even more general t * = (t1,t2,...) -- countable infinite tuple such that t n == t[forall k in Natural without Zero . t(n+k) = t 0] and something like curry :: (t * -> a) -> c * -> a uncurry :: (c * -> a) -> t * -> a zip :: c [*] -> [t *] -- What's a good notation for this? unzip :: [t *] -> c [*] (Maybe only with n instead of * forall n.) -- Stefan Karrmann
Hi, you may use (f .) . g. Wolfgang On Thursday, 2003-07-17, 02:27, CEST, Dr Mark H Phillips wrote:
Hi,
Hopefully this is a simple question. I am wanting to know good ways of using ".", the function composition operator, when dealing with currying functions.
Suppose I have the following functions defined:
f :: Int -> Int f x = x*x
g :: Int -> Int -> Int g a b = a + b
If I wish to add 1 and 2 together and then square them I can do:
f (g 1 2) = 9
but what if I wish to use function composition in the process?
I can't do
(f.g) 1 2
because the 2 doesn't get passed in till too late.
I could do
(f.(g 1)) 2
or even
(f.(uncurry g)) (1,2)
But what I really want is a function with signature Int -> Int -> Int. The answer is probably:
(curry (f.(uncurry g))) 1 2
but this seems awfully messy just to do f (g 1 2).
And what if g were a function with three curried arguments? Then uncurry and curry wouldn't apply. What then?
Is there a better way?
Thanks,
Mark.
Thanks to all the people who responded to my question! The solution from Wolfgang Jeltsch: (f.).g was what I was after. But the other responses were useful also. Thanks! Mark. On Thu, 2003-07-17 at 09:57, Dr Mark H Phillips wrote:
Hi,
Hopefully this is a simple question. I am wanting to know good ways of using ".", the function composition operator, when dealing with currying functions.
Suppose I have the following functions defined:
f :: Int -> Int f x = x*x
g :: Int -> Int -> Int g a b = a + b
If I wish to add 1 and 2 together and then square them I can do:
f (g 1 2) = 9
but what if I wish to use function composition in the process?
I can't do
(f.g) 1 2
because the 2 doesn't get passed in till too late.
I could do
(f.(g 1)) 2
or even
(f.(uncurry g)) (1,2)
But what I really want is a function with signature Int -> Int -> Int. The answer is probably:
(curry (f.(uncurry g))) 1 2
but this seems awfully messy just to do f (g 1 2).
And what if g were a function with three curried arguments? Then uncurry and curry wouldn't apply. What then?
Is there a better way?
Thanks,
Mark.
-- Dr Mark H Phillips Research Analyst (Mathematician)
AUSTRICS - smarter scheduling solutions - www.austrics.com
Level 2, 50 Pirie Street, Adelaide SA 5000, Australia Phone +61 8 8226 9850 Fax +61 8 8231 4821 Email mark@austrics.com.au
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell -- Dr Mark H Phillips Research Analyst (Mathematician)
AUSTRICS - smarter scheduling solutions - www.austrics.com Level 2, 50 Pirie Street, Adelaide SA 5000, Australia Phone +61 8 8226 9850 Fax +61 8 8231 4821 Email mark@austrics.com.au
participants (17)
-
Andrew J Bromage -
Brett A. Letner -
Christian Maeder -
Dean Herington -
dpt＠exoskeleton.math.harvard.edu -
dpt＠lotus.bostoncoop.net -
Dr Mark H Phillips -
Jerzy Karczmarczuk -
Johannes Waldmann -
Jon Fairbairn -
K. Fritz Ruehr -
Keith Wansbrough -
Matthew Donadio -
Robert Ennals -
Stefan Karrmann -
Tom Pledger -
Wolfgang Jeltsch