algorithm - 了解涉及生成器的递归函数

Question

我遇到了以下用 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))
}

代码摘自 Chris Eidhof、Florian Kugler 和 Wouter Swierstra 合着的“Functional Programming in Swift”一书

Answer 1

给定一个数组 [a_1,…,a_n]，代码:

• 生成子数组 [a_2,…,a_n];
• 对于 [a_2,…,a_n] 的每个子数组 B(递归生成)，生成 [a_1] + B。

例如，给定数组 [1,2,3]，我们:

• 生成 [2,3]；
• 对于 [2,3] 的每个子数组 B(即 [3] 和 [2])，生成 [1] + B(这生成 [1,3] 和 [1,2])。