__It is all distributivity__

Let • be a binary infix operator. Depending on how we Curry, we can form two classes of unary operators from **,** the general elements of which are often denoted by (`x`•) and (•`y`), defined

(

x•) = 〈λy:x•y〉 (•y) = 〈λx:x•y〉

We call them in this note "the derived unary operators".

To begin with we observe —with apologies for the two different usages of parentheses—

(`x`•`z`)•`y` = `x`•(`z`•`y`)

= {definition of derived operators}

(•`y`).((`x`•).`z`) = (`x`•).((•`y`).`z`)

= {definition of functional composition}

((•`y`)◦(`x`•)).`z` = ((`x`•)◦(•`y`)).`z` ,

hence, that a binary operator is "associative" means that its derived unary operators commute.

To say that • "distributes over" some binary operator is really a statement about its derived unary operators: "• distributes from the left over □" means that for all `x`, `y`, `z`:

(`x`•).(`y` □ `z`) = (`x`•).`y` □ (`x`•).`z` ;

distribution from the right means similarly

(•`x`).(`y` □` z`) = (•`x`).`y` □ (•`x`).`z` .

Both formulae are of the form

`f`.(`y` □ `z`) = `f`.`y` □ `f`.`z` ,

which captures "`f` distributes over □". But what comes of this formula if □ turns out to be unary? Replacing in the last formula `p`□`q` by `g`.`p`, we get

`f`.(`g`.`y`) = `g`.(`f`.`y`) or `f`◦`g` = `g`◦`f` .

Hence, that two unary operators "commute" means that they distribute over each other. Hence, that a binary operator is associative just means that its derived unary operators distribute over each other.

Austin, 2 November 1992

prof. dr. Edsger W. Dijkstra

Department of Computer Sciences

The University of Texas as Austin

Austin, TX 78712-1188 USA

Transcribed by Guy Haworth.

Last revised