module type Functor = sig
  type 'a t
  val map : ('a -> 'b) -> ('a t -> 'b t)
end

module Mu (F : Functor) : sig
  type t = { mu : t F.t }
  val cata : ('a F.t -> 'a) -> (t -> 'a)
end = struct
  type t = { mu : t F.t }
  let rec cata phi t = phi (F.map (cata phi) t.mu)
end

module ListF (T : sig type a end) = struct
  type 'a t = Nil | Cons of T.a * 'a
  let map f = function
    | Nil -> Nil
    | Cons (x, a) -> Cons (x, f a)
end

module MuList (T : sig type a end) = struct
  module ListA = ListF (T)
  module Base = Mu (ListA)
  include Base

  let of_list l s =
    let cons hd tl = { mu = ListA.Cons (hd, tl) } in
    let nil        = { mu = ListA.Nil } in
    List.fold_right cons s nil

  let to_list =
    cata begin function
      | ListA.Nil -> []
      | ListA.Cons (hd, tl) -> hd :: tl
    end
end