[MLton] associativity of &

[Vesa Karvonen]

Quoting Stephen Weeks <sweeks@sweeks.com>:
> In writing up the fold stuff, I wondered about the decision to make
> the "&" of product types be infix left, rather than infix right.
> 
>   datatype ('a, 'b) prod = & of 'a * 'b
>   infix  4 &
> 
> What was the reason behind that decision?

I came up with the infix & when I came up with the for-loop combinators
(http://mlton.org/ForLoops - I should really add the >>= operator to that
page).  In that context the choice between infix & and infixr & can be
made fairly arbitrarily (there may be some performance implications (one
way or the other), but I don't have the time to think about them at the
moment).

I recall thinking about whether infix & or infixr & was better, but I
don't recall any particular technical reason for choosing infix &.

> I think it might be better
> to make "&" infix right.  By analogy with lists, in which :: is infix
> right, it is easier to recur over products via a fold left if they
> look like
> 
>   1 & (2 & (3 & (4 & ())))
> 
> rather than
> 
>   ((((1 & 2) & 3) & 4) & ())

Yes, I recently toyed with the idea of implementing Joy-like combinators
(http://www.latrobe.edu.au/philosophy/phimvt/joy.html) in SML and I used
infixr & for the same reason.  (See the code below.)  infixr & may indeed
be overall the better choice.

> With "&" infix right, constructing product via a fold left is slightly
> trickier, because one has to construct a function that fills a "hole"
> in the product, and apply that function at the very end.  But it's not
> too bad.

Maybe one could implement combinators to make it easy to use either
infix & or infixr &.

-Vesa Karvonen

(* Joy-like combinators
 *
 * These combinators do *not* quite capture Joy.  The dynamic
 * typing of Joy isn't easily translated to static H-M.
 *)

datatype ('a, 'b) c = & of 'a * 'b
infixr &

fun $ p = p
fun P ? k = k ?
fun % p f = P (f o p)
fun J k = k $
fun ` ? x = P? %(fn s => x & s)
fun dup ? = P? %(fn x & s => x & x & s)

fun uop ? uop = P? %(fn x & s => uop x & s)
fun bop ? bop = P? %(fn l & r & s => bop (l, r) & s)

fun neg ? = uop? ~
fun add ? = bop?op +
fun mul ? = bop?op *
fun sub ? = bop?op -
fun div' ? = bop?op div
fun mod' ? = bop?op mod
fun while' ? =
    P? %(fn st & pr & s =>
            let fun lp s = if hd (pr s) then s else lp (st s) in lp s end)
fun primrec ? =
    P? %(fn st & ba & n & s =>
            let fun lp (i, x & s) =
                    if i = n then x & s else lp (i+1, st (x & i+1 & s))
            in lp (0, ba s)
            end)

fun run p = (fn x & () => x) (p ())

val 3 = run (J `1 `2 add $)
fun fact ? = P? `(J `1 $) `(J mul $) primrec
fun sq ? = P? dup mul
val 120 = run (J `5 fact $)