Record Add List Function in OCaml

Question

I defined a custom list type as part of f for homework.

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

I already made a "length", and now I need the "add" 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 cannot use the list module, so I cannot use either :: or @ .

Answer 1

I think my comments are too long to be considered just comments. I do not want to answer, I just want to give hints. Otherwise, it will defeat the goal.

Repeat my prompts:

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

b. First you need to know how to add something to an empty list. Ie, you need to know what to do when the first parameter is empty.

from. Then you need to know how to break a non-empty case into a smaller problem adding.

If you don’t know how to create an element, you can start by writing a function that takes (say) an integer and a list of integers and returns a new list with an integer. Here is a function that takes an integer and returns a list containing only one integer:

 let list1 k = Item (k, Empty) 

One way to think that every time Item appears in your code is to create a new element. Item is called a constructor because it creates an element.

Hope this helps.

Answer 2

Your structure is a list, so you should start by defining the nil value, which is an empty list, and the cons head tail function, which adds the head element in front of the tail list.

Another tip: sometimes it helps to start with a simple example and try to do it manually, i.e. decompose what you want to do in simple operations that you do yourself. Then you can summarize and write code ...