瞭解涉及生成器的遞歸函數

我遇到了下面的遞歸算法，這裏寫在Swift中，給定一個數組，產生一個生成一個比原始數組短的元素的子數組的生成器。通過在每個索引處刪除一個元素來創建子數組。瞭解涉及生成器的遞歸函數

即輸入[1,2,3]將返回生成器[1,2] [2,3] [1,3]。

該算法的工作原理，但我很難理解如何。有人可以解釋發生了什麼，或提供有關如何分析或理解它的建議？在此先感謝

// Main algorithm 
func smaller1<T>(xs:[T]) -> GeneratorOf<[T]> { 
    if let (head, tail) = xs.decompose { 

     var gen1:GeneratorOf<[T]> = one(tail) 

     var gen2:GeneratorOf<[T]> = map(smaller1(tail)) { 
      smallerTail in 
      return [head] + smallerTail 
     } 
     return gen1 + gen2 
    } 

    return one(nil) 
} 


// Auxillary functions used 
func map<A, B>(var generator:GeneratorOf<A>, f:A -> B) -> GeneratorOf<B> { 
    return GeneratorOf { 
     return generator.next().map(f) 
    } 
} 

func one<X>(x:X?) -> GeneratorOf<X> { 
    return GeneratorOf(GeneratorOfOne(x)) 
}

的代碼是從書「函數式編程的雨燕採取克里斯Eidhof，弗洛裏安·庫格勒和沃特Swierstra

來源

2015-04-29 Sam Clewlow

看來這主要是一個Swift的具體問題。它可能是一個常見的編程問題，但是代碼引用了特定語言的符號。編程網站會更合適。 – babou

由於這種算法的表達方式需要對Swift編程語言有充分的理解，因此它不適合[cs.se]。因此，我將它轉移到[所以]在主題上作爲理解一小段代碼的問題。 – Gilles

好的，謝謝澄清和遷移。 –

給定一個數組[A_1，...，A_N]，代碼：

生成子數組[a_2，...，a_n];
對於每個子陣列B [A_2，...，A_N]（遞歸生成），生成[A_1] + B.

例如，給定陣列[1,2,3]，我們：

Generate [2,3];對於[2,3]（即[3]和[2]）的每個子數組B，生成[1] + B（這生成[1,3]和[1,2]）。

來源

2015-04-29 17:39:49

感謝您的解釋，這真的很有幫助。你能解釋一下你用來分解算法以瞭解它的過程嗎？ –

我剛剛讀了代碼。它也有助於瞭解代碼試圖完成什麼。更一般地說，如果你被困住了，你應該嘗試運行一些代碼並查看它們輸出的內容 - 在代碼中添加調試打印輸出。這可以幫助你瞭解發生了什麼。 –

瞭解涉及生成器的遞歸函數

回答

相關問題