Help declaring some functions

Learning
1

I just started learning OCaml but have a hard time understanding the “basics”. I have got some training examples where I am supposed to create the following functions but I have no clue of how to even start. Could anyone help me declare a few of them to see if I get the hang of it. We are not supposed to use any built-in library like List or similar.

I think I could figure out the cons, empty and length but the rest is a mystery to me.

val first: 'a my_list -> 'a /return the first element of a list.
val last: 'a my_list -> 'a /return the last element of a list.
val rest: 'a my_list -> 'a my_list //return everything but the first element in a list.
val cons: 'a -> my_list -> 'a my_list

val empty: 'a my_list -> bool
val length: 'a my_list -> int

val map: ('a -> 'b) -> 'a my_list -> 'b my_list /create the map function using the previously created functions
val fold: ('b -> 'a -> 'a) -> 'a -> 'b my_list -> 'a
val append: 'a my_list -> 'a my_list -> 'a my_list

val as_list 'a my_list -> 'a list
val from_list 'a list -> 'a my_list

2

Most of these are covered in OCaml from the very beginning (and its exercises), which I can wholeheartedly recommend - it was the book that helped me get started.

You didn’t give us the type declaraction for your my_list, which makes it slightly tricky to help you write functions using it. I’ll assume it’s something like:

type 'a my_list = Nil | Node of 'a * 'a my_list

It sounds like you may want to read up on “pattern matching.”

val first: 'a my_list -> 'a   (* return the first element of a list.*)

let first = function
  | Nil -> failwith "throw an exception because the list has no elements"
  | Node (a, ignore_the_rest) -> a

The above will throw an exception if the list is empty. You might want to change your interface to be:

val first: 'a my_list -> 'a option
(** [first lst] returns [Some] the first element of [lst], or [None] if the list is empty. *)

let first = function
  | Nil -> None
  | Node ( a, _ ) -> Some a (* the _ is a wildcard which also means "throw this away *)

val last: 'a my_list -> 'a

let rec last = function
  | Nil -> None
  | Node (a, Nil) -> Some a
  | Node ( _ , remainder) -> last remainder (* call the function again with the next part *)

val rest: 'a my_list -> 'a my_list

For this one you can do pattern matching very similar to the first function.

val map: ('a -> 'b) -> 'a my_list -> 'b my_list

Here you’ll want to write a nested recursive function with an “accumulator”, a technique used to accumulate the result of your chain of recursive function calls. Your accumulator will be created using your cons, starting with a Nil list, adding the result of calling the ('a -> 'b) function on each value taken from the 'a list (which you can be split using your first and last).
When you have made the new accumulator, the function can call itself again, until it is finished.

Note that the above will give you the reversed list of results, but you can get around that by calling your inner function again with a (fun x -> x) to get the “reverse of the reverse.” (== the correct order).

You’ll also need to know the length of the list and make sure you don’t call first or last on an empty list, since that will crash with an exception. This last bit can be avoided by using the option type as return value for those functions, as I outlined above.

fold is much the same, except that you set the “accumulator” ('a) to the result of the provided function applied with the value from the list and the old accumulator - instead of constructing a new list of results.

val append: 'a my_list -> 'a my_list -> 'a my_list

You can use last and cons here if you write a function that return “everything but the last”. That would be kind of like map, but with a special case for the last non-nil element.

val as_list 'a my_list -> 'a list

Here you can use fold_left using List.cons.

 val from_list 'a list -> 'a my_list

Here you can also use pattern matching, using :: to deconstruct the list while constructing your list. Then something like the inner function of your map function to reverse it.

Note that none of these proposed solutions are particularly performant, but they are probably the conceptually easiest.

3

Thanks for the answer, the my_list declaration looks like this if it makes any difference:

type 'a my_list =
| Empty
| Cons of 'a list_content
and
'a list_content = { data: 'a; next: 'a my_list }

4

That doesn’t change a lot, you just have to adapt your pattern matching. Example with first and last:

let first = function
  | Empty -> failwith "first: the list is empty"
  | Cons {data; _  } -> data

let rec last = function
  | Empty -> failwith "last: the list is empty"
  | Cons {data; next=Empty} -> data
  | Cons {next; _} -> last next