F#：如何找到笛卡尔的力量

Question

我在写笛卡尔幂函数时遇到了问题。我找到了很多关于计算笛卡尔乘积的例子，但没有一个是关于笛卡尔乘积的。

例如，1;2的幂3=[ 1;1;1；1; 1; 2 ;1 ; 1 ; 2;2 ;1；1；2；2；1；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‘’和''a‘a list’时，结果类型将是无限的。我将感谢任何帮助和链接。

Answer 1

我还想补充一点，在编写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

这不是最有效的实现(例如，因为在for循环中使用yield可能不是一件好事)，但这只是大型n的问题。在F#中，最好从最简洁、更容易理解的实现开始:-)。

Answer 2

至于错误的来源，我们有以下类型约束

// 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<`a>和`a list list，并且U和V必须具有相同的类型，这意味着`a = `a list，这就是导致“infinity type”错误消息的原因(infinity type是... list list list list。即使V的值是可变的，它也必须具有单一类型。

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

这给了你一个结果的序列，而不是一个列表。不幸的是，我不能通过观察它来判断它是否足够懒惰:它可能必须在内存中生成整个列表才能开始给您提供第一个元素。您应该能够通过在调试器中逐步执行它来找出答案。(或者你可能比我更擅长阅读“懒惰”。)