run.ceylon

void tree(Tree<Integer> tree) {
    Integer? i = tree.element;
    if (exists i) {
        value sum = i + 1;
    }
    [NonemptyTree<Integer>*] children = tree.children;
    if (nonempty children) {
        NonemptyTree<Integer> child = children[0];
    }
    NonemptyTree<Integer>? child = children[0];
}

void empty(EmptyTree tree) {
    Null n = tree.element;
    [] children = tree.children;
    Null child = children[0];
}

void nonemptyTree(NonemptyTree<Integer> tree) {
    Integer i = tree.element;
    value sum = i + 1;
    [NonemptyTree<Integer>*] children = tree.children;
    if (nonempty children) {
        NonemptyTree<Integer> child = children[0];
    }
    NonemptyTree<Integer>? child = children[1];
    if (exists child) {}
}

void leaf(Leaf<Integer> tree) {
    Integer i = tree.element;
    value sum = i + 1;
    [] children = tree.children;
    Null child = children[0];
}

void branch(Branch<Integer> tree) {
    Integer i = tree.element;
    [NonemptyTree<Integer>+] children = tree.children;
    Integer j = children[0].element;
    NonemptyTree<Integer>? child = children[1];
    Integer? k = child?.element;
}

void heterogenousTree(Branch<Integer|Float|String|Character|Boolean, Integer, [Leaf<Float>, Leaf<String>, Leaf<Character>, Leaf<Boolean>]> tree) {
    Integer i = tree.element;
    [Leaf<Float>, Leaf<String>, Leaf<Character>, Leaf<Boolean>] children = tree.children;
    Float f = children[0].element;
    String s = children[1].element;
    Character c = children[2].element;
    Boolean b = children[3].element;
    Null n = children[4];
}

shared void run() {
    value tree = Branch{
        element = "foo";
        children = [
            Leaf{
                element = "bar";
            },
            Branch{
                element = "baz";
                children = [
                    Leaf{
                        element = "qux";
                    }
                ];
            }
        ];
    };
    print(tree);
    print(Zipper(tree).down?.right?.element("BAZ")?.root);
}

Tree.ceylon

shared interface Tree<out Element> of EmptyTree | NonemptyTree<Element>
        satisfies Collection<Element> given Element satisfies Object {
    shared formal Element? element;
    shared formal [NonemptyTree<Element>*] children;
    clone() => this;
}

TreeEmpty.ceylon

shared interface EmptyTree of emptyTree satisfies Tree<Nothing> {
    shared actual Null element => null;
    shared actual [] children => [];
    iterator() => emptyIterator;
    string => "[]";
    empty => true;
    size => 0;
}

shared object emptyTree satisfies EmptyTree {}

TreeNonempty.ceylon

shared interface NonemptyTree<out Element> of Leaf<Element> | Branch<Element>
        satisfies Tree<Element> given Element satisfies Object {
    shared actual formal Element element;
    iterator() => {element, *expand(children)}.iterator();
    string => "[``", ".join{element, *children}``]";
    empty => false;
}

TreeNonemptyBranch.ceylon

shared final class Branch
        <out Element, out Root = Element, out Children = [NonemptyTree<Element>+]>
            (element, children) satisfies NonemptyTree<Element>
                given Element satisfies Object
                given Root satisfies Element
                given Children satisfies [NonemptyTree<Element>+] {
    shared actual Root element;
    shared actual Children children;
    shared actual Boolean equals(Object that) {
        if (is Branch<Object> that) {
            return element == that.element && children == that.children;
        }
        else {
            return false;
        }
    }
    hash => [element, *children].hash;
    size = 1 + sum(children.map(NonemptyTree<Element>.size));
}

TreeNonemptyLeaf.ceylon

shared final class Leaf<out Element>(element) satisfies NonemptyTree<Element>
        given Element satisfies Object {
    shared actual Element element;
    shared actual [] children => [];
    shared actual Boolean equals(Object that) {
        if (is Leaf<Object> that) {
            return element == that.element;
        }
        else {
            return false;
        }
    }
    hash => [element].hash;
    size => 1;
}

Zipper.ceylon

shared final class Zipper<out Element>(tree, ancestors = [])
        given Element satisfies Object {
    shared NonemptyTree<Element> tree;
    shared [[Element, [NonemptyTree<Element>*], [NonemptyTree<Element>*]]*] ancestors;
    shared NonemptyTree<Element> root => up?.root else tree;
    shared Zipper<Element>? up {
        if (exists parent = ancestors.first) {
            return Zipper<Element>(
                Branch(
                    parent[0],
                    parent[1].fold([tree, *parent[2]])(
                        (siblings, sibling) => [sibling, *siblings]
                    )
                ),
                ancestors.rest
            );
        }
        else {
            return null;
        }
    }
    shared Zipper<Element>? left {
        if (exists parent = ancestors.first, nonempty left = parent[1]) {
            return Zipper<Element>(
                left.first,
                [[parent[0], left.rest, [tree, *parent[2]]], *ancestors.rest]
            );
        }
        else {
            return null;
        }
    }
    shared Zipper<Element>? right {
        if (exists parent = ancestors.first, nonempty right = parent[2]) {
            return Zipper<Element>(
                right.first,
                [[parent[0], [tree, *parent[1]], right.rest], *ancestors.rest]
            );
        }
        else {
            return null;
        }
    }
    shared Zipper<Element>? down {
        if (nonempty children = tree.children) {
            return Zipper<Element>(
                children.first,
                [[tree.element, [], children.rest], *ancestors]
            );
        }
        else {
            return null;
        }
    }
    shared Zipper<Element|Other> element<out Other>(Other element)
            given Other satisfies Object {
        if (nonempty children = tree.children) {
            return Zipper<Element|Other>(Branch(element, children), ancestors);
        }
        else {
            return Zipper<Element|Other>(Leaf(element), ancestors);
        }
    }
}