如何从在 F# 中迭代​​ for 循环的函数返回值

Question

我正在尝试循环数组并返回一个值，如下所示。但这在 if 语句之后的行上给了我一个错误。它说“这个表达式应该有类型unit，但有类型int”

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

我该怎么做？我正在用递归循环重新编码，因为这似乎是在函数语言中进行此类循环的更被接受的方式，但我仍然想知道我上面做错了什么。

Answer 1

for 循环不应该返回值，它们只执行固定次数的操作，然后返回 () （单位）。如果你想迭代并最终返回一些东西，你可以：

• 在循环外部有一个引用，当你得到最终结果时将其放入其中，然后在循环之后返回引用内容

• 直接使用递归函数

• 使用将封装结果的高阶函数为您遍历，让您专注于应用程序逻辑

如果您的数据结构支持，高阶函数就很好。然而，诸如 fold_left 之类的简单遍历函数不支持过早停止迭代。如果您希望支持这一点（显然这在您的用例中会很有趣），则必须使用具有过早退出支持的遍历。对于像您这样的简单函数，简单的递归函数可能是最简单的。

在 F# 中，还应该可以以命令式风格编写函数，使用 yield 将其转换为生成器，然后最终强制生成器获取结果。这可以看作是 OCaml 技术的对应部分，即使用异常跳出循环。

编辑：避免“过早停止”问题的一个好解决方案是使用惰性中间数据结构，该结构只会构建到第一个令人满意的结果。这是优雅且良好的脚本风格，但仍然比直接退出支持或简单递归效率低。我想这取决于你的需求；该函数是否要在关键路径中使用？

编辑：以下是一些代码示例。它们是 OCaml，数据结构不同（其中一些使用 Batteries 中的库），但是想法是一样的。

(* 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

当可以使用高阶函数时为什么要使用循环？

我会写：

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

Seq 模块包含许多用于操作集合的函数。它通常是使用命令式循环的一个很好的替代方案。

但我还是想知道我是什么
上面做错了。

for 循环的主体是一个类型为unit 的表达式。你唯一能做的就是产生副作用（修改可变值、打印......）。

在 F# 中，if then else 类似于 ? ：来自C语言。 then 和 else 部分必须具有相同的类型，否则在静态类型语言中没有意义。当 else 缺失时，编译器假定它是 else ()。因此，then 必须具有 unit 类型。将值放入 for 循环中并不意味着返回，因为 F# 中的所有内容都是值（包括 if then）。

Answer 3

+1 加油
以下是 F# 中的一些示例。我添加了一个（第二个）来展示 yield 如何在序列表达式中与 for 配合使用，正如 Gasche 提到的那样。

(* 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) 

编辑：返回选项的版本

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

我建议使用高阶函数（如 Laurent 提到的）或显式编写递归函数（这是替换 F# 中循环的通用方法）。

如果您想看到一些奇特的 F# 解决方案（这可能是使用某些临时惰性数据结构的更好版本），那么您可以看一下我的文章，其中定义了 F# 的命令式计算生成器。这允许您编写如下内容：

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

存在一些开销（与使用其他临时惰性数据结构一样），但它看起来就像 C# :-)。
编辑我还在 F# Snippets 上发布了示例：http://fssnip.net/40

Answer 5

我认为您在如何编写此代码方面遇到问题的原因是您没有处理找不到设置位的失败情况。其他人发布了许多找到该位的方法。以下是处理失败案例的几种方法。

失败案例（按选项）

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"

失败案例（按异常）

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

失败案例（按 -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

选项之一是使用 seq 和 findIndex 方法：

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