Writing a list append function in OCaml

Question

I've defined a custom list type as part f a homework exercise.

type 'a myType =
  | Item of ('a * 'a myType)
  | Empty;;

I've already done 'length' and now I need a 'append' function. My length function:

let length l =
  let rec _length n = function
    | Empty         -> n
    | Item(_, next) -> _length (n + 1) next
  in _length 0 l;;

But I really don't know how to make the append function.

let append list1 list2 = (* TODO *)

I can't use the list module so I can't use either :: or @.

Answer 1

I guess my comments are getting too lengthy to count as mere comments. I don't really want to answer, I just want to give hints. Otherwise it defeats the purpose.

To repeat my hints:

a. The second parameter will appear unchanged in your result, so you can just spend your time worrying about the first parameter.

b. You first need to know how to append something to an empty list. I.e., you need to know what to do when the first parameter is Empty.

c. You next need to know how to break down the non-empty case into a smaller append problem.

If you don't know how to create an item, then you might start by writing a function that takes (say) an integer and a list of integers and returns a new list with the integer at the front. Here is a function that takes an integer and returns a list containing just that one integer:

let list1 k =
    Item (k, Empty)

One way to think of this is that every time Item appears in your code, you're creating a new item. Item is called a constructor because it constructs an item.

I hope this helps.