“分而治之”思想在 Scala 中的应用

摘要

本文简要介绍“分而治之”思想在 Scala 中的一个应用，希望给大家一些灵感。

源自一个问题

Scala 中的 List 内置了一个方法 ::: 来连接两个相同类型的 List

scala> List(1,2,3) ::: List(4,5)
res2: List[Int] = List(1, 2, 3, 4, 5)

那么我们如何自己来编写一个函数实现该功能呢？

“分而治之”

怎么来实现“分而治之”呢？
这里我们使用模式匹配（pattern matching）来实现分的部分，然后在每个 case 的后面具体的实现“治”

scala> def append[T](xs: List[T], ys: List[T]): List[T] = 
     | xs match {
     | case List() => ys
     | case x :: xs1 => x :: append(xs1, ys)
     | }
append: [T](xs: List[T], ys: List[T])List[T]

append 函数的输入参数是两个 T 类型的 List（这里的 T 代表类型参数，表明 List 中的元素是 T 类型的），返回的仍然是 List[T]，我们对第一个 List 进行“分”，通过 match 实现，然后对每种匹配到的情况进行“治”，如果是空的 List 那么直接返回第二个传进来的 List；如果匹配到的是 x :: xs1，即 T 类型的 x 和一个 List[T] 连接形成的 List[T]（例如 1::List(2,3) 的结果就是 List(1,2,3)），就返回 x :: append(xs1, ys) ，即递归调用

scala> append(List(1,2,3), List(4,5))
res4: List[Int] = List(1, 2, 3, 4, 5)

实际的实现过程其实是：

1 :: 2 :: 3 :: List(4, 5)  // 1 :: (2 :: (3 :: List(4, 5)))  括号可以省略

至此，我们使用模式匹配简单的实现了这种“分而治之”的思想

总结

希望该思想能够帮助大家解决实际编程中遇到的类似问题，当然不限于您使用的是哪种变成语言

本文参考：Programming in Scala, 3rd Edition 16.6 FIRST-ORDER METHODS ON CLASS LIST 阅读本书的一些想法会第一时间和大家分享