list_concatenation.ml

type nil
(* heteregenous list with no concatenation *)
type 'list t =   
  | Nil: nil t
  | Cons: 'a * 'b t -> ('a -> 'b) t

(* concatenation helper *)
type (_,_, _ ) helper = 
 | Z : ( nil , 'e, 'e) helper
 | S: ('a,'b, 'e) helper -> ('c -> 'a, 'c  ->  'b, 'e) helper

let rec append: 
  type list1 list2 list. (list1, list, list2) helper -> list1 t -> list2 t -> list t =
  fun helper list1 list2 -> match list1, helper with
  | Cons (a, l), S h -> Cons(a, append h l list2)
  | Nil, Z -> list2

let l = Cons(1,Cons("hi", Nil) )
let l2 = Cons(2.5,Cons([0], Nil) )

let l3 = append (S (S Z) ) l l2