use "basic_models.g";

struct node<T> where { DefaultConstructible<T>, Regular<T> }
{
  node<T>* next;
  T data;
};

fun cons<T> where { DefaultConstructible<T>, Regular<T> }
(T x, node<T>* n) -> node<T>*@ {
  return new node<T>{data = x, next = n};
}
fun free_list<T> where { DefaultConstructible<T>, Regular<T> }
(node<T>* n) {
  if (n != cast<node<T>*>(nullptr)) {
    free_list(n->next);
    delete n;
  }
}


fun map<T,U> where { DefaultConstructible<T>, Regular<T>,
                     DefaultConstructible<U>, Regular<U> }
((fun(T)->U@) f, node<T>* n) -> node<U>*@ {
  if (n == cast<node<T>*>(nullptr))
    return nullptr;
  else
    return cons(f(n->data), map(f, n->next));
}

fun add1(int x) -> int@ { return x + 1; }


fun main() -> int@ {
  let ls1 = cons(0, cons(1, cons(2, cast<node<int>*>(nullptr))));
  let ls2 = map(add1, ls1);
  let x = (*ls2).data - 1;
  free_list(ls1);
  free_list(ls2);
  return x;
}