What to use for type classes or constraints?

[dcurrie]

I'd like to make a generic tree, i.e., one that can contain values of any type, and keys that are comparable.

There is already a compare function that is perfect. How can I specify a tree type that uses it?

If I use

public type bbtree<k,v> {
  Nil
  Node(left: bbtree<k,v>, right: bbtree<k,v>, size: int, key: k, value: v)
}

and use it

public fun insert(tree: bbtree<k,v>, key: k, value: v): bbtree<k,v> {
    match(tree) {
        // identifier Nil is ambiguous!? Nil -> new-leaf(key, value)
        Node(tl, tr, _, tk, tv) ->
            match(compare(key, tk)) {
                LT -> balance(insert(tl, key, value), tk, tv, tr)
                GT -> balance(tl, tk, tv, insert(tr, key, value))
                EQ -> new-node(tl, key, value, tr)
            }
        _ -> new-leaf(key, value)
    }
}

there is an error

bbtree.kk(106,19): error: no function compare is defined that matches the argument types
  context      :                   compare(key, tk)
  term         :                   compare
  inferred type: ($a, _b, ...) -> ...
  candidates   : compare: (int, int) -> order
                 compare: (x : double, y : double) -> order
                 compare: (x : bool, y : bool) -> order
                 compare: (x : char, y : char) -> order
                 compare: (x : string, y : string) -> order

I'd be happy to constrain keys to the "candidates" above... but how?

[daanx]

Ah, there are no type classes in Koka like there are in Haskell. There is static overloading of identifiers: like a (+) operation is defined for int , double, string etc. and Koka will pick the right one based on the static type; Here Koka cannot statically determine which compare function to use as the tree is polymorphic in the key (of type k).

The only way around it for now is:

1. Use a concrete type for the tree key :-) Actually, that may not be too bad -- for example, when I implemented the Haskell standard Data.Map and Data.Set libraries, I used Data.IntMap concretely as that could use Patricia trees which can be more efficient. Often, string maps can be made better as well.
2. pass the comparison function as an extra parameter to insert; a bit cumbersome but ok. A negative is that we could switch comparison functions for each insert and violate invariants.
3. package each tree with an appropriate comparison function at creation and use that during insertion; this maintains the invariant and is less cumbersome; however, it may still be a problem when merging different trees where the comparisons for each tree may differ. Here Haskell really shines with typeclasses.
4. use a cmp effect and use that for insertion etc. the compare function becomes like an implicit parameter. (This may be tricky though when using many trees with differently typed keys but there is ongoing work to make that work better.)
5. wait for a future version of Koka that has some form of type-class constraints: actually, I have been thinking about using the ideas in this 1995 paper by Wadler, Odersky and Wehr, where a form of overloading is presented that is more restricted than arbitrary type classes. I generally dislike the type classes in general as these are too powerful in Haskell and thus lead to a huge design space with many tricky edge cases -- it's like another language inside Haskell. I would like to find something much simpler that just handles this kind of dynamic overloading.

[dcurrie]

Thank you, Daan. I was aware of 1 through 3, and not too fond of them! ;-) Having never used a language-supported effect system before, I'll give option 4 a try. It seems to suffer some of the downsides of 2 (switch comparison functions for each insert), but I'd like to learn a bit about effect handlers and with. So, I made these changes:

public effect cmp<k> {
  fun cmp(x: k, y: k) : order
}

and

public fun insert(tree: bbtree<k,v>, key: k, value: v): cmp<k> bbtree<k,v> {
    match(tree) {
        Node(tl, tr, _, tk, tv) ->
            match(cmp(key, tk)) {
                Lt -> balance(insert(tl, key, value), tk, tv, tr)
                Gt -> balance(tl, tk, tv, insert(tr, key, value))
                Eq -> new-node(tl, key, value, tr)
            }
        // identifier Nil is ambiguous!
        // Nil -> new-leaf(key, value)
        _ -> new-leaf(key, value)
    }
}

This compiles. When I try to test with

fun testinst(tree: bbtree<k,v>, key: k, value: v): bbtree<k,v> {
    with fun cmp(x: int, y:int) { compare(x,y) }
    insert(tree, key, value)
}

I get

compile: bbtree.kk
loading: std/core
loading: std/core/types
loading: std/core/hnd
check  : bbtree
bbtree.kk(122, 5): error: effects do not match
  context        :     with fun cmp(x: int, y:int) { compare(x,y) }
                       insert(tree, key, value)
  term           :     insert(tree, key, value)
  inferred effect: <cmp<$a>|_e1>
  expected effect: <cmp<int>|_e>

What am I doing wrong?
Is this the sort of thing you meant in option 4?

[dcurrie]

Ah, it came to me last night... testinst isn't generic in the key type, so I have to specify it:

fun testinst(tree: bbtree<int,v>, key: int, value: v): bbtree<int,v> {
    with fun cmp(x: int, y:int) { compare(x,y) }
    insert(tree, key, value)
}

Now it compiles at least!

[schicks]

Would that be like the OCaml functor system? it does seem like that might play very nicely with effect handlers. (eg, a module signature as an effect, and a with open kind of statement to handle that effect)