let is_nil(lst)  { case lst | Nil        => True | else => False };
let is_cons(lst) { case lst | Cons(x,xs) => True | else => False };
let head(lst)    { case lst | Cons(x,xs) => x  };
let tail(lst)    { case lst | Cons(x,xs) => xs };

let nth(lst,i) {
  if i == 0 then
    head(lst)
  else
    nth(tail(lst), i-1)
};

let length(lst) {
  case lst
  | Nil        => 0
  | Cons(x,xs) => 1 + length(xs)
};

let sum(lst) {
  case lst
  | Nil        => 0
  | Cons(x,xs) => x + sum(xs)
};

let map(f, lst) {
  case lst
  | Nil        => Nil
  | Cons(x,xs) => Cons(f(x), map(f, xs))
};

let fold(f, acc, lst) {
  case lst
  | Nil        => acc
  | Cons(x,xs) => fold(f, f(acc, x), xs)
};

let foldr(f, acc, lst) {
  case lst
  | Nil        => acc
  | Cons(x,xs) => f(x, foldr(f, acc, xs))
};

let reverse(lst) {
  let iter(lst, result) {
    case lst
    | Nil        => result
    | Cons(x,xs) => iter(xs, Cons(x,result))
  };
  iter(lst, Nil)
};

let foldr2(f, acc, lst) {
  let g(x,y) { f(y,x) };
  fold(g, acc, reverse(lst))
};