A little JavaScript, a few sums

(2018-10-07. Index.)

(Standard ML code here. JavaScript code here.)

In chapter 6 of The Little MLer there is some stuff.

There is fruit:

datatype fruit =
    Peach
  | Apple
  | Pear
  | Lemon
  | Fig

There is tree:

datatype tree =
    Bud
  | Flat of fruit * tree
  | Split of tree * tree

There is height, which looks quite like this in the book:

(* height : tree -> int *)
fun height Bud = 0
  | height (Flat(_,  t)) = 1 + height (t)
  | height (Split(s, t)) = 1 + Int.max (height(s), height(t))

There are other things in there too. More functions, and like, stuff. We mostly want these, just.

Anyway we can make a couple of trees:

val smol_tree = Split (Bud, Flat (Peach, Bud))
val larger_tree = Split (Flat (Apple, Flat (Lemon, Bud)), Flat (Peach, Bud))

And so, in like a REPL:

- height smol_tree;
val it = 2 : int
- height larger_tree;
val it = 3 : int

Okay.


So JavaScript is a pretty nonstandard ML.

(By the way, from here on, I don’t know what I’m doing, how stupid it is, how weird it is, or anything. I really don’t know JavaScript, or like how people use it, much.)

In the book we use sums for the tree-stuff. Sums are also sometimes called tagged unions. We will make a tag-function for tagging like, some stuff:

const tag = t => {
  function halp() {
    return { tag: t, values: [... arguments] }
  }
  return halp;
};

We can try to use it. Something like this:

tag("label")(1, "horse", [2,3]);

Gives us something like this:

{
  tag: "label",
  values: Array(3)
    0: 1
    1: "horse"
    2: (2) [2, 3]
}

It appears to have the tag and the stuff we passed in. Good. We can make constructors then.

Fruit:

const Peach = tag("Peach")();
const Apple = tag("Apple")();
const Pear = tag("Pear")();
const Lemon = tag("Lemon")();
const Fig = tag("Fig")();

Tree:

const Bud = tag("Bud")();
const Flat = tag("Flat");
const Split = tag("Split");

(Flat and Split are like constructor-functions that need additional stuff when we use them to construct stuff. The other ones are constructors that don’t need additional stuff, so we have like already, uh, passed in the no arguments to those.)

Now we can make the trees:

const smol_tree = Split(Bud, Flat(Peach, Bud));
const larger_tree = Split(Flat(Apple, Flat(Lemon, Bud)), Flat(Peach, Bud));

So we have like half of sum now. We have construct. We need destruct.

Okay with sums it’s like, in order to construct a value you have to do one of the things. A fruit is a peach or an apple or one of the other ones. In order to construct one we only have to choose like which one.

But in order to destruct a value, it’s like, it can be any one of the things, so we have to know what to do in every case. We have to know what to do if it is a peach and we have to know what to do if it is an apple and so on. We have to know how to deal with all the things.

A thing some people enjoy saying is that sum is the dual of product. In order to construct a product you have to supply all the things, but when destructing one you’re maybe only interested in one of the things, and you can like get at that thing while ignoring the other things. (E.g. to make a pair you have to supply two things, but when you have a pair you can use just the first of its things if you like.)

So a constructed product could totally have everything required to destruct a sum. Like maybe an object along the lines of:

{
  Peach: // what to do if it is a peach
  Apple: // what to do if it is an apple
  // and so on...
}

So if we have a sum-value and like a, uh, corresponding product-value, then we can use the tag from the sum-thing to look up the “what to do” in the product-thing. We will use functions for the “what to do.” We will make a match-function for destructing sums:

const match = cases => x => cases[x.tag].apply(null, x.values);

We can try to make a function with match:

const is_apple =
  match(
    {
      Peach: () => false,
      Apple: () => true,
      Pear: () => false,
      Lemon: () => false,
      Fig: () => false
    }
  );

And then use it:

is_apple(Apple);
is_apple(Fig);

That gives us like true and false. Seems fine.

Okay should can make height then:

const height =
  match(
    {
      Bud: () => 0,
      Flat: (_, t) => 1 + height(t),
      Split: (a, b) => 1 + Math.max(height(a), height(b))
    }
  );

Test:

height(smol_tree);
height(larger_tree);

And that gives like 2 and 3. So probably yay.