(*
  One way of representing nonnegative integers is called “Peano numerals” and we define
  the type of a peano numeral as follows:
  datatype 'a peano = C of ('a -> 'a) * 'a -> 'a
  We can think of a peano numeral as a function that is applied to some base number n
  times. For example:
   0 is represented as ZERO = C(fn (f,x) => x)
   1 is represented as ONE = C(fn (f,x) => f(x))
   2 is represented as TWO = C(fn (f,x) => f(f(x)))
   ...
*)

datatype 'a peano = C of ('a -> 'a) * 'a -> 'a;

(* 2.1

  Write a function create:int -> 'a peano which when given an integer it will
  generate a peano numeral. Ensure that the resulting peano numeral you return
  does not contain any calls to the function create.
*)

(* create:int -> 'a peano *)

fun create(n) =
    let
    fun create'(0) = (fn (f,x) => x)
          | create'(n) = (fn (f,x) => f(create'(n-1) (f, x)))
    in
    C(create'(n))
    end

(* 2.2

  Write a function peanoToInt which accepts a peano numeral as input and converts
  it into an integer.
*)

(* peanoToInt: [__] peano -> int *)
(* note the [__] will not necessarily be 'a *)

(* Also note, writing code of the form

  val pn = create(42);
  peanoToInt( pn );

may not work.
You should, however, be able to write

  peanoToInt(create(42));

or
  let
      val pn = create(42)
  in
      peanoToInt(pn)
  end
*)

fun peanoToInt(p) = p (fn x => x+1, 0)