在 F# 中，lambda 表达式中的 yield 如何使用？

Question

我在F#中实现了一个标准的可变原地排列算法（如果有类似的内置方式，我将非常感激提供的信息）:

let permutations f (alphabet:'a array) =
    let swap i j =
        let aux = alphabet.[i]
        alphabet.[i] <- alphabet.[j]
        alphabet.[j] <- aux
    let rec permutations' n =
        if n = alphabet.Length
        then f alphabet
        else
            for i in n..(alphabet.Length-1) do
                swap n i
                permutations' (n+1)
                swap n i
    permutations' 0

虽然该函数非常多才多艺，但我想知道在F#中是否有一种实现包装器函数的方法，可以将发现的项作为序列产生。类似于以下（不正确）的F#方法：

let permutations_seq (alphabet:'a array) =
    seq {
        permutations (fun arr -> yield arr.Clone()) alphabet
    }

在 permutations 函数中，我不想直接使用 yield，因为我希望保持该函数的通用性，而且我也不想客户端总是为数组克隆付出代价。

您会如何处理？

- devoured elysium

---

为什么permutations不能产生未克隆的数组？这样，用户就可以决定他想要做什么。 - svick

另外，你具体想象这个怎么工作？你的“permutations”函数不会返回直到所有排列都被创建，但是“permutations_seq”应该立即返回并在需要时生成排列。如果“permutations”在另一个线程上运行，并且大部分时间都在“f”内部阻塞，那么这样做是否可以？如果“permutations_seq”的枚举过程提前结束会发生什么？“f”是否应该抛出异常？ - svick

@svick：“为什么排列不能产生未克隆的数组？”嗯，那是我的原始想法，说实话。但我觉得返回一个具有如此奇怪行为的序列会感觉很奇怪。 - devoured elysium

顺便提一下，在回调函数中使用yield看起来像是异步模式，例如异步工作流或响应式扩展。然而，实际的代码并不真正是异步的，所以最好还是使用yield。 - bradgonesurfing

Answer 1

如果你想从lambda函数中“产生”结果，那么lambda函数本身需要返回一个序列（因此lambda函数的调用者也需要返回一个序列），所以没有办法在不修改permutations函数的情况下得到你想要的结果（因为在一个（嵌套的）作用域中运行的代码无法将生成的值传递给在某个其他（外部）作用域中定义的列表）。

但是，你可以将permutations更改为以下内容：

let permutations f (alphabet:'a array) =
    let swap i j =
        let aux = alphabet.[i]
        alphabet.[i] <- alphabet.[j]
        alphabet.[j] <- aux
    let rec permutations' n = seq {
        if n = alphabet.Length
        then yield! f alphabet
        else
            for i in n..(alphabet.Length-1) do
                swap n i
                yield! permutations' (n+1)
                swap n i }
    permutations' 0

我将 permutations' 包装在 seq { .. } 块中，并在 f alphabet 前添加了 yield!（这样由函数 f 生成的所有元素都会被传递作为结果），同时我还在递归调用前添加了 yield!。

然后，您可以编写如下代码：

permutations (fun arr -> seq { yield arr |> Array.map id }) [|1;2;3|]

代码正在使用Array.map id而非Clone，这样你可以得到一个类型安全的数组副本，而不是由.NET克隆机制返回的obj。

然而，我认为你实际上并不需要从lambda中产生多个项目，所以你可以将yield! f alphabet更改为yield f alphabet（只返回一个元素而不是多个元素），并编写：

permutations (fun arr -> arr |> Array.map id) [|1;2;3|]

这样，您至少可以得到一个很好的抽象方式来隐藏克隆行为（并且您可以轻松选择是否克隆数组）。

- Tomas Petricek

---

这不太对。你应该使用“yield f alphabet”而不是“yield! f alphabet”。结果应该是“seq<'a array>”，而不是“seq<`a>”。我想修复它，但我有点紧张，因为我的级别只有5k，而不是92k ;) - bradgonesurfing

同时，一旦您删除了平坦化的yield！传入“f”似乎是不必要的。相反，使用“permutations [|1;2;3|] |> Seq.map (fun alphabet -> alphabet |> Array.map id)”来确保它被克隆。 - bradgonesurfing

Answer 2

你必须让未克隆的数组屈服。显然存在奇怪的行为，如果在序列上调用toList，则会得到一个数组，其中包含数组的最后一个值。所以，你首先需要使用clone函数对其进行Seq.map处理。此外，如果已经使用可变对象，则不需要将函数递归。

let permutations (alphabet:'a array) =
    let swap i j =
        let aux = alphabet.[i]
        alphabet.[i] <- alphabet.[j]
        alphabet.[j] <- aux
    let rec permutations' n = 
        seq {
                if n = alphabet.Length
                then yield alphabet
                else
                    for i in n..(alphabet.Length-1) do
                        swap n i
                        yield! permutations' (n+1)
                        swap n i
        }
    permutations' 0


let a = [|"a"; "b"; "c"; "d"|]
let p =
    (permutations a)
    |> Seq.map (fun arr -> arr.Clone() )
    |> Seq.toList

输出

  val p : obj list =
  [[|"a"; "b"; "c"; "d"|]; [|"a"; "b"; "d"; "c"|]; [|"a"; "c"; "b"; "d"|];
   [|"a"; "c"; "d"; "b"|]; [|"a"; "d"; "c"; "b"|]; [|"a"; "d"; "b"; "c"|];
   [|"b"; "a"; "c"; "d"|]; [|"b"; "a"; "d"; "c"|]; [|"b"; "c"; "a"; "d"|];
   [|"b"; "c"; "d"; "a"|]; [|"b"; "d"; "c"; "a"|]; [|"b"; "d"; "a"; "c"|];
   [|"c"; "b"; "a"; "d"|]; [|"c"; "b"; "d"; "a"|]; [|"c"; "a"; "b"; "d"|];
   [|"c"; "a"; "d"; "b"|]; [|"c"; "d"; "a"; "b"|]; [|"c"; "d"; "b"; "a"|];
   [|"d"; "b"; "c"; "a"|]; [|"d"; "b"; "a"; "c"|]; [|"d"; "c"; "b"; "a"|];
   [|"d"; "c"; "a"; "b"|]; [|"d"; "a"; "c"; "b"|]; [|"d"; "a"; "b"; "c"|]]

- bradgonesurfing

Answer 3

如果您真的想使用回调（reactive）方法，则请使用响应式扩展。

https://github.com/fsharp/FSharp.Reactive/blob/master/src/Observable.fs

并写

let permutations (alphabet:'a array) =
    Observable.create (fun subscriber ->
      let swap i j =
          let aux = alphabet.[i]
          alphabet.[i] <- alphabet.[j]
          alphabet.[j] <- aux
      let rec permutations' n = 
          seq {
                  if n = alphabet.Length
                  then subscriber.OnNext(alphabet)
                  else
                      for i in n..(alphabet.Length-1) do
                          swap n i
                          permutations' (n+1)
                          swap n i
          }
      permutations' 0
    )

然后你可以做到：

permutations [|"a"; "b"; "c"|]
|> Observable.map ( fun arr -> arr.Clone() )
|> Observable.ToEnumerable
|> Seq.ToList

然而请注意，与我基于收益率发布的另一个答案相比，这种情况下你并没有比收益率获得更多的好处。

- bradgonesurfing