How would I return a value from a function which iterates over a for loop in F#

Question

I am trying loop over an array and return a value as shown below. But this gives me an error on the line after the if statement. It says "This expression was expected to have type unit but has type int"

let findMostSignificantBitPosition (inputBits:System.Collections.BitArray) =
for i = inputBits.Length - 1 to 0  do
    if inputBits.[i] then
        i
done

How would I do this? I am in the middle of recoding this with a recursive loop, as it seems to be the more accepted way of doing such loops in functional languages, but I still want to know what I was doing wrong above.

Answer 1

for loops are not supposed to return values, they only do an operation a fixed number of times then return () (unit). If you want to iterate and finally return something, you may :

• have outside the loop a reference where you put the final result when you get it, then after the loop return the reference content

• use a recursive function directly

• use a higher-order function that will encapsulate the traversal for you, and let you concentrate on the application logic

The higher-function is nice if your data structure supports it. Simple traversal functions such as fold_left, however, don't support stopping the iteration prematurely. If you wish to support this (and clearly it would be interesting in your use case), you must use a traversal with premature exit support. For easy functions such as yours, a simple recursive function is probably the simplest.

In F# it should also be possible to write your function in imperative style, using yield to turn it into a generator, then finally forcing the generator to get the result. This could be seen as a counterpart of the OCaml technique of using an exception to jump out of the loop.

Edit: A nice solution to avoid the "premature stop" questions is to use a lazy intermediate data structure, which will only be built up to the first satisfying result. This is elegant and good scripting style, but still less efficient than direct exit support or simple recursion. I guess it depends on your needs; is this function to be used in a critical path?

Edit: following are some code sample. They're OCaml and the data structures are different (some of them use libraries from Batteries), but the ideas are the same.

(* using a reference as accumulator *)
let most_significant_bit input_bits =
  let result = ref None in
  for i = Array.length input_bits - 1 downto 0 do
    if input_bits.(i) then
      if !result = None then
        result := Some i
  done;
  !result

let most_significant_bit input_bits =
  let result = ref None in
  for i = 0 to Array.length input_bits - 1 do
    if input_bits.(i) then
      (* only the last one will be kept *)
      result := Some i
  done;
  !result

(* simple recursive version *)
let most_significant_bit input_bits =
  let rec loop = function
    | -1 -> None
    | i ->
      if input_bits.(i) then Some i
      else loop (i - 1)
  in
  loop (Array.length input_bits - 1)

(* higher-order traversal *)
open Batteries_uni
let most_significant_bit input_bits =
  Array.fold_lefti
    (fun result i ->
      if input_bits.(i) && result = None then Some i else result)
    None input_bits

(* traversal using an intermediate lazy data structure 
   (a --- b) is the decreasing enumeration of integers in [b; a] *)
open Batteries_uni
let most_significant_bit input_bits =
  (Array.length input_bits - 1) --- 0
  |> Enum.Exceptionless.find (fun i -> input_bits.(i))

(* using an exception to break out of the loop; if I understand
   correctly, exceptions are rather discouraged in F# for efficiency
   reasons. I proposed to use `yield` instead and then force the
   generator, but this has no direct OCaml equivalent. *)
exception Result of int
let most_significant_bit input_bits =
  try
    for i = Array.length input_bits - 1 downto 0 do
      if input_bits.(i) then raise (Result i)
    done;
    None
  with Result i -> Some i

Answer 2

Why using a loop when you can use high-order functions?

I would write:

let findMostSignificantBitPosition (inputBits:System.Collections.BitArray) =
    Seq.cast<bool> inputBits |> Seq.tryFindIndex id

Seq module contains many functions for manipulating collections. It is often a good alternative to using imperative loops.

but I still want to know what I was doing wrong above.

The body of a for loop is an expression of type unit. The only thing you can do from there is doing side-effects (modifying a mutable value, printing...).

In F#, a if then else is similar to ? : from C languages. The then and the else parts must have the same type, otherwise it doesn't make sense in a language with static typing. When the else is missing, the compiler assumes it is else (). Thus, the then must have type unit. Putting a value in a for loop doesn't mean return, because everything is a value in F# (including a if then).

Answer 3

+1 for gasche
Here are some examples in F#. I added one (the second) to show how yield works with for within a sequence expression, as gasche mentioned.

(* using a mutable variable as accumulator as per gasche's example *)
let findMostSignificantBitPosition (inputBits: BitArray) =
    let mutable ret = None // 0
    for i = inputBits.Length - 1 downto 0  do
        if inputBits.[i] then ret <- i
    ret

(* transforming to a Seq of integers with a for, then taking the first element *)
let findMostSignificantBitPosition2 (inputBits: BitArray) =
    seq {
        for i = 0 to inputBits.Length - 1 do
        if inputBits.[i] then yield i
    } |> Seq.head

(* casting to a sequence of bools then taking the index of the first "true" *)
let findMostSignificantBitPosition3 (inputBits: BitArray) =
    inputBits|> Seq.cast<bool>  |> Seq.findIndex(fun f -> f) 

Edit: versions returning an Option

let findMostSignificantBitPosition (inputBits: BitArray) =
    let mutable ret = None
    for i = inputBits.Length - 1 downto 0  do
        if inputBits.[i] then ret <- Some i
    ret

let findMostSignificantBitPosition2 (inputBits: BitArray) =
    seq {
        for i = 0 to inputBits.Length - 1 do
        if inputBits.[i] then yield Some(i)
        else yield None
    } |> Seq.tryPick id

let findMostSignificantBitPosition3 (inputBits: BitArray) =
    inputBits|> Seq.cast<bool>  |> Seq.tryFindIndex(fun f -> f)