(* Non-empty lists *)
type 'a listx =
  | Nil of 'a
  | Cons of ('a * 'a listx)

let rec fold_left f acc l =
  match l with
  | Nil x -> f acc x
  | Cons (x, l') -> fold_left f (f acc x) l'

let hd =
 function
  | Nil x
  | Cons (x,_) -> x

let rec map f =
  function
  | Nil x -> Nil (f x)
  | Cons (x, l') -> Cons (f x, map f l')

let rec append l =
  function
  | Nil x -> Cons (x, l)
  | Cons (x, l') -> Cons (x, append l l')

let rec length = function
  | Nil _ -> 1
  | Cons (_, xs) -> 1 + (length xs)

let rec assoc x = function
  | Nil (y,t)
  | Cons ((y,t),_) when x=y -> t
  | Nil _ -> raise Not_found
  | Cons (_,l) -> assoc x l

let rec to_list =
 function
    Nil x -> [x]
  | Cons (x,l) -> x::to_list l

let rec from_list =
 function
    [] -> raise (Failure "from_list: empty list")
  | [x] -> Nil x
  | x::l -> Cons(x,from_list l)

let rec split_nth n l =
 match n,l with
    0,_ -> []
 | 1,Nil x -> [x]
 | n,Cons (hd,tl) -> hd::split_nth (n-1) tl
 | _,_ -> raise (Failure "split_nth: not enough args")

let rec max =
  function
  | Nil x -> x
  | Cons (x, l) -> Pervasives.max x (max l)

let rec last =
  function
  | Nil x -> x
  | Cons (_, l) -> last l
(*
let rec nth i l = match l, i with
 | Cons (x, _), 1  -> x
 | _, n when n <= 0 -> raise (Invalid_argument "Listx.nth")
 | Cons (_, xs), n -> nth (n-1) xs
 | Nil x, 1        -> x
 | Nil _, _        -> raise (Invalid_argument "Listx.nth")
;;
*)