[Haskell] Typing in haskell and mathematics

[Ben Rudiak-Gould]

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