F＃：如何找到笛卡儿的力量 [英] F#: how to find Cartesian power

问题描述

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

例如，[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 UV = 
 let mutable res = [] 
 for u in U do 
 for v in V do 
 res<  -  res @ [[u; v]] 
 res 
  

并尝试计算笛卡尔功率。
我使用下面的代码来计算笛卡尔乘积：

 让Cpower U n = 
让可变V = U 
 for i = 0 to n-1 do 
 V < -  Dprod UV 
 V 
  

Visual Studio说：错误统一''a'和''列表'时，生成的类型将是无限的。我会感谢任何帮助和链接。我还会补充说，它通常是首选避免使用<$ c $当编写F＃代码时，c> mutable 值。当你学习F＃或者当你需要优化一些代码来加快运行速度时，这很好，但是如果你想写一个更习惯的F＃代码，最好使用递归而不是 mutable values。

我试图更优雅地写出笛卡儿的力量，这里是我的版本。它是递归地实现的。当我们需要计算 X ^ 1 并且递归情况执行如下的笛卡尔乘积时，我明确地处理了这种情况： X ^ n = X * X ^（n-1）

我使用序列表达式并且该方法生成序列的元素（作为结果返回）使用 yield ：

  let rec cartesianPow input n = seq {
 if（n = 1）然后
 //当递归终止时，处理这种情况。我们需要将
 //输入中的每个元素变成包含单个元素的列表：
 // [1; 2; 4] ^ 1 = [[1]; [2]; [3]] 
 for el输入do 
 yield [el] 
 else 
 //我们执行一个笛卡尔积（并运行
 //的其余部分功率计算递归）。数学：
 // [1; 2; 3] ^ n = [1; 2; 3] x（[1; 2; 3] ^（n-1））
 for el在输入do 
 for rest in cartesianPow input（n  -  1）do 
 yield el ::休息} 
 
 cartesianPow [0; 1] 3 
  

这不是最有效的实现（例如，因为使用 yield 在中用于循环可能不是一件好事），但这对大 n 。在F＃中，从最简单的实现开始，通常是一个好主意，它更易于理解： - ）。

I have a problem with writing a Cartesian power function. I found many examples about calculating Cartesian Product, but no one about Cartesian power.
For example, [1;2] raised to power 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] ]
I use following code to calculate Cartesian Product:

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

And trying to calculate Cartesian power. I use following code to calculate Cartesian Product:

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

Visual Studio said: Error The resulting type would be infinite when unifying ''a' and ''a list'. I will thankful for any help and links.

解决方案

I would also add that it is generally prefered to avoid using mutable values when writing F# code. It's fine when you're learning F# or when you need to optimize some code to run faster, but if you want to write a more idiomatic F# code, it's better to use recursion instead of mutable values.

I tried to write the Cartesian power a bit more elegantly and here is my version. It is implemented recursively. I explicitly handle the case when we need to calculate X^1 and the recursive case performs a Cartesian product like this: X^n = X * X^(n-1)

I'm using sequence expressions and the method generates elements of the sequence (to be returned as the result) using 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

This isn't the most efficient implementation (e.g. because using yield inside for loop may not be a good thing to do), but that would be only problem for large n. In F#, it is usually a good idea to start with the cleanest implementation that's easier to understand :-).

这篇关于F＃：如何找到笛卡儿的力量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！