Рекурсивная функция для вычисления перестановок в F # имеет ошибку несоответствия типов - PullRequest
Новая
       41

Рекурсивная функция для вычисления перестановок в F # имеет ошибку несоответствия типов

2 голосов
/ 24 декабря 2011

Я пытаюсь написать общую функцию на F #, которая бы возвращала все перестановки списка. Я пытался сделать это, используя рекурсивный алгоритм, вдохновленный Java-версией здесь

Но в последней строке рекурсивной функции я получаю ошибку, приведенную в комментариях. Я предполагаю, что это как-то связано с сопоставлением вывода, полученного при выходе из рекурсивного цикла (вывод 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)

1 Ответ

3 голосов
/ 24 декабря 2011

Предположим, что отступ вашей функции правильный, сообщение об ошибке довольно информативно.В функции 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 *)
        |]
...