更不穩定序列比「經典」

Question

笛卡爾的生產有一個足夠好的功能 - 序列其定義這樣的：

let rec sequence = function 
    | []  -> Seq.singleton [] 
    | (l::ls) -> seq { for x in l do for xs in sequence ls do yield (x::xs) } 

但看看它的結果：

序列[[1..2]; [1..10000]] |> Seq.skip 1000 ;; val it：seq = seq [[1; 1001]; [1; 1002]; [1; 1003]; [1; 1004]; ...]

正如我們所看到的第一個「座標」的產品改變非常緩慢，當第二列表結束它會改變的值。

我寫了如下（下面的評論）我自己的序列：

/// Sum of all producted indeces = n 
let rec hyper'plane'indices indexsum maxlengths = 
    match maxlengths with 
    | [x]  -> if indexsum < x then [[indexsum]] else [] 
    | (i::is) -> [for x in [0 .. min indexsum (i-1)] do for xs in hyper'plane'indices (indexsum-x) is do yield (x::xs)] 
    | []  -> [[]] 

let finite'sequence = function 
    | [] -> Seq.singleton [] 
    | ns -> 
     let ars = [ for n in ns -> Seq.toArray n ] 
     let length'list = List.map Array.length ars 
     let nmax = List.max length'list 
     seq { 
      for n in [0 .. nmax] do 
      for ixs in hyper'plane'indices n length'list do 
       yield (List.map2 (fun (a:'a[]) i -> a.[i]) ars ixs) 
     } 

的核心思想是在（二）名單看起來在（二）正交的維度，每一個元素標誌着其在指數名單。所以我們可以枚舉所有元素，通過枚舉每個笛卡兒積的每個元素的超平面（在2D情況下，這是一條線）。換句話說，想象一下excel的表格，其中第一列包含[1; 1]到[1; 10000]的值，其次是從[2; 1]到[2; 10000]。編號爲1的「超平面」是連接單元格A2和單元格B1的線。對於我們的例子

hyper'plane'indices 0 [2; 10000] ;; val it：int list list = [[0; 0]]
hyper'plane'indices 1 [2; 10000] ;; val it：int list list = [[0; 1]; [1; 0]]
hyper'plane'indices 2 [2; 10000] ;; val it：int list list = [[0; 2]; [1; 1]]
hyper'plane'indices 3 [2; 10000] ;; val it：int list list = [[0; 3]; [1; 2]]
hyper'plane'indices 4 [2; 10000] ;; val it：int list list = [[0; 4]; [1; 3]]

那麼如果我們有的indeces和數組，我們從給定的列表產生比我們現在可以定義序列爲{平面0中的所有元素;比平面1中的所有元素...等等}並且獲得比原始序列更多的易失性函數。

但是有限'序列變成了非常貪吃的功能。現在是問題。我如何改進它？

祝福亞歷山大。 （對於英語不好的人，很抱歉）

Answer 1

你能解釋一下問題到底是什麼 - 時間或空間的複雜性或性能？你有沒有具體的基準？我不知道如何在這裏改進時間複雜性，但是我編輯了一下代碼來刪除中間列表，這可能會對內存分配行爲有所幫助。

不要這樣做：

for n in [0 .. nmax] do 

而是執行此操作：

for n in 0 .. nmax do 

下面是代碼：

let rec hyper'plane'indices indexsum maxlengths = 
    match maxlengths with 
    | [] -> Seq.singleton [] 
    | [x] -> if indexsum < x then Seq.singleton [indexsum] else Seq.empty 
    | i :: is -> 
     seq { 
      for x in 0 .. min indexsum (i - 1) do 
       for xs in hyper'plane'indices (indexsum - x) is do 
        yield x :: xs 
     } 

let finite'sequence xs = 
    match xs with 
    | [] -> Seq.singleton [] 
    | ns -> 
     let ars = [ for n in ns -> Seq.toArray n ] 
     let length'list = List.map Array.length ars 
     let nmax = List.max length'list 
     seq { 
      for n in 0 .. nmax do 
       for ixs in hyper'plane'indices n length'list do 
        yield List.map2 Array.get ars ixs 
     } 

這是否收費的更好嗎？順便說一句，美麗的問題。

更新：也許你更有興趣混合序列公平比在算法中維護精確的公式。這是一個Haskell代碼，可以公平地混合有限數量的可能無限序列，其中公平性意味着對於每個輸入元素都有一個包含它的輸出序列的有限前綴。你提到的，你有一個2D增量的解決方案，是很難推廣到N維的評論，和Haskell代碼正是這麼做的：

merge :: [a] -> [a] -> [a] 
merge [] y   = y 
merge x []   = x 
merge (x:xs) (y:ys) = x : y : merge xs ys 

prod :: (a -> b -> c) -> [a] -> [b] -> [c] 
prod _ [] _ = [] 
prod _ _ [] = [] 
prod f (x:xs) (y:ys) = f x y : a `merge` b `merge` prod f xs ys where 
    a = [f x y | x <- xs] 
    b = [f x y | y <- ys] 

prodN :: [[a]] -> [[a]] 
prodN []  = [[]] 
prodN (x:xs) = prod (:) x (prodN xs) 

我還沒有移植這F＃還沒有 - 它需要一些思想爲序列與頭部/尾部不匹配得很好。

更新2：

一個相當機械翻譯F＃如下。

type Node<'T> = 
    | Nil 
    | Cons of 'T * Stream<'T> 

and Stream<'T> = Lazy<Node<'T>> 

let (!!) (x: Lazy<'T>) = x.Value 
let (!^) x = Lazy.CreateFromValue(x) 

let rec merge (xs: Stream<'T>) (ys: Stream<'T>) : Stream<'T> = 
    lazy 
    match !!xs, !!ys with 
    | Nil, r | r, Nil -> r 
    | Cons (x, xs), Cons (y, ys) -> Cons (x, !^ (Cons (y, merge xs ys))) 

let rec map (f: 'T1 -> 'T2) (xs: Stream<'T1>) : Stream<'T2> = 
    lazy 
    match !!xs with 
    | Nil -> Nil 
    | Cons (x, xs) -> Cons (f x, map f xs) 

let (++) = merge 

let rec prod f xs ys = 
    lazy 
    match !!xs, !!ys with 
    | Nil, _ | _, Nil -> Nil 
    | Cons (x, xs), Cons (y, ys) -> 
     let a = map (fun x -> f x y) xs 
     let b = map (fun y -> f x y) ys 
     Cons (f x y, a ++ b ++ prod f xs ys) 

let ofSeq (s: seq<'T>) = 
    lazy 
    let e = s.GetEnumerator() 
    let rec loop() = 
     lazy 
     if e.MoveNext() 
      then Cons (e.Current, loop()) 
      else e.Dispose(); Nil 
    !! (loop()) 

let toSeq stream = 
    stream 
    |> Seq.unfold (fun stream -> 
     match !!stream with 
     | Nil -> None 
     | Cons (x, xs) -> Some (x, xs)) 

let empty<'T> : Stream<'T> = !^ Nil 
let cons x xs = !^ (Cons (x, xs)) 
let singleton x = cons x empty 

let rec prodN (xs: Stream<Stream<'T>>) : Stream<Stream<'T>> = 
    match !!xs with 
    | Nil -> singleton empty 
    | Cons (x, xs) -> prod cons x (prodN xs) 

let test() = 
    ofSeq [ 
     ofSeq [1; 2; 3] 
     ofSeq [4; 5; 6] 
     ofSeq [7; 8; 9] 
    ] 
    |> prodN 
    |> toSeq 
    |> Seq.iter (fun xs -> 
     toSeq xs 
     |> Seq.map string 
     |> String.concat ", " 
     |> stdout.WriteLine)