I'm working in OCaml and need to write a function

let rev lst = ...

which reverses the list lst without using recursion. I don't think I can use iterative methods either, like a for-loop. And I can't use List library functions. And I can't define some kind of data structure that allows me to interface with the elements in reverse order. It has to be a very from-bare-OCaml implementation.

Given these constraints I really can't think of any way to do this. I really don't even know where to start. The only two things in my bag of tricks, when dealing with arbitrary lists, are recursion and iteration.

CodePudding user response：

The only loophole I can see here is to define another function that uses recursion, and then have rev use it such that rev itself is not recursive. List.fold_left is easy enough to reimplement such that your rev function also doesn't use any functions from the List module. This should satisfy the requirements.

let rec foldl f i =
  function
  | [] -> i
  | x::xs -> foldl f (f i x) xs

And then rev:

let rev lst = foldl (fun i x -> x::i) [] lst

If you feel like being clever, you could reimplement Fun.flip as well, and create a cons function. Both simple enough.

let flip f a b = f b a

let cons a b = a :: b

let rev lst = foldl (flip cons) [] lst