从f#中的lambda表达式中产生的

I've implemented a standard mutable in-place permutations algorithm in F# (if there's some built-in way of doing something similar, I'd be grateful for the information):

我在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

Although the function is quite versatile I was wondering if there was some way in F# to implement a wrapper function that would yield me the discovered items as a sequence. Something resembling the following (incorrect) F# method:

虽然这个函数非常通用，但我想知道f#中是否有什么方法可以实现包装函数，从而将发现的项目作为一个序列提供给我。类似于以下(不正确)的f#方法:

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

In permutations I don't want to directly yield as I'd like to maintain the function general and I don't want the client to always have to pay the price for array cloning.

在排列中，我不希望直接产生结果，因为我希望维护函数的通用性，我不希望客户端总是为数组克隆付出代价。

How would you do it?

你会怎么做?

3 个解决方案

#1

If you want to "yield" results from the lambda function, then the lambda function itself needs to return a sequence (and so the caller of the lambda function needs to return a sequence too). So, there is no way to get what you want without modifying the permutations function (because you cannot yield values from code running in one (nested) scope to a list defined in some other (outer) scope).

如果希望“yield”函数的结果，那么lambda函数本身需要返回一个序列(因此lambda函数的调用者也需要返回一个序列)。因此，如果不修改排列函数，就无法得到想要的结果(因为不能从运行在一个(嵌套)范围中的代码向其他(外部)范围中定义的列表输出值)。

However, you can change permutations to look something like this:

然而，你可以改变排列看起来像这样:

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

I wrapped permutations' in the seq { .. } block and added yield! before f alphabet (so that all elements produced by the function f are passed as results) and I also added yield! to the recursive call.

我在seq {..块加良率!在f字母表之前(这样，函数f产生的所有元素都作为结果通过)，我还增加了yield!递归调用。

Then you can write:

然后你可以写:

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

The code is using Array.map id instead of Clone so that you get a type-safe copy of the array rather than an obj as returned by the .NET cloning mechanism.

代码使用数组。映射id而不是克隆，这样您就可以得到一个类型安全的数组副本，而不是. net克隆机制返回的obj。

However, I suppose that you do not actually need to yield multiple items from the lambda, so you could change yield! f alphabet to just yield f alphabet (to return just a single element rather than multiple elements) and write:

但是，我认为您实际上不需要从lambda中生成多个项，因此您可以更改yield!f字母表只返回一个元素而不是多个元素，然后写:

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

This way, you - at least - get a nice way to abstract away the cloning behavior (and you can choose to clone or not to clone the array easily).

这样，您至少可以得到一种很好的方法来抽象克隆行为(您可以选择克隆还是不克隆数组)。

#2

If you really want to use a call back (reactive) approach then use reactive extensions

如果您确实想使用回调方法，那么就使用无反应扩展。

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

and write

和写

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
    )

Then you can do

然后你可以做

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

However note the symetry with respects to the other answer I posted based on yield so you don't gain much over yield in this case.

但是，请注意symetry的另一个基于产量的答案，所以在这种情况下，您不会获得太多的收益。

#3

You have to yield the uncloned array. There is the obvious strange behaviour in that if you call toList on the sequence then you get an array of the last value of the array. So the first thing you have to do is Seq.map it with the clone function. Also I don't think there is a need to make your function recursive if you are allready working with mutables.

必须生成未克隆的数组。有一种明显的奇怪行为，如果你调用序列上的toList，你会得到数组最后一个值的数组。首先要做的是Seq。用克隆函数映射它。而且，如果您已经准备好使用mutables，那么我认为不需要使函数递归。

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

outputs

输出

  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"|]]

#1