TRA

TRA-4

Tip: 按 function 类型直接引用成员方法

背景: 全局方法

在 Swift 中实名函数可以直接用作 function 类型, 这在 functional 编程中非常有用.

例如: Array.sort(by:) 接受一个类型为 (Element, Element) -> Bool 的 comparator, 如果我们有一个函数就是这样的类型, 那么可以如下直接调用.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/// 奇数始终在偶数前
func compare(_ lhs: Int, _ rhs: Int) -> Bool {
  switch (lhs.isMultiple(of: 2), rhs.isMultiple(of: 2)) {
    case (true, true), (false, false):
      return lhs < rhs
    case (_, let isEven):
      return isEven
  }
}

var array = [1, 2, 3, 4, 5, 6]
array.sort(by: compare)  
// 等价于
array.sort {
  compare($0, $1)
}

问题: 成员方法

在实际开发中, 我们不可能把所有方法定义成全局的 free function 或 static function, 而是会把逻辑定义成某个类型的实例方法. 这种情况下, 也有办法直接引用方法的名字, 而不用显式创建一个临时的 closure.

self 不是 comparator 的参数

当我们想引用的成员函数, 其显式的参数和返回值与接受的 function 类型一致, 那么可以直接用 obj.foo 的方式引用. 当 function 为 non-escaping 时, 且 obj 为 self 时, 可进一步省略, 直接传递 foo.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Manager {
  var storage = [0, 1, 2, 3, 4]

  private func compare(_ lhs: Int, _ rhs: Int) -> Bool {
    /// 省略
  }
}

extension Manager {
  func perform() {
    storage.sort(by: compare)
    // 等价于
    storage.sort(by: self.compare)
    // 等价于
    storage.sort {
      self.compare($0, $1)
    }
  }
}

这种 Swift 语法称为 partial application: 在上述的例子中, 为了实际执行 compare, 我们本需要提供 self 和 lhs, rhs 3 个参数, 但是我们在传递给 sort 时, 只"部分地"提供了 self 参数, 而不提供 lhs 和 rhs, 这也是 “partial” 的含义.

通用地:
一个 Object 类型的任何实例成员方法 foo, 如果其签名是 (Param0, Param1, Param2...) -> ReturnType.
那么对一个该类型的对象 object, 可以直接引用 object.foo, 得到的是一个隐式创建的 closure, 其类型就是 (Param0, Param1, Param2...) -> ReturnType.
需要注意, 当 Object 是 class 时, 这里创建的隐式 closure 从语义上对 self 有一个强引用, 注意使用时不要在 code 中产生循环强引用.

self 是 comparator 的参数

有时候我们想引用的成员函数, 显式的参数和返回值与接受的 function 类型本不一致, 但算上隐式的 self 后, 就一致了. 这种情况也是很常见的, 例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Answer {
  let grade: Int
  init(_ grade: Int) {
    self.grade = grade
  }

  func isBetter(than another: Answer) -> Bool {
    grade > another.grade
  }
}

var answers = [Answer(10), Answer(50), Answer(100)]
answers.sort {
  $0.isBetter(than: $1)
}

如果我们也不想显式传建一个临时 closure, 那么我们可以使用类型名而不是对象名作为 qualifier 来引用这个方法, 例如 Answer.isBetter.
这种引用方式非 full-application, 也非 partial-application, 而是 non-application.

在目前的 Swift 语言实现下, 一个 Object 类型的任何实例成员方法 foo, 如果其签名是 (Param0, Param1, Param2...) -> ReturnType.
那么直接引用 Object.foo, 也会得到一个 closure. 但需要注意, 其类型并不是 (Object, Param0, Param1, Param2...) -> ReturnType, 而是它的 curried 形式: (Object) -> (Param0, Param1, Param2...) -> ReturnType.

因此, 针对上面这个例子, 是无法直接引用 Answer.isBetter的. 试图调用 answers.sort(by: Answer.isBetter) 会产生编译错误.

此时, 在条件允许的情况下, 我们可以通过定义一个泛型的自定义的运算符, 把 curried 形式的函数转化为非 curried 形式, 之后就可以传递给目标参数了. 这本身也是 functional programming 的一个应用.

1
2
3
4
5
6
7
8
9
10
11
prefix operator ~

// 针对二元操作
prefix func ~ <A, B, C>(_ curried: @escaping (A) -> (B) -> C) -> (A, B) -> C {
  return { lhs, rhs in
    curried(lhs)(rhs)
  }
}

/// 此时可以直接引用成员函数名
answers.sort(by: ~Answer.isBetter)

Receive: Swift UI 布局系统探究

iOS 13 时, Apple 引入了原生 Swift framework SwiftUI. 他的优点十分明显, 但学习曲线并不平坦. 我个人认为, 至少有 2 个方面需要初学者花时间熟悉:

  • 数据驱动. SwiftUI 针对不同生命期的 data, 提供了一系列 property wrapper, 在描述 View 时, UI 和 data 之间会创建隐式的绑定. 理解不同的 data wrapper 和驱动机制是关键之一.
  • 布局系统. 和 UIKit 中显式或依赖 constraints 自动地操纵 frame/bounds 不同, SwiftUI 通过嵌套不同的 View 对象和调用 modifiers 来完成布局的描述. 从本质上说, 这是一个黑盒, 而 Apple 的文档并不特别详尽(尽管最近的几个版本 Apple 已经在改善文档方面作出了巨大的努力).

针对后一个问题, 整个社区始终在不断的学习和研究之中. Objc.io 之前推出的一本书籍和最近的一系列 video “SwiftUI Layout Explained” 对系统性地理解 SwiftUI 的布局流程有很大帮助.

Algorithm: N-皇后问题

题目

来自 leetcode

1
2
3
4
5
6
7
8
9
10
11
12
The n-queens puzzle is the problem of placing n queens on an n x n chessboard 
such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, 
where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example:
  Input: n = 4
  Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
  Explanation: There exist two distinct solutions.

解答

使用深度遍历和回溯技巧即可完成所有可能布局的遍历, 这里给出递归方式的实现.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
func solveNQueens(_ n: Int) -> [[String]] {
  /// 存放每一行 queen 的列号, 初始化和所有后续操作都维护了以下不变量: 它一定是某个 0..<n 的排列
  var placed = Array(0..<n)
  /// 最终返回的所有的结果
  var allResults: [[String]] = []

  /// 将当前布局 data 转换成结果 string
  func flush() {
    var rows: [String] = []
    for row in 0..<n {
      var characters = Array<Character>(repeating: ".", count: n)
      characters[placed[row]] = "Q"
      rows.append(String(characters))
    }
    allResults.append(rows)
  }

  // 核心的递归方法
  // 递归不变量:
  // 在每次该方法进入前, 我们保证当前 0..<depth 行的数据都是合法的
  func checkRecursive(_ depth: Int) {
    // 递归终结
    if depth == n {
      flush()
      return
    }

    // 递归逻辑: 
    // 由于前 0..<depth 的数据已经正确, 只需要考虑第 depth 行
    for exchangeIndex in depth..<n {
      // 第 depth 行可能的列号, 一定选自剩余未排列的列号之一
      if validate(depth, exchangeIndex) {
        placed.swapAt(depth, exchangeIndex)
        checkRecursive(depth + 1)
        // 回溯, 撤销前面的 swap 操作
        placed.swapAt(depth, exchangeIndex)
      }
    }
  }

  // 检查下一行, 如果将之和第 targetIndex 行的数据交换, 结果否合法
  func validate(_ depth: Int, _ targetIndex: Int) -> Bool {
    let target = placed[targetIndex]
    // 由于我们选择的数据结构, 天然保证了每行和每列不可能出现 2 个 queen, 只需要检查对角线方向
    for index in 0..<depth {
      if depth - index == abs(target - placed[index]) {
        return false
      }
    }
    return true
  }

  // main entry point
  checkRecursive(0)
  return allResults
}

这里的核心优化是选取了一个适当的数据结构来表示可能的的棋盘布局, 来省略大量的逻辑判断.