skew_heap.py

# Haskell-inspired functional skew heap in Python employing Scott-encoded sum types
# Inspired by <https://doisinkidney.com/posts/2019-10-02-what-is-good-about-haskell.html>

# data Maybe a = Nothing | Just a
nothing = lambda f_nothing, f_just: f_nothing()
just = lambda x: lambda f_nothing, f_just: f_just(x)

# data List a = Nil | Cons a (List a)
nil = lambda f_nil, f_cons: f_nil()
cons = lambda x, xs: lambda f_nil, f_cons: f_cons(x, xs)

# data Pair a b = Pair a b
pair = lambda x, y: lambda f: f(x, y)

# data Tree a = Leaf | Node a (Tree a) (Tree a)
leaf = lambda f_leaf, f_node: f_leaf()
node = lambda x, l, r: lambda f_leaf, f_node: f_node(x, l, r)

# foldr f a xs = case xs of
#     Nil -> a
#     Cons x ys -> f x (foldr f a ys)
def foldr(f, a, xs):
    return xs(
        lambda: a,
        lambda x, ys: f(x, foldr(f, a, ys)))

# unfoldr f a = case f a of
#     Nothing -> Nil
#     Just p -> case p of
#         Pair x b ->
#             Cons x (unfoldr f b)
def unfoldr(f, a):
    return f(a)(
        lambda: nil,
        lambda p: p(lambda x, b:
            cons(x, unfoldr(f, b))))

# merge xs ys = case xs of
#     Leaf -> ys
#     Node x xl xr -> case ys of
#         Leaf -> xs
#         Node y yl yr ->
#             if x <= y
#             then Node x (merge ys xr) xl
#             else Node y (merge xs yr) yl
def merge(xs, ys):
    return xs(
        lambda: ys,
        lambda x, xl, xr: ys(
            lambda: xs,
            lambda y, yl, yr:
                node(x, merge(ys, xr), xl) if x <= y else
                node(y, merge(xs, yr), yl)))

# popMin tree = case tree of
#     Leaf -> Nothing
#     Node x xl xr -> Just (x, merge xl xr)
def popMin(tree):
    return tree(
        lambda: nothing,
        lambda x, xl, xr: just(pair(x, merge(xl, xr))))

# insert x tree = merge (Node x Leaf Leaf) tree
def insert(x, tree):
    return merge(node(x, leaf, leaf), tree)

# listToHeap elements = foldr insert Leaf elements
def listToHeap(elements):
    return foldr(insert, leaf, elements)

# heapToList tree = unfoldr popMin tree
def heapToList(tree):
    return unfoldr(popMin, tree)

def fromIter(elements):
    i = iter(elements)
    try:
        return cons(next(i), fromIter(i))
    except StopIteration:
        return nil

def toIter(xs):
    def yielding(x, y):
        yield x
        return y
    while xs is not None:
        xs = yield from xs(lambda: iter(()), yielding)

def treeRepr(tree):
    return tree(
        lambda: "leaf",
        lambda x, l, r:
            "node(" + repr(x) + ", " + treeRepr(l) + ", " + treeRepr(r) + ")")

t1 = listToHeap(fromIter([3, 5, 7]))
t2 = listToHeap(fromIter([2, 6, 8]))
t3 = merge(t1, t2)

print(treeRepr(t1))
print(treeRepr(t2))
print(treeRepr(t3))
print(list(toIter(heapToList(t3))))