Access the element at a list with index

Question

In OCaml, I want to write a function that returns the element at a given index of a list. For example [4;5;6] 0 -> 4, [4;5;6] 1 -> 5. I know how to do this recursively, but can anyone show how to do this problem using fold_left or fold_right? Thank you so much!

Answer 1

Let's look at how you can print the elements in a list using fold_left.

let print lst =
  List.fold_left 
    (fun i x -> Format.printf "%d: %d\n" i x; i + 1) 
    0 lst;

The initial index of 0 is passed in as the initial value. Each time through we have the side effect of printing a line, and then update the initial value to i + 1.

Result:

# print [1;4;6;2;7];;
0: 1
1: 4
2: 6
3: 2
4: 7
- : int = 5

This shows us nicely how the fold updates its accumulator as it iterates through a list.

But if we're going to search for a value at an index, let's use a tuple of a current index and an option type for the return value, in case we don't find the index we're looking for.

let at idx lst = 
  List.fold_left 
    (fun i x ->
       match i with
       | (_, Some _)               -> i
       | (idx', _) when idx = idx' -> (idx', Some x)
       | (idx', _)                 -> (idx' + 1, None))
    (0, None)
    lst

We start with 0 and None as our initial value. For each item in the list we check to see if the option type value in the accumulator is Some _. We don't care about the value, but if it's not None we've found what we're looking for and do not need to update the accumulator.

If the accumulator does contain None and the current index is the same as the one we're looking for, update the accumulator with Some of the current value. The index does not need to be updated.

If the index is not the one we're looking for, increment the index and continue.

# at 3 [1;2;3;4;5];;
- : int * int option = (3, Some 4)

But since we don't need the first element in the tuple, we can use a let binding to name the result we are looking for and return that.

let at idx lst = 
  let (_, result) = List.fold_left 
    (fun i x ->
       match i with
       | (_, Some _)               -> i
       | (idx', _) when idx = idx' -> (idx', Some x)
       | (idx', _)                 -> (idx' + 1, None))
    (0, None)
    lst
  in
  result

Now:

# at 3 [1;2;3;4;5];;
- : int option = Some 4

Taking a look at how List.fold_left can be implemented may be instructive.

let rec fold_left f init lst =
  match lst with
  | []    -> init
  | x::xs -> fold_left f (f init x) xs

In at the Some _ condition in the accumulator tuple causes that accumulator value to propagate to the end of the fold without update.

---

Alternately we could use a local exception to break out of the fold immediately on finding the index we're looking for.

let at idx lst = 
  let exception Early_exit of int in
  try
    let (_, result) = List.fold_left 
      (fun i x ->
         match i with
         | (_, Some _)               -> i
         | (idx', _) when idx = idx' -> raise (Early_exit x)
         | (idx', _)                 -> (idx' + 1, None))
      (0, None)
      lst
    in
    result
  with Early_exit x -> Some x

Or perhaps a little bit more cleanly:

let at idx lst = 
  let exception Early_exit of int in
  match List.fold_left 
    (fun i x ->
       match i with
       | (_, Some _)               -> i
       | (idx', _) when idx = idx' -> raise (Early_exit x)
       | (idx', _)                 -> (idx' + 1, None))
    (0, None)
    lst with
  | (_, result)            -> result
  | exception Early_exit x -> Some x

Of course, we now know that if the exception Early_exit wasn't raised, the index wasn't found, so the result would always be None.

let at idx lst = 
  let exception Early_exit of int in
  match List.fold_left 
    (fun i x ->
       match i with
       | (_, Some _)               -> i
       | (idx', _) when idx = idx' -> raise (Early_exit x)
       | (idx', _)                 -> (idx' + 1, None))
    (0, None)
    lst with
  | _                      -> None
  | exception Early_exit x -> Some x

And testing:

# at 3 [1;2;3;4;5];;
- : int option = Some 4

But if we're using exceptions this way, we really don't need List.fold_left at all. We can just use List.iteri.

let at idx lst =
  let exception Found of int in
  try 
    List.iteri (fun i x -> if i = idx then raise (Found x)) lst;
    None 
  with Found x -> Some x

We can also make this work with a polymorphic function so that the list is not constrained to contain just int values.

let at (type a) idx lst =
  let exception Found of a in
  try 
    List.iteri (fun i x -> if i = idx then raise (Found x)) lst;
    None 
  with Found x -> Some x

Answer 2

Since all the other answers seem somewhat over-complicated, this is sufficient:

let at xs i =
  snd (List.fold_left
    (fun (i, y) x -> i - 1, if i = 0 then Some x else y)
    (i, None)
    xs
  )

Answer 3

You need some exit mechanism when the index element is found.

exception Value of int

let get_index_value_using_fold_left l i =
  let index_value = ref 0 in
  try
    List.fold_left
      (
        fun a e ->
          if !index_value = i
          then
            raise (Value e)
          else
            (
              index_value := !index_value + 1;
              a
            )
      ) None l
  with
  | Value ans -> Some ans

let ans = get_index_value_using_fold_left [11;2;13;4;15;6;17;8;19;20;] 2

let () =
  Option.iter (fun x -> Printf.printf "%d\n" x) ans

Answer 4

Both kinds of fold let you access the elements of a list in order while maintaining some state that you can choose freely. The difference is that fold_left starts at the beginning of the list and works toward the end and fold_right starts at the end of the list and works back toward the beginning.

Since your index starts at the beginning of the list I'd say it will be easier to work with fold_left.

So, your problem is to figure out some kind of state that you can maintain so that by the time you've looked at the whole list, you know what the nth element of the list was.

You can basically figure out the state from the problem: you need to know what element of the list you're looking at (so you know when you come to the nth one). You need to remember the nth element (if you've seen it already) so that it's available when you reach the end of the list. If you haven't seen the nth element yet you need something of the same type to use as a placeholder (or you could use an option type).

You need a function that takes state like this (along with one element of the list) and produces the state that goes with the next element of the list. This is really not so different from writing a loop, except that you need to pass the state explicitly as a parameter and return the new state as a result.