CODEWITHSUNDEEP
ocaml
Erik Hansson
Erik Hansson

Reputation: 5

Explain efficient list reversal recursively

(* val rev : ’a list -> ’a list -> ’a list *)

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

Could some one please tell me what happens here recursively? Also, why are two arguments l and r used in the code?

Let's say I want to reverse [1;2;3] how does the function reverse is to 3,2,1?

  rev [1;2;3] []

Upvotes: 0

Views: 803

Answers (2)

Pandemonium
Pandemonium

Reputation: 8390

What's with the r

Going into detail, let's start with a function without r (accumulator):

let rec rev l =
  match l with
    [] -> l
  | h :: t -> rev t @ [h]

What is inefficient here is not just because it's not tail-recursive (which I won't cover in detail; see the link below), but also because you have to append an element [h] to the end of every reversed sublist on every call. In Ocaml, appending to a list is inefficient compared to prepending to it, because a list is a just a singly-linked list, which you only have access to the head's pointer.

Prepending a new element to the head of the list requires only a newly created element to create a pointer to the previous head element and returning a newly created list with that new element as the head. This is only an O(1) operation.

Appending an element to the list, however, incurs an O(N) complexity because you have to traverse to the end of the list before creating a new pointer for the last element to point to the new element. If you have a list of length N where N is a huge number, O(N) is pretty bad.

With an accumulator (r), you are "accumulating" or modifying a state and passing into the next function call. This is the basis of tail-recursion but also avoid the above pitfall. To see what it really does, see the pseudocode below.

What the recursive function does

Here is a visual representation of what happens as the recursive operation goes on (first argument being l and second being r).

(* pseudocode *)
(* while List.length l <> 0 *)

rev [1; 2; 3; 4] []
rev [2; 3; 4] (1 :: [])
rev [3; 4] (2 :: [1])
rev [4] (3 :: [2; 1])
rev [] (4 :: [3; 2; 1])

(* List.length l = 0 *)
return [4; 3; 2; 1]

In practice, you might want to create an inner "helper" function that takes care of the recursive heavy-lifting and leave the outer function simply as a user-friendly, single-arity API.

let rev l =
  let rec helper l' r =
    match l' with
      [] -> r
    | (h::t) -> helper t (h::r)
  in helper l []

this article on recursion I wrote might help you understand tail-recursion better.

Upvotes: 2

trivelt
trivelt

Reputation: 1965

This function is recursive because there is a call of rev inside itself. r parameter is here so called accumulator - thanks to it this function is tail recursive.

How does it work in details?

  1. You call rev [1;2;3] [], so l=[1;2;3] and r=[]. L is matched with h::t - that means head and tail of the list. h=1, t=[2;3].
  2. Last call in the body of rev function is rev [2;3] [1]
  3. In the next call argument l is matched as previous, so rev is called with [3] [2;1]
  4. Last recursive call is rev [] [3;2;1]. L is matched with [] and r (=[3;2;1]) is returned.

Note that you can hide accumulator in the following way:

let rev l =
    let rec rev l r = match l with
        [] -> r
        | (h::t) -> rev t (h::r)
    in
    rev l []

Then you can use this function passing only one argument rev [1;2;3].

Upvotes: 1

Related Questions