[Haskell] Typing in haskell and mathematics
Ben Rudiak-Gould
Benjamin.Rudiak-Gould at cl.cam.ac.uk
Tue Feb 1 07:49:20 EST 2005
Jeremy Gibbons wrote:
> If you want "a < b < c" to mean "(a < b) && (b < c)" but "a + b + c"
> to mean "(a + b) + c", you're going to have to treat "<" differently
> from "+", which goes against the spirit of considering them both
> simply functions.
I've wanted to chime in here for a while now. I strongly disagree with
the idea that there's something wrong with "a < b < c", in math or in
programming languages.
Infix operator parsing happens in two independent stages: first
operators are grouped according to precedence, and then according to
associativity. In the second stage we only consider expressions that
look like (e1 `op1` e2 `op2` ... `opn` en), where all operators are in
the same precedence class. In most languages this stage looks for three
cases:
* all operators are left-associative
* all operators are right-associative
* n==1 and `op1` is nonassociative
Now, the first two of these are hacks, when applied to associative
operators. A mathematician would never say that "a+b+c" is shorthand for
"(a+b)+c" -- that smacks of evaluation order. "a+b+c" is shorthand for
"parenthesize it however you like, because it *doesn't matter*". It's
just a list of things to be added up. This applies equally to
"a+b-c-d+e", which is a notational abbreviation for "a+b+(-c)+(-d)+e".
And no mathematician would write "a*b/c/d*e". The idea that this would
be evaluated from left to right is an error of grade-school students.
(Henning Thielemann's paper has an example of this: the student who
writes something like "7 * 3 + 1 = 22 / 2 = 11 * 3 + 1 = 34...")
Left-associativity and right-associativity are useful hacks, granted --
but then why limit ourselves to foldl1 and foldr1? What about foldl and
foldr (specifying a zero element in the infix declaration) or foldc
where foldc takes (a at b@c at d@e at f@g at h) to (((a at b)@(c at d))@((e at f)@(g at h)))?
This is a better way of parenthesizing `merge`, for example. (>>=) can't
be right-associative and so ends up left-associative, even though that
leads to inefficient code. It ought to produce (e1 >>= (\x1 -> e2 x1 >>=
(...))), but we have no way to express that.
The following two cases seem much less hacky to me:
* all operators are the same and the operator is (declared as) variadic
* all operators are (declared as) inequalities (giving (e1 `op1` e2)
&& (e2 `op2` e3) && ...)
Such operators are commonly seen in mathematics, unlike true
left-associative or right-associative operators, which are rare and
usually merit a special explanation to avoid confusing the reader.
Even the first stage (precedence) is broken in every computer language
I've encountered. How should (a .&. b * c) group? Clearly it shouldn't
-- it should be rejected. But there's no way to do that except to give
(.&.) and (*) equal precedence and opposite associativities. Aside from
the fact that that's clearly a hack, I don't see any reason to expect
that the graph of operator clashes can be two-colored in general, or
that every connected subgraph can sensibly have a single precedence.
The problem is the silly imposition of a linear order on precedence
classes, a convention which seems to date to the dawn of high-level
programming languages, but was never found in mathematics. Even
languages which could easily specify a partial order (because they have
a fixed set of operators) don't do it. I've never understood why.
There's a strong case to be made for getting rid of infix operators
entirely (I personally think that complex arithmetic/logical expressions
are much more comprehensible in Scheme), but if you're going to have
them, variadic operators make more sense than left-associative operators.
-- Ben
More information about the Haskell
mailing list