CODEWITHSUNDEEP
listocaml
K1ng0e
K1ng0e

Reputation: 43

Writing a list append function in OCaml

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 @.

Upvotes: 4

Views: 1956

Answers (2)

Fabrice Le Fessant
Fabrice Le Fessant

Reputation: 4274

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

Another advice: sometimes, it helps a lot to start by taking a simple example, and trying to do it manually, i.e. decomposing what you want to do in simple operations that you do yourself. Then, you can generalize and write the code...

Upvotes: 2

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66818

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.

Upvotes: 8

Related Questions