iOS 开发每天分享优质文章ios 知识点

探索reduce函数的起源

2019-06-04  本文已影响0人  iOS_小久

今天我们加入了乌特勒支大学助理教授Wouter Swierstra,他是Functional Swift的合着者。他工作的一个领域是函数式编程,他很高兴看到来自这个领域的一些想法,人们已经在很长一段时间内工作,正在成为像Swift这样的主流语言。

我们将在几集中共同探讨函数式编程的兔子洞。更具体地说,我们将关注reduce。为了提醒自己是什么reduce,我们先写一些例子。

减少的例子

我们创建一个数组,用于保存从1到10的数字,我们调用reduce它来查找数组中的最大数字。该函数有两个参数:初始结果值,以及将单个数组元素与结果组合在一起的函数。我们传入尽可能小Int的初始值,我们max用于组合函数:

let numbers = Array(1...10)
numbers.reduce(Int.min, max) // 10

我们还可以reduce通过传入零和+运算符来计算所有元素的总和:

numbers.reduce(0, +) // 55

让我们仔细看看reduceon 的函数签名Array

func reduce<Result>(_ initialResult: Result, _ nextPartialResult: (Result, Self.Element) throws -> Result) rethrows -> Result

该函数在其Result类型上是通用的。在上面两个例子中,结果类型和数组元素的Int类型都是,但这些类型不必匹配。例如,我们还可以reduce用来确定数组是否包含元素。这个reduce电话的结果是Bool

extension Sequence where Element: Equatable {
    func contains1(_ el: Element) -> Bool {
        return reduce(false) { result, x in
            return x == el || result
        }
    }
}

numbers.contains1(3) // true
numbers.contains1(13) // false

我们调用reduce初始结果false,因为如果数组为空,这必须是结果。在组合函数中,我们检查传入的元素是否等于我们正在寻找的元素,或者到目前为止的结果是否相等true

这个版本contains不是最高效的,因为它做的工作比它需要的多。然而,找到一个使用的实现是一个有趣的练习reduce

名单

但是reduce从哪里来的?我们可以通过定义单链表并reduce在其上查找操作来探索其起源。

在Swift中,我们将链表定义为枚举,其中包含空列表的大小写和非空列表的大小写。传统上称为非空情况cons,其关联值是单个列表元素和尾部。尾部是另一个列表,它使案例递归,因此我们必须将其标记为间接:

enum List<Element> {
    case empty
    indirect case cons(Element, List)
}

我们可以创建一个整数列表,如下所示:

let list: List<Int> = .cons(1, .cons(2, .const(3, .empty)))

然后我们定义一个名为的函数fold,看起来很像reduce,但它有点不同:

extension List {
    func fold<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {

    }
}

这两个论点fold与两个案例相匹配并不是偶然的List。在函数的实现中,我们使用每个参数及其相应的大小写:

extension List {
    func fold<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {
        switch self {
        case .empty:
            return emptyCase
        case let .cons(x, xs):
            return consCase(x, xs.fold(emptyCase, consCase))
        }
    }
}

现在我们可以fold在列表中计算其元素的总和:

list.fold(0, +) // 6

我们还可以fold用来查找列表的长度:

list.fold(0, { _, result in result + 1 }) // 3

在论证fold和宣言之间存在对应关系List

我们可以将enum案例List视为构造列表的两种方法:一种是构造一个空列表,另一种是构造一个非空列表。

并且fold有两个参数:一个用于.empty案例,一个用于.cons案例 - 正是我们为了计算每个案例的结果所需的信息。

如果我们认为emptyCase参数不是类型的值Result,而是作为函数() -> Result,那么与.empty构造函数的对应关系变得更加清晰。

折叠与减少

fold功能几乎是相同的reduce,但有一个小的区别。可以通过调用两个函数并比较结果来证明两者之间的差异。

首先我们调用fold,传递两个案例的构造函数List作为参数:

dump(list.fold(List.empty, List.cons))

/*
▿ __lldb_expr_4.List<Swift.Int>.cons
  ▿ cons: (2 elements)
    - .0: 1
    ▿ .1: __lldb_expr_4.List<Swift.Int>.cons
      ▿ cons: (2 elements)
        - .0: 2
        ▿ .1: __lldb_expr_4.List<Swift.Int>.cons
          ▿ cons: (2 elements)
            - .0: 3
            - .1: __lldb_expr_4.List<Swift.Int>.empty
*/

我们看到结果与原始列表完全相同。换句话说,fold使用两个case构造函数调用是一种编写身份函数的复杂方法:没有任何改变。

然后我们reduce一个数组,传入相同的构造函数List- 除了我们必须交换conscase 的参数的顺序,因为首先reduce传递累积结果而第二个传递当前元素:

dump(Array(1...3).reduce(List.empty, { .cons($1, $0) }))

/*
▿ __lldb_expr_6.List<Swift.Int>.cons
  ▿ cons: (2 elements)
    - .0: 3
    ▿ .1: __lldb_expr_6.List<Swift.Int>.cons
      ▿ cons: (2 elements)
        - .0: 2
        ▿ .1: __lldb_expr_6.List<Swift.Int>.cons
          ▿ cons: (2 elements)
            - .0: 1
            - .1: __lldb_expr_6.List<Swift.Int>.empty
*/

当我们检查这个reduce调用的结果时,我们看到它List是以相反的顺序包含数组元素,因为reduce遍历数组并将每个元素处理成结果。这与什么不同fold,因为它从左到右穿过链表,并且仅emptyCase当它到达列表的最末端时才使用该值。

有很多操作,比如计算总和或长度,reducefold给出相同的结果。但是通过秩序重要的操作,我们开始看到两个函数的行为差异。

List.reduce

我们已经实现了fold,我们已经使用过Swift Array.reduce,但看看它的实现也很有意思List.reduce。我们在扩展中编写函数,并给它们相同的参数fold

extension List {
    func reduce<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {
        // ...
    }
}

为了实现该功能,我们将emptyCase参数分配给初始结果,然后我们切换列表以查看它是否为空。如果它是空的,我们可以立即返回结果。如果列表是非空的,我们将x元素添加到我们到目前为止使用consCase函数看到的结果中,并且我们递归调用reduce尾部,传递累积的结果:

extension List {
    func reduce<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {
        let result = emptyCase
        switch self {
        case .empty:
            return result
        case let .cons(x, xs):
            return xs.reduce(consCase(x, result), consCase)
        }
    }
}

尾递归

在这里我们可以看到它reduce是尾递归的:它要么返回一个结果,要么立即进行递归调用。fold不是尾递归,因为它调用consCase函数,并且递归或多或少被隐藏并用于构造该函数的第二个参数。

这种差异导致了不同的结果,现在通过比较两种方法我们可以更清楚地看到List

let list: List<Int> = .cons(1, .cons(2, .const(3, .empty)))
list.fold(List.empty, List.cons) // .cons(1, .cons(2, .const(3, .empty)))
list.reduce(List.empty, List.cons) // .cons(3, .cons(2, .const(1, .empty)))`

使用尾递归的操作可以很容易地用循环重写:

extension List {
    func reduce1<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {
        var result = emptyCase
        var copy = self
        while case let .cons(x, xs) = copy {
            result = consCase(x, result)
            copy = xs
        }
        return result
    }
}

这个版本reduce1产生的结果与reduce

list.reduce1(List.empty, List.cons) // .cons(3, .cons(2, .cons(1, .empty)))

reduce只是折叠操作的一个例子,我们实际上也可以在许多其他结构上定义这些操作。


到最后小编推荐一个群 691040931 里面有许多的iOS开发者在交流技术分享自己的心得,更有一些资料不定期的分享更新。
资料截图

原文地址:https://talk.objc.io/episodes/S01E150-the-origins-of-reduce

上一篇下一篇

猜你喜欢

热点阅读