recursion - 在 F# 中计算排列的递归函数具有类型不匹配错误

Question

我正在尝试在 F# 中编写一个通用函数，该函数将返回列表的所有排列。我试图使用受 Java 版本 here 启发的递归算法来完成此操作。

但是在递归函数的最后一行，我得到了注释中给出的错误。我猜这与将递归循环退出时产生的输出(正在执行 if(Array.length <= 1) then 的输出)与其余的 Array.Map 函数进行整理有关。

如果有人能够解释为什么会发生此错误以及我如何修复它，我将不胜感激。

let GetPermutationsOfList inputList =

let rec innerLoop firstPart secondPart =
    if (Array.length secondPart) <= 1 then
        [| Array.append firstPart secondPart |]
    else
        let SliceAtMarkerElement m =
           let currentMarkerElement = secondPart.[m] 
           let everythingBeforeMarkerElement = secondPart.[0 .. m - 1]
           let everythingAfterMarkerElement = secondPart.[m+1 .. ]
           let newSecondPartList = Array.append everythingBeforeMarkerElement everythingAfterMarkerElement
           let newFirstPartList = Array.append firstPart [|currentMarkerElement|]
           (newFirstPartList, newSecondPartList)

        [|for i in 0 .. ((Array.length secondPart) - 1) -> i|] |> 
        Array.map(fun c -> SliceAtMarkerElement c) |>
        // The following line gives the error 
        // "Type Mismatch. Expecting a 'a but given a 'a[] The resulting type would be infinite when unifying "a' and "a[]"
        Array.map(fun d -> innerLoop (fst d) (snd d))

innerLoop Array.empty (List.toArray inputList)

Answer 1

假设您函数的缩进是正确的，错误消息非常有用。在 innerLoop功能，Array.append firstPart secondPart应该返回 'b [] .然而，最后一行 Array.map(fun d -> innerLoop (fst d) (snd d))强制它返回 'b [] [] ，无法与 'b [] 统一.

我想你想计算每个 innerLoop 的排列并在之后连接这些结果。您必须使用 Array.collect而不是 Array.map :

[|for i in 0 .. (Array.length secondPart)-1 -> i|] 
|> Array.map (fun c -> SliceAtMarkerElement c) 
|> Array.collect (fun d -> innerLoop (fst d) (snd d))

上面的片段使用了两个临时数组，很浪费。您可以仅使用计算表达式来消除这些额外的数组:

[| for i in 0 .. (Array.length secondPart)-1 do
      let first, second = SliceAtMarkerElement i
      yield! innerLoop first second (* concatenating results *)
    |]

更新:

如注释中所述，您希望返回一个数组数组，其中每个数组都是一个排列。所以你的改变会起作用， map操作应该是:

[| for i in 0 .. (Array.length secondPart)-1 do
          let first, second = SliceAtMarkerElement i
          yield innerLoop first second (* returning each array as a permutation *)
        |]