.net - 从 F# 中的 lambda 表达式内部产生

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因为我想维护通用功能，并且我不希望客户总是不得不为数组克隆付出代价。

你会怎么做？

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 { .. }阻止并添加 yield!之前 f alphabet (以便函数 f 产生的所有元素都作为结果传递)，我还添加了 yield!到递归调用。

然后你可以写:

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

代码正在使用 Array.map id而不是 Clone以便您获得数组的类型安全副本而不是 obj由 .NET 克隆机制返回。

但是，我认为您实际上不需要从 lambda 中产生多个项目，因此您可以更改 yield! f alphabet只是 yield f alphabet (仅返回单个元素而不是多个元素)并写入:

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

通过这种方式，您 - 至少 - 获得了一种很好的方法来抽象出克隆行为(并且您可以选择克隆或不轻松地克隆阵列)。