CODEWITHSUNDEEP
ocaml
Anatoliy Sokolov
Anatoliy Sokolov

Reputation: 397

I need to make an @ using cons in OCAML

My teacher says we cant use appends @ in our program so im going to write my own recursive function for it.

Here is what i have so far:

(my own appends function)

let rec appends a b = 
    match a with
    | [] -> b
    | hd::[]-> hd::b
    | hd::tl-> (what i need help on)
    ;;

im not sure how to add just the last element of a to b if a is a list with multiple elements and then call appends on the first part since you can only remove the first element of a list with the :: any advice would be appreciated

Upvotes: 0

Views: 176

Answers (2)

Chris
Chris

Reputation: 36680

Late answer, but consider that [1; 2; 3] is a syntactic convenience for 1 :: 2 :: 3 :: []. If you wanted to append [4; 5; 6] to [1; 2; 3] you need to replace the [] with [4; 5; 6].

You need to turn append [1; 2; 3] [4; 5; 6] into 1 :: 2 :: 3 :: [4; 5; 6].

If I just wanted to write an identity function for a list, it'd look like:

let rec list_id lst =
  match lst with
  | [] -> []
  | x::xs -> x :: list_id xs

Now, you just need to pass in a second list, and have the base case return that instead. A locally scoped recursive function with access to b solves this nicely.

let append a b =
  let rec aux = function
    | [] -> b
    | x::xs -> x :: aux xs
  in
  aux a

Upvotes: 0

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

Something that might help is to think more functionally, i.e., to think of the code as a definition of what it means in principle to append two lists. This is as opposed to thinking of the code as a set of actions to be performed. Sometimes this helps, especially when coding in a functional language.

So, your first case says: if a is empty, the result of appending a and b is just b itself.

Your second case says: if a is a list of one element hd, the result of appending a and b is a list that consists of hd added to the beginning of b.

You're looking for a general definition for appending that works for any non-empty list a. The key insight is that your definition can be recursive, i.e., it can use your appends function.

So here is a proposed definition: if a is a list whose head is hd and whose tail is tl, the result of appending a and b is a list whose head is hd and whose tail is tl appended to b.

(This in fact gives the whole thing away. I hope it doesn't spoil the exercise for you.)

Upvotes: 2

Related Questions