Limit recursion to the first three elements of list of floats

Question

I'm new to functional programming (ReasonML / OCaml).

I have a list of floats. I want to get the first three non-zero items of a list and no more. Items can be positive, negative, and zero.

How can recursion be limited until the first three non-zero floats are extracted?

I was thinking of doing something like:

switch (list) {
  | [first, second, third, ...rest] => (first +. second +. third) /. 3.0
  | _ => 0.0
};

But how can I guarantee that first, second, and third are non-zero floats? And if they are, discard them recursively until three non-zero floats are found -- or return 0.0.

Answer 1

A nicer way to do this using recursion is to make it more generic: instead of finding the 3 first non-zero, let's find the n first non-zero.

Below is an OCaml implementation, I don't know Reason.

let rec find_n l n ~f =
  if n = 0 then []
  else match l with
  | [] -> failwith "Cannot find enough items"
  | h::t ->
      if f h then
        h :: (find_n t (n-1) ~f)
      else
        find_n (t n ~f)

Here's the function's signature:

val find_n : 'a list -> int -> f:('a -> bool) -> 'a list = <fun>

There's a lot going on here, but it's not that bad. The logic here is the following:

If I want 3 items from a list:

• If its head matches, then I need to look for 2 items in the tail.
• Else, then I still need to look for 3 items in the tail.

Everything else is just additional logic:

• If I'm looking for 0 items, I'm done.
• If the list is empty and I still need to look for more items, I failed.

A word about tail-recursion

Unfortunately, the above implementation is not tail-recursive, which means it will fail on large lists. A common technique to make a function tail-recursive is to use an accumulator (acc in the code below) to store the intermediate result.

Then, we encapsulate this extra logic in a local helper function (often called loop or aux) so that the accumulator doesn't show up in the function's signature.

let find_n l n ~f =
  let rec loop l' n' acc =
    if n' = 0 then acc else
      match l' with
      | [] -> failwith "Cannot find enough items"
      | h::t ->
          if f h then
            loop t (n' - 1) (h::acc)
          else
            loop t n' acc
  in
  loop l n []

Answer 2

Got it!

List.filer can be used to filter out elements equal to zero.

let filtered = List.filter (fun item => item != 0.0) list;
switch (filtered) {
  | [first, second, third, ...rest] => (first +. second +. third) /. 3.0
  | _ => 0.0
};