F＃：如何找到笛卡爾電源

我有一個寫笛卡爾冪函數的問題。我發現了很多關於計算笛卡爾乘積的例子，但沒有一個關於笛卡兒乘方的例子。例如，[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]]
我用下面的代碼來計算笛卡爾乘積：F＃：如何找到笛卡爾電源

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「和'名單」時產生的類型將是無限的。我會感謝任何幫助和聯繫。

來源

2010-04-15 Nike

你知道@有線性運行時嗎？最後使用::和reverse（如果甚至有必要的話）會比使用@快得多。 – sepp2k 2010-04-15 20:42:56

我還會補充一點，在編寫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＃中，從最簡潔的實現開始，通常是一個好主意:-)。

來源

2010-04-15 21:23:20

我解決我的問題：

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

來源

2010-04-15 20:24:25 Nike

至於在誤差的來源，我們有以下類型約束

// 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，並且，美和V必須具有相同的類型意味着`a = `a list，這就是「無限類型」錯誤信息的結果（無窮大類型爲... list list list list。儘管值爲V是可變的，它必須有一個單一的類型。

來源

2010-04-15 20:50:50 outis

這裏是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

這給你的結果，而不是一個列表的起。不幸的是，我看不出它是否很懶夠了：它可能必須在內存中生成整個列表來開始給你第一個元素。您應該能夠在調試器中逐步瞭解它。（或者你在閱讀懶惰方面可能會比我更好。）

來源

2010-04-15 21:23:13

F＃：如何找到笛卡爾電源

回答

相關問題