How could I return a value from a function that iterates through a for loop in F #

Question

I am trying to loop over an array and return a value as shown below. But this gives me an error in the line after the if statement. He says: "This expression is expected to have a unit of type, but of type int"

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

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

Answer 1

for loops should not return values, they only perform the operation a fixed number of times, and then return () (one). If you want to repeat and finally return something, you can:

• have a link outside the loop in which you add the final result when you receive it, and then, after the loop returns the link content

• use recursive function directly

• use a higher order function that will encapsulate the workaround for you and allow you to focus on the application logic

A higher function is good if your data structure supports it. However, simple traversal functions such as fold_left do not support prematurely terminating the iteration. If you want to support this (and obviously it will be interesting in your use case), you should use a workaround with premature exit support. For simple functions like yours, a simple recursive function is probably the simplest.

In F # it should also be possible to write your function in an imperative style, using yield to turn it into a generator, and then finally make the generator get the result. This can be seen as an analogue of the OCaml method of using exceptions to jump out of a loop.

Edit: A good solution to avoid “premature stopping” issues is to use a lazy intermediate data structure that will only be created for the first satisfactory result. This is an elegant and good scripting style, but still less effective than direct exit support or simple recursion. I think it depends on your needs; Is this feature used for the critical path?

Edit:. The following is sample code. They are 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 use 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 managing collections. This is often a good alternative to using imperative loops.

but I still want to know what I'm doing wrong above.

The body of a for loop is an expression of a unit of type. The only thing you can do from there is to do side effects (change mutable value, print ...).

In F #, if then else is like ? : ? : in C. languages. then and else parts must be of the same type, otherwise it does not make sense in a language with static typing. When else missing, the compiler assumes it is else () . Thus, then must be of type unit . Putting a value in a for loop does not mean return , because all this value is in F # (including a if then ).

Answer 3

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

 (* using a mutable variable as accumulator as per gasche 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 a parameter

 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) 

Answer 4

I would recommend using a higher-order function (as Laurent mentioned) or explicitly writing a recursive function (which is a general approach to replacing loops in F #).

If you want to see some kind of fancy F # solution (which is probably the best version of using the lazy data temporal structure), you can take a look at my article that defines the required compiler for F #. This allows you to write something like:

 let findMostSignificantBitPosition (inputBits:BitArray) = imperative { for b in Seq.cast<bool> inputBits do if b then return true return false } 

There is some overhead (as with other temporary lazy data structures), but it looks just like C # :-). EDIT I also posted samples to F # Snippets: http://fssnip.net/40

Answer 5

I think the reason you have trouble writing this code is because you are not handling the failure case without detecting the dial bit. Others have published many ways to find a beat. Here are some ways to handle a failure.

option failure case

 let findMostSignificantBitPosition (inputBits:System.Collections.BitArray) = let rec loop i = if i = -1 then None elif inputBits.[i] then Some i else loop (i - 1) loop (inputBits.Length - 1) let test = new BitArray(1) match findMostSignificantBitPosition test with | Some i -> printf "Most Significant Bit: %i" i | None -> printf "Most Significant Bit Not Found" 

Exclusion Failure Case

 let findMostSignificantBitPosition (inputBits:System.Collections.BitArray) = let rec loop i = if i = -1 then failwith "Most Significant Bit Not Found" elif inputBits.[i] then i else loop (i - 1) loop (inputBits.Length - 1) let test = new BitArray(1) try let i = findMostSignificantBitPosition test printf "Most Significant Bit: %i" i with | Failure msg -> printf "%s" msg 

failure case -1

 let findMostSignificantBitPosition (inputBits:System.Collections.BitArray) = let rec loop i = if i = -1 then i elif inputBits.[i] then i else loop (i - 1) loop (inputBits.Length - 1) let test = new BitArray(1) let i = findMostSignificantBitPosition test if i <> -1 then printf "Most Significant Bit: %i" i else printf "Most Significant Bit Not Found" 

Answer 6

One option is to use the seq method and findIndex as:

 let findMostSignificantBitPosition (inputBits:System.Collections.BitArray) = seq { for i = inputBits.Length - 1 to 0 do yield inputBits.[i] } |> Seq.findIndex(fun e -> e)