F #: как найти декартову силу

Question

У меня проблема с написанием декартовой степенной функции.Я нашел много примеров о расчете декартовых произведений, но ни одного о декартовой мощи.
Например, [1; 2] возвели в степень 3 = [[1; 1; 1];[1; 1; 2];[1; 2; 1];[1; 2; 2];[2; 1; 1];[2; 1; 2];[2; 2; 1];[2; 2; 2]]
Я использую следующий код для вычисления декартового произведения:

 let Cprod U V =
        let mutable res = []
        for u in U do
            for v in V do
                res <- res @ [[u;v]]
        res

И пытаюсь вычислить декартову степень.Я использую следующий код для вычисления декартового произведения:

let Cpower U n =
    let mutable V = U
    for i=0 to n-1 do
        V <- Dprod U V
    V

Visual Studio сказала: Ошибка Результирующий тип будет бесконечным при объединении '' a 'и' 'список'.Буду благодарен за любую помощь и ссылки.

Answer 1

Откуда исходит ошибка, у нас есть следующие ограничения типа

// Cprod: seq<`a> -> seq<`a> -> `a list list
let Cprod U V =
    ...

// Cpower: seq<`a> -> int -> ???
let Cpower U n =
    // V: seq<`a>
    let mutable V = U
    // n: int
    for i=0 to n-1 do
        (* The next line implies two type constraints:
           V: seq<`a>
           V: `a list list *)
        V <- Dprod U V
    V

То, что V должно быть seq<&#x60;a> и `a list list, и что U и V должны иметь одинаковый тип, означает, что `a = `a list, что приводит к сообщению об ошибке "бесконечного типа" (бесконечность тип ... list list list list. Хотя значение V является изменяемым, оно должно иметь один тип.

Answer 2

Я бы также добавил, что обычно при написании кода F # предпочтительнее избегать использования значений mutable. Это хорошо, когда вы изучаете F # или когда вам нужно оптимизировать некоторый код для более быстрой работы, но если вы хотите написать более идиоматический код F #, лучше использовать рекурсию вместо mutable значений.

Я попытался изобразить декартову степень немного более элегантно, и вот моя версия. Это реализовано рекурсивно. Я явно обрабатываю случай, когда нам нужно вычислить X^1, а рекурсивный случай выполняет декартово произведение, подобное этому: X^n = X * X^(n-1)

Я использую выражения последовательности, и метод генерирует элементы последовательности (которые должны быть возвращены в результате), используя yield:

let rec cartesianPow input n = seq {
  if (n = 1) then
    // This handles the case when the recursion terminates. We need to turn
    // each element from the input into a list containing single element:
    //   [1; 2; 4] ^ 1 = [ [1]; [2]; [3] ]
    for el in input do 
      yield [el]
  else
    // We perform one Cartesian product (and run the rest of the 
    // power calculation recursively). Mathematically:
    //   [1; 2; 3] ^ n = [1; 2; 3] x ([1; 2; 3] ^ (n-1))
    for el in input do 
      for rest in cartesianPow input (n - 1) do
        yield el :: rest }

cartesianPow [ 0; 1 ] 3

Это не самая эффективная реализация (например, потому что использование yield внутри цикла for может быть не очень полезным), но это будет проблемой только для больших n. В F # обычно хорошей идеей будет начать с самой чистой реализации, которую легче понять: -).

Answer 3

Вот версия, портированная с Haskell:

let replicate n x = [for i in 1 .. n -> x]
let sequence ms = 
  List.fold (fun m' m -> [for x in m do for xs in m' -> (x::xs)]) [[]] ms
let Cpower n l = replicate n l |> sequence

Это работает как подсчет: если вы думаете о l как о цифрах, то он копирует их на количество мест, которые у вас есть, а затем считает их с помощью sequence.

Другими словами, все двоичные числа, меньшие 2 ^ 3, могут быть сгенерированы путем репликации [0;1] 3 раза, чтобы получить [[0;1]; [0;1]; [0;1]], а затем запустить на них sequence.

Это можно сделать более ленивым, переключившись на Seq.fold:

let sequence' ms =
  Seq.fold (fun m' m -> seq {for x in m do for xs in m' do yield (x::xs)})
           (seq {yield []})
           ms

Это дает вам последовательность результатов вместо списка. К сожалению, я не могу сказать, посмотрев на него, лениво ли достаточно : возможно, ему придется сгенерировать весь список в памяти, чтобы начать давать вам первый элемент. Вы должны быть в состоянии выяснить это, пройдя через это в отладчике. (Или вы можете лучше читать лень, чем я.)

Answer 4

Я решаю свою проблему:

let rec Cprod = function
    | [] -> [[]]
    | hs::tss ->
        [ for h in hs do            
            for ts in D tss ->
                h::ts]

let Cpower U n = 
    let mutable inp = []
    for i=0 to n-1 do
        inp <- inp @ [U]
    Dprod inp