bst_topk.if

data Tree = Empty | Node { value, left, right };

extern fn append(a, b) explain { Concatenates two lists. };
extern fn take_k(xs, k) explain { Returns first k items from list. };

fn insert(t, x) =
  match t {
    Empty => Node { value: x, left: Empty, right: Empty };
    Node { value, left, right } =>
      if x < value {
        Node {
          value,
          left: insert(left, x),
          right
        }
      } else {
        Node {
          value,
          left,
          right: insert(right, x)
        }
      };
  };

fn to_desc_list(t) =
  match t {
    Empty => [];
    Node { value, left, right } => append(to_desc_list(right), append([value], to_desc_list(left)));
  };

fn topk(t, k) =
  t
    |> to_desc_list
    |> take_k(k);

Empty
  |> insert(5)
  |> insert(2)
  |> insert(8)
  |> insert(1)
  |> insert(3)
  |> insert(7)
  |> topk(3)