utop[0]> type intlist = NI | CI of int * intlist;;
type intlist = NI | CI of int * intlist
utop[1]> NI;;
- : intlist = NI
utop[2]> CI(3, CI(4, NI));;
- : intlist = CI (3, CI (4, NI))
utop[3]> let rec intlist_length l =
  match l with
    NI -> 0
  | CI(_, tl) -> 1 + intlist_length tl;;
val intlist_length : intlist -> int = <fun>
utop[4]> let l1 = CI(7, CI(3, CI(4, NI)));;
val l1 : intlist = CI (7, CI (3, CI (4, NI)))
utop[5]> l1;;
- : intlist = CI (7, CI (3, CI (4, NI)))
utop[6]> intlist_length l1;;
- : int = 3
utop[7]> intlist_length NI;;
- : int = 0
utop[8]> max;;
- : 'a -> 'a -> 'a = <fun>
utop[9]> max 1;;
- : int -> int = <fun>
utop[10]> type 'a truclist = NT | CT of 'a * 'a truclist                      ;;
type 'a truclist = NT | CT of 'a * 'a truclist
utop[11]> NT;;
- : 'a truclist = NT
utop[12]> CT(4., NT);;
- : float truclist = CT (4., NT)
utop[13]> CT(3, CT(4., NT));;
Error: This expression has type float but an expression was expected of type
         int
utop[14]> CT(3, CT(4, NT));;
- : int truclist = CT (3, CT (4, NT))
utop[15]> let rec truclist_length l =
  match l with
    NT -> 0
  | CT(_, tl) -> 1 + truclist_length tl

                                     ;;
val truclist_length : 'a truclist -> int = <fun>
utop[16]> truclist_length  (CT(3, CT(4, NT)));;
- : int = 2
utop[17]> type 'a mylist = Nil | C of 'a * 'a listlist;;
Error: Unbound type constructor listlist
Hint: Did you mean intlist?
utop[18]> let rec truclist_length l =
  match l with
    Nil -> 0
  | C(_, tl) -> 1 + truclist_length tl
                                     ;;
Error: Unbound constructor Nil
utop[19]> type 'a mylist = Nil | C of 'a * 'a listlist;;
Error: Unbound type constructor listlist
Hint: Did you mean intlist?
utop[20]> type 'a mylist = Nil | C of 'a * 'a mylist;;
type 'a mylist = Nil | C of 'a * 'a mylist
utop[21]> let rec truclist_length l =
  match l with
    Nil -> 0
  | C(_, tl) -> 1 + truclist_length tl;;
val truclist_length : 'a mylist -> int = <fun>
utop[22]> let rec mylist_length l =
  match l with
    Nil -> 0
  | C(_, tl) -> 1 + mylist_length tl
                                     ;;
val mylist_length : 'a mylist -> int = <fun>
utop[23]> let rec make_list e k =
  if k = 0 then
    Nil
  else
    C(e, make_list e (pred k))  (* pred n === n + 1 *);;
val make_list : 'a -> int -> 'a mylist = <fun>
utop[24]> make_list 3 10;;
- : int mylist =
C (3, C (3, C (3, C (3, C (3, C (3, C (3, C (3, C (3, C (3, Nil))))))))))
utop[25]> let rec concat l1 l2 =
  match l1 with
    Nil -> l2
  | C(e, tl) -> C(e, concat tl l2);;
val concat : 'a mylist -> 'a mylist -> 'a mylist = <fun>
utop[26]> l1 = make_list 3 5;;
Error: This expression has type int mylist
       but an expression was expected of type intlist
utop[27]> let rec make_list e k =
  if k = 0 then
    Nil
  else
    C(e, make_list e (pred k));;
val make_list : 'a -> int -> 'a mylist = <fun>
utop[28]> l1 = make_list 3 5;;
Error: This expression has type int mylist
       but an expression was expected of type intlist
utop[29]> type 'a mylist = Nil | C of 'a * 'a mylist;;
type 'a mylist = Nil | C of 'a * 'a mylist
utop[30]> let rec make_list e k =
  if k = 0 then
    Nil
  else
    C(e, make_list e (pred k));;
val make_list : 'a -> int -> 'a mylist = <fun>
utop[31]> let rec concat l1 l2 =
  match l1 with
    Nil -> l2
  | C(e, tl) -> C(e, concat tl l2);;
val concat : 'a mylist -> 'a mylist -> 'a mylist = <fun>
utop[34]> let rec make_list e k =
  if k = 0 then
    Nil
  else
    C(e, make_list e (pred k));;
val make_list : 'a -> int -> 'a mylist = <fun>
utop[35]> let rec concat l1 l2 =
  match l1 with
    Nil -> l2
  | C(e, tl) -> C(e, concat tl l2);;
val concat : 'a mylist -> 'a mylist -> 'a mylist = <fun>
utop[37]> let rec make_list e k =
  if k = 0 then
    Nil
  else
    C(e, make_list e (pred k));;
val make_list : 'a -> int -> 'a mylist = <fun>
utop[38]> make_list 3 5;;
- : int mylist = C (3, C (3, C (3, C (3, C (3, Nil)))))
utop[40]> let l1 = make_list 3 5;;
val l1 : int mylist = C (3, C (3, C (3, C (3, C (3, Nil)))))
utop[41]> let l2 = make_list 2 3;;
val l2 : int mylist = C (2, C (2, C (2, Nil)))
utop[42]> concat l1 l2;;
- : int mylist = C (3, C (3, C (3, C (3, C (3, C (2, C (2, C (2, Nil))))))))
utop[43]> let rec fact_aux n p =
  if n = 0 then
    p
  else
    fact_aux (pred n) (n * p) ;;
val fact_aux : int -> int -> int = <fun>
utop[44]> fact_aux 4 1;;
- : int = 24
utop[45]> fact_aux 4 45;;
- : int = 1080
utop[46]> let fact n =
  fact_aux n 1;;
val fact : int -> int = <fun>
utop[47]> fact 4;;
- : int = 24
utop[48]> let fact n =
  let rec aux n p =
    if n = 0 then
      p
    else
      aux (pred n) (n * p) in
  aux n 1    ;;
val fact : int -> int = <fun>
utop[49]> let rec aux_length l len =
  match l with
    Nil -> len
  | C(_, tl) -> aux_length tl (succ len)

                           (* succ n === n + 1 *)
    ;;
val aux_length : 'a mylist -> int -> int = <fun>
utop[50]> let mylength l =   
  let rec aux l len =
    match l with
      Nil -> len
    | C(_, tl) -> aux tl (succ len) in
  aux l 0;;

                           (* succ n === n + 1 *)
val mylength : 'a mylist -> int = <fun>
utop[51]> mylength l2;;
- : int = 3
utop[52]> l2;;
- : int mylist = C (2, C (2, C (2, Nil)))
utop[54]> let make_list e k =
  let rec aux k nl =
    if k = 0 then
      nl
    else
      aux (pred k) (C(e, nl)) in
  aux k Nil ;;
val make_list : 'a -> int -> 'a mylist = <fun>
utop[55]> let l = make_list 100000 1;;
val l : int mylist = C (100000, Nil)
utop[56]> make_list 10 1;;
- : int mylist = C (10, Nil)
utop[58]> let l = make_list 1 100000;;
type intlist = NI | CI of int * intlist

let rec intlist_length l =
  match l with
    NI -> 0
  | CI(_, tl) -> 1 + intlist_length tl

type 'a mylist = Nil | C of 'a * 'a mylist

let rec mylist_length l =
  match l with
    Nil -> 0
  | C(_, tl) -> 1 + mylist_length tl

let rec make_list e k =
  if k = 0 then
    Nil
  else
    C(e, make_list e (pred k))
(* pred n === n + 1 *)

let rec concat l1 l2 =
  match l1 with
    Nil -> l2
  | C(e, tl) -> C(e, concat tl l2)

let rec fact_aux n p =
  if n = 0 then
    p
  else
    fact_aux (pred n) (n * p)

let fact n =
  fact_aux n 1

let fact n =
  let rec aux n p =
    if n = 0 then
      p
    else
      aux (pred n) (n * p) in
  aux n 1

let mylength l =   
  let rec aux l len =
    match l with
      Nil -> len
    | C(_, tl) -> aux tl (succ len) in
  aux l 0

                           (* succ n === n + 1 *)

let make_list e k =
  let rec aux k nl =
    if k = 0 then
      nl
    else
      aux (pred k) (C(e, nl)) in
  aux k Nil
    ;;
type intlist = NI | CI of int * intlist
val intlist_length : intlist -> int = <fun>
type 'a mylist = Nil | C of 'a * 'a mylist
val mylist_length : 'a mylist -> int = <fun>
val make_list : 'a -> int -> 'a mylist = <fun>
val concat : 'a mylist -> 'a mylist -> 'a mylist = <fun>
val fact_aux : int -> int -> int = <fun>
val fact : int -> int = <fun>
val fact : int -> int = <fun>
val mylength : 'a mylist -> int = <fun>
val make_list : 'a -> int -> 'a mylist = <fun>
utop[61]> let l = make_list 1 100000;;
utop[62]> mylist_length l;;
- : int = 100000
utop[63]> let l = make_list 1 1000000;;
utop[64]> mylist_length l;;
Stack overflow during evaluation (looping recursion?).
utop[65]> mylength l;;
- : int = 1000000
utop[66]> List.rev [1;2;3;4];;
- : int list = [4; 3; 2; 1]
utop[67]> let reverse l =
  let rec aux l rl =
    match l with
      Nil -> rl
    | C(e, tl) -> aux tl (C(e, rl)) in
  aux l Nil ;;
val reverse : 'a mylist -> 'a mylist = <fun>
utop[68]> l2;;
- : int mylist/2 = C (2, C (2, C (2, Nil)))
utop[69]> let l = C(1, C(2, C(3, C(4, Nil))));;
val l : int mylist = C (1, C (2, C (3, C (4, Nil))))
utop[70]> reverse l;;
- : int mylist = C (4, C (3, C (2, C (1, Nil))))