Skip to content

Instantly share code, notes, and snippets.

@mandel59
Forked from anonymous/gist:6937815
Last active December 25, 2015 07:18
Show Gist options
  • Save mandel59/6937823 to your computer and use it in GitHub Desktop.
Save mandel59/6937823 to your computer and use it in GitHub Desktop.
enum void = {}
struct unit = {}
enum bool = {
false
true
}
enum nat = {
zero
succ: nat
}
struct point3D[T=double] = {
x: T
y: T
z: T
}
enum list(a) = {
nil
cons: {
head: a
tail: ref(list(a))
}
}
enum vect(n: nat, a) = {
case n = zero:
nil
case(m) n = succ(m):
cons: {
head: a
tail: vect(m, a)
}
}
def fib(n) = {
case n = 0: 0
case n = 1: 1
case(m) n = succ(succ(m)): fib(m) + fib(succ(m))
}
def fold_left[a, b](f: a -> b -> a): a -> list(b) -> a = {
def foldl(x, l) {
case l = nil: x
case(y, ys) l = cons {y; ys}: foldl(f(x, y), ys)
}
foldl
}
def fold_right[a, b](f: a -> b -> b): list(a) -> b -> b = {
def foldr(l, y) {
case l = nil: y
case(x, xs) l = cons {x; xs}: f(x, foldr(xs, y))
}
foldr
}
def partition[a](p: a -> bool): list(a) -> {list(a); list(a)} = {
def part(l) = {
case l = nil: {nil; nil}
case l = cons {x; xs}: {
def {lt; lf} = part(xs)
case p(x) = true: {cons {x; lt}; lf}
default: {lt; cons {x; lf}}
}
}
part
}
def concat[a](lx: list(a), ly: list(a)): list(a) = {
case lx = nil: ly
case lx = cons {x; xs}: cons {x; concat(xs, ly)}
}
def quick_sort[a](cmp: a -> a -> bool): list(a) -> list(a) = {
def qsort(l) {
case l = nil: nil
case l = cons {x; xs}:
def {lt; ge} = partition(cmp x)
concat(qsort(lt), cons {x; qsort(ge)})
}
qsort
}
struct utf8 = {
x0: byte
case x0 = byte {0;_;_;_;_;_;_;_}: _ = unit {}
case(a, b, c, d) {
x0 = byte {1;1;0;a;b;c;d;_}
a || b || c || d
}: {
x1: byte
case x1 = byte {1;0;_;_;_;_;_;_}: _ = unit {}
}
case(a, b, c, d) x0 = byte {1;1;1;0;a;b;c;d}: {
x1: byte
x2: byte
case(e) {
x1 = byte {1;0;e;_;_;_;_;_}
x2 = byte {1;0;_;_;_;_;_;_}
a || b || c || d || e
}: _ = unit {}
}
case(a, b, c) x0 = byte {1;1;1;1;0;a;b;c}: {
x1: byte
x2: byte
x3: byte
case(d, e) {
x1 = byte {1;0;d;e;_;_;_;_}
x2 = byte {1;0;_;_;_;_;_;_}
x3 = byte {1;0;_;_;_;_;_;_}
a || b || c || d || e
}: _ = unit {}
}
default:
_: void
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment