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.
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