0

Here is my original code.

let rec reverse l =
   match l with 
   | [] -> []
   | (h::t) -> (reverse t) :: h
PatJ
  • 5,996
  • 1
  • 31
  • 37
AndroidNewbie
  • 25
  • 8

1 Answers1

3

The cons :: operator takes an element as left-hand argument and a list as right-hand argument. Here, you do the opposite which does not work.

The right way to add an element at the element at the end of a list is to use list concatenation:

let rec reverse l =
  match l with
  | [] -> []
  | h :: t -> (reverse t) @ [h]

That code is not optimal though, and you may want to make it tail recursive.

PatJ
  • 5,996
  • 1
  • 31
  • 37
  • How would one go about making this function tail recursive? I do not really understand the concept of tail recursion yet since I just started using Ocaml – AndroidNewbie Feb 17 '15 at 01:55
  • Well, the idea of tail recursion is that the recursive calls of your function will always be the "last" action executed by your function. to speak in C terms, your calls to the function are always in the form `return myfun ()`. Here the last call of your function is to `@`. Tail-recursion is often allowed by adding an "accumulator" argument to your function that will store your intermediate result and be returned by your terminal cases (here the terminal case is `[]`). – PatJ Feb 17 '15 at 02:01
  • You can lookup this question: http://stackoverflow.com/questions/33923/what-is-tail-recursion – PatJ Feb 17 '15 at 02:02
  • Not being tail-recursive is not the worst offender for the `reverse` function proposed. Its main problem is its quadratic complexity in the size of its argument. The tail-recursive version is linear. – byako Feb 17 '15 at 22:14