读书笔记《functional-kotlin》函数式编程入门

Chapter 2. Getting Started with Functional Programming

函数式编程在过去五年里一直在软件行业掀起波澜，每个人都想跟风。函数式 programming 比较古老，从 1950 年代开始使用 Lisp 被考虑第一种编程语言（或者至少是第一种引入功能特性的语言）仍然存在为Common Lisp，和其他方言，例如Scheme和< span class="strong">Clojure。

在本章中，我们将介绍以下主题：

What is functional programming?
Basic concepts
Functional collections
Implementing a functional list

What is functional programming?

函数式编程是一种范式（一种结构化程序的风格）。本质上，focus 是用表达式转换数据（理想情况下，这样的表达式不应该有副作用）。它的名称，函数式，是基于数学函数的概念（不在子例程、方法或过程中）。数学函数定义了一组输入和输出之间的关系。每个输入只有一个输出。例如，给定一个函数，f(x) = X²; f(5) 总是 25。

在编程语言中，保证 calling 带有参数的函数始终返回相同值的方法是避免访问可变状态：

fun f(x: Long) : Long { 
   return x * x // no access to external state
}

f 函数不访问任何外部状态；因此，调用 f(5) 将始终返回 25：

fun main(args: Array<String>) {
    var i = 0

    fun g(x: Long): Long {
       return x * i // accessing mutable state
    }

    println(g(1)) //0
    i++
    println(g(1)) //1
    i++
    println(g(1)) //2
}

另一方面，g 函数依赖于可变状态并返回不同的值。

现在，在现实生活中的程序（内容管理系统（CMS< /span>)、购物车或聊天)、state 更改。因此，在函数式编程风格中，状态管理必须明确且谨慎。稍后将介绍在函数式编程中管理状态更改的技术。

函数式编程风格将为我们提供以下好处：

Code is easy to read and test: Functions that don't depend on external mutable state are more accessible to reason about and to prove
State and side effects are carefully planned: Limiting state management to individual and specific places in our code makes it easy to maintain and refactor
Concurrency gets safer and more natural: No mutable state means that concurrency code needs less or no locks around your code

Basics concepts

函数式编程由一些定义明确的概念组成。随后将简要介绍这些概念，随后将在接下来的章节中深入介绍每个概念。

First-class and higher-order functions

函数式编程最基本的概念是一等函数。支持一等函数的编程语言会将函数视为任何其他类型；这样的 languages 将允许您将函数用作变量、参数、返回、泛化类型等。说到parameters和return，一个使用或返回other 函数是一个高阶函数。

Kotlin 支持这两个概念。

让我们尝试一个简单的函数（在 Kotlin 的文档中，这种函数被命名为 lambda）：

val capitalize = { str: String -> str.capitalize() }

fun main(args: Array<String>) {
   println(capitalize("hello world!"))
}

capitalize lambda 函数的类型是 (String) ->字符串;换句话说，capitalize 将采用 String 并返回另一个 String——在这种情况下，一个大写的 String。

作为 lambda 函数，capitalize 可以使用带参数的括号执行（或根本不带参数，视情况而定）。

但是 (String) -> String 类型是什么意思？

(字符串) -> String 是 Function1 , Function1 是 Kotlin 标准库中定义的接口。 Function1<P1, R> 有一个方法， invoke(P1): R，它被标记为一个操作符（我们稍后会介绍运算符）。

Kotlin 的编译器可以在编译时将快捷语法翻译成一个完全成熟的函数对象（实际上，编译器会应用更多的优化），如下所示：

val capitalize = { str: String -> str.capitalize() }

它等价于以下代码：

val capitalize = object : Function1<String, String> {
   override fun invoke(p1: String): String {
      return p1.capitalize()
   }
}

正如您可以看到的，capitalize 值的主体位于内部 invoke 方法。

在 Kotlin 中，lambda 函数也可以用作其他函数的参数。

让我们看一下下面的例子：

fun transform(str:String, fn: (String) -> String): String {
   return fn(str)
}

transform(String, (String) -> String) 函数接受一个 String 并对其应用 lambda 函数.

出于所有意图和目的，我们可以概括 transform：

fun <T> transform(t: T, fn: (T) -> T): T {
   return fn(t)
}

使用 transform 非常简单。看看下面的代码片段：

fun main(args: Array<String>) {
    println(transform("kotlin", capitalize))
}

我们可以直接将 capitalize 作为参数传递，很棒的东西。

有更多方法可以调用 transform 函数。让我们尝试更多：

fun reverse(str: String): String {
   return str.reversed()
}

fun main(args: Array<String>) {
    println(transform("kotlin", ::reverse))
}

reverse 是一个函数；我们可以使用double 冒号（::）如下：

object MyUtils {
   fun doNothing(str: String): String {
      return str
   }
}

fun main(args: Array<String>) {
    println(transform("kotlin", MyUtils::doNothing))
}

doNothing 是一个对象方法，在这种情况下，我们在 MyUtils 之后使用 :: 对象名称：

class Transformer {
   fun upperCased(str: String): String {
      return str.toUpperCase()
   }

   companion object {
      fun lowerCased(str: String): String {
         return str.toLowerCase()
      }
   }
}

fun main(args: Array<String>) {
    val transformer = Transformer()

    println(transform("kotlin", transformer::upperCased))

    println(transform("kotlin", Transformer.Companion::lowerCased))
}

我们还可以传递对实例或伴随对象方法的引用。但可能最常见的情况是直接传递一个 lambda：

fun main(args: Array<String>) {
    println(transform("kotlin", { str -> str.substring(0..1) }))
}

使用 it 隐式参数有一个较短的版本，如下所示：

fun main(args: Array<String>) {
    println(transform("kotlin", { it.substring(0..1) }))
}

it 是一个隐式参数（您没有显式声明它），可以在 lambdas 中使用，只需一个参数。

Note

尽管在所有情况下都使用 it 很诱人，但是一旦您开始将它与连续或嵌套的 lambda 一起使用，它们可能难以阅读。谨慎使用它，并且在清楚它是哪种类型时使用它（不是双关语）。

如果函数接收 lambda 作为最后一个参数，则 lambda 可以在括号外传递：

fun main(args: Array<String>) {
    println(transform("kotlin") { str -> str.substring(0..1) })
}

此功能开启了创建领域特定语言 (DSL ) 与 Kotlin。

你知道Ruby的 unless流控制语句吗？ unless 是一个控制语句，如果条件为 false 则执行一段代码；这是一种否定的 if 条件，但没有 else 子句。

让我们通过执行以下代码片段为 Kotlin 创建一个版本：

fun unless(condition: Boolean, block: () -> Unit){
   if (!condition) block()
}

fun main(args: Array<String>) {
    val securityCheck = false // some interesting code here

    unless(securityCheck) {
        println("You can't access this website")
    }
}

unless 接收条件作为布尔值并阻塞以作为 lambda 执行 () ->单位（无参数，无返回）。当 unless 被执行时，它看起来就像任何其他 Kotlin 的控制流结构。

现在，类型别名可以与函数混合，用来代替简单的接口。举个例子，我们的 Machine<T> interface 来自Chapter 1< /a>, Kotlin – 数据类型、对象和类：

interface Machine<T> {
   fun process(product: T)
}

fun <T> useMachine(t: T, machine: Machine<T>) {
   machine.process(t)
}

class PrintMachine<T> : Machine<T> {
   override fun process(t: T) {
      println(t)
   }
}

fun main(args: Array<String>) {
    useMachine(5, PrintMachine())

    useMachine(5, object : Machine<Int> {
       override fun process(t: Int) {
          println(t)
       }
    })
}

它可以替换为类型别名并与函数的所有语法特征一起使用：

typealias Machine<T> = (T) -> Unit

fun <T> useMachine(t: T, machine: Machine<T>) {
   machine(t)
}

class PrintMachine<T>: Machine<T> {
   override fun invoke(p1: T) {
      println(p1)
   }
} 

fun main(args: Array<String>) {
    useMachine(5, PrintMachine())

    useMachine(5, ::println)

    useMachine(5) { i ->
        println(i)
    }
}

Pure functions

纯函数没有副作用，也没有内存，也没有 I/O。纯函数有很多属性，包括引用透明、缓存（memoization）、和其他（我们将在接下来的章节中介绍这些功能）。

可以在 Kotlin 中编写纯函数，但编译器不像在其他语言中那样强制执行它。您可以创建纯函数来享受它的好处。因为 Kotlin 不强制执行纯函数，所以许多程序员说 Kotlin 不是真正的函数式编程工具，也许他们是对的。是的，Kotlin 不强制执行纯函数式编程，这为您提供了极大的灵活性，包括以纯函数式编写的能力，如果您愿意的话。

Recursive functions

递归函数是调用自身的函数 , 有某种条件来停止执行。在 Kotlin 中，递归函数维护一个堆栈，但可以使用 tailrec 修饰符进行优化。

让我们看一个示例，factorial 函数的实现。

首先，让我们看一下以下代码片段中典型的命令式实现、循环和状态更改：

fun factorial(n: Long): Long {
   var result = 1L
   for (i in 1..n) {
      result *= i
   }
   return result
}

它没有什么花哨的，也没有特别优雅的。现在，让我们看一下递归实现，没有循环，也没有状态变化：

fun functionalFactorial(n: Long): Long {
   fun go(n: Long, acc: Long): Long {
      return if (n <= 0) {
         acc
      } else {
         go(n - 1, n * acc)
      }
   }

   return go(n, 1)
}

我们使用内部递归函数； go 函数调用自身，直到达到一个条件。如您所见，我们从最后一个 n 值开始，并在每次递归迭代中减少它。

一个优化的实现是类似的，但带有 tailrec 修饰符：

fun tailrecFactorial(n: Long): Long {
   tailrec fun go(n: Long, acc: Long): Long {
      return if (n <= 0) {
         acc
      } else {
         go(n - 1, n * acc)
      }
   }

   return go(n, 1)
}

为了测试哪个实现更快，我们可以编写一个穷人的 man profiler 函数：

fun executionTime(body: () -> Unit): Long {
   val startTime = System.nanoTime()
   body()
   val endTime = System.nanoTime()
   return endTime - startTime
}

对于我们的目的， executionTime 函数是可以的，但任何严肃的生产 code 应该使用适当的分析工具进行分析，例如 Java Microbenchmark Harness ( JMH）：

fun main(args: Array<String>) {
    println("factorial :" + executionTime { factorial(20) })
    println("functionalFactorial :" + executionTime { functionalFactorial(20) })
    println("tailrecFactorial :" + executionTime { tailrecFactorial(20) })
}

这是前面代码的输出：

tailrec 优化版本甚至比普通命令式版本更快。但是 tailrec 并不是一个能让你的代码运行得更快的魔法咒语。作为一般规则， tailrec 优化后的代码将比未优化的版本运行得更快，但并不总是优于旧的命令式代码。

让我们探索一个斐波那契实现，从 imperative 开始，如下所示：

fun fib(n: Long): Long {
   return when (n) {
      0L -> 0
      1L -> 1
      else -> {
         var a = 0L
         var b = 1L
         var c = 0L
         for (i in 2..n) {
            c = a + b
            a = b
            b = c
         }
         c
      }
   }
}

现在，让我们看一下函数式递归实现：

fun functionalFib(n: Long): Long {
   fun go(n: Long, prev: Long, cur: Long): Long {
      return if (n == 0L) {
         prev
      } else {
         go(n - 1, cur, prev + cur)
      }
   }

   return go(n, 0, 1)
}

现在我们来看看它对应的 tailrec 版本，如下：

fun tailrecFib(n: Long): Long {
   tailrec fun go(n: Long, prev: Long, cur: Long): Long {
      return if (n == 0L) {
         prev
      } else {
         go(n - 1, cur, prev + cur)
      }
   }

   return go(n, 0, 1)
}

再一次，让我们用 executionTime 来分析它：

fun main(args: Array<String>) {
    println("fib :" + executionTime { fib(93) })
    println("functionalFib :" + executionTime { functionalFib(93) })
    println("tailrecFib :" + executionTime { tailrecFib(93) })
}

输出将如下所示：

tailrec 实现比递归版本快得多，但不如普通的命令式实现快。

Lazy evaluation

一些函数式语言提供 lazy（非严格）evaluation 模式。 Kotlin 默认使用 eager (strict) 评估。

Kotlin 不作为语言本身的一部分提供对惰性求值的原生支持，而是作为 Kotlin 标准库和语言的一部分 feature 命名为 delegate properties（我们将在以后的章节中详细介绍）：

fun main(args: Array<String>) {
    val i by lazy {
        println("Lazy evaluation")
        1
    }

    println("before using i")
    println(i)
}

输出将类似于以下屏幕截图：

在 by 保留字之后，lazy() 高级函数接收一个 (( ) -> T) 初始化 lambda 函数将在第一次访问 i 时执行。

但也可以将普通的 lambda 函数用于一些惰性用例：

fun main(args: Array<String>) {
    val size = listOf(2 + 1, 3 * 2, 1 / 0, 5 - 4).size
}

如果我们尝试执行这个表达式，它将抛出 ArithmeticException 异常，因为我们正在除以零：

fun main(args: Array<String>) {
    val size = listOf({ 2 + 1 }, { 3 * 2 }, { 1 / 0 }, { 5 - 4 }).size
}

执行这个没有问题。有问题的代码没有被执行，实际上使其成为 lazy 评估。

Functional collections

功能集合是集合通过高阶函数与其元素交互的方式。函数式集合具有常见的操作名称，例如 filter、map 和 fold;这些名称是按约定定义的（类似于设计模式），并且正在多个库和语言中实现。

不要与纯函数式数据结构混淆——一种用纯函数式语言实现的数据结构。纯函数式数据结构是不可变的，并使用 lazy 评估和其他函数式技术。

函数式集合可以但不一定是纯粹的函数式数据结构。我们已经介绍了算法的命令式实现如何比函数式实现更快。

Kotlin 带有一个优秀的函数式集合库。让我们看一下：

val numbers: List<Int> = listOf(1, 2, 3, 4)

我们的值 numbers 作为一个 List<Int> 类型。现在，让我们按如下方式打印其成员：

fun main(args: Array<String>) {
    for(i in numbers) {
       println("i = $i")
    }
}

到目前为止，一切都很好，但它看起来并不是很实用。

不要再担心了； Kotlin 集合包括许多接收 lambda 以对其成员进行操作的函数。我们可以用 lambda 替换这个循环，如下所示：

fun main(args: Array<String>) {
    numbers.forEach { i -> println("i = $i") }
}

现在，让我们在以下代码中转换我们的集合：

val numbers: List<Int> = listOf(1, 2, 3, 4)

fun main(args: Array<String>) {
    val numbersTwice: List<Int> = listOf()

    for (i in numbers) {
       numbersTwice.add(i * 2) //Compilation error: Unresolved reference: add 
    }
}

此代码无法编译； numberTwice 没有 add(T) 方法。 List<T> 是一个不可变的列表；初始化后可以修改。要将元素添加到列表中，它必须具有不同的类型——在我们的例子中是 MutableList<T>：

val numbers: List<Int> = listOf(1, 2, 3, 4)

fun main(args: Array<String>) {
    val numbersTwice: MutableList<Int> = mutableListOf()

    for (i in numbers) {
        numbersTwice.add(i * 2) //Nice!
    }
}

MutableList<T> 扩展 List<T>;它添加了修改集合本身的方法，例如add(T)、remove(T)、清除等。

所有主要的 Kotlin 集合类型（List<T>、Set<T> 和 Map< ;K, V>）具有可变子类型（MutableList 、 MutableSet<T> 和 < code class="literal">MutableMap）。

但是我们可以将这个 transformation 替换为单行表达式，如下面的代码所示：

val numbers: List<Int> = listOf(1, 2, 3, 4)

fun main(args: Array<String>) {
    val numbersTwice: List<Int> = numbers.map { i -> i * 2 }
}

map 操作可以让你转换（技术上将一个值映射到另一个）。这段代码有很多优点，也干净了很多，现在 numbersTwice 值是一个List<Int> ;list，而不是 MutableList<T> list。

让我们再举几个例子。我们可以使用循环对数字的所有元素求和：

val numbers: List<Int> = listOf(1, 2, 3, 4)

fun main(args: Array<String>) {
    var sum = 0

    for (i in numbers) {
       sum += i
    }

    println(sum)    
}

它可以减少到只有一行，具有不可变的 sum 值，如下所示：

val numbers: List<Int> = listOf(1, 2, 3, 4)

fun main(args: Array<String>) {
    val sum = numbers.sum()

    println(sum)    
}

很好，但并不有趣，所以让我们提高赌注：

val numbers: List<Int> = listOf(1, 2, 3, 4)

fun main(args: Array<String>) {
    val sum = numbers.fold(0) { acc, i -> acc + i }

    println(sum)
}

fold 方法迭代一个集合，保留一个累加器值。 fold 以一个 T 值作为初始值；在第一次迭代中，这个初始值将是累加器，随后的迭代将使用 lambda 的返回值作为下一个累加器值：

val numbers: List<Int> = listOf(1, 2, 3, 4)

fun main(args: Array<String>) {
    val sum = numbers.fold(0) { acc, i ->
        println("acc, i = $acc, $i")
        acc + i
    }

    println(sum)
}

输出将类似于以下屏幕截图：

类似于 fold，reduce 使用 accumulator 但没有初始值：

val numbers: List<Int> = listOf(1, 2, 3, 4)

fun main(args: Array<String>) {
    val sum = numbers.reduce { acc, i ->
        println("acc, i = $acc, $i")
        acc + i
    }

    println(sum)
}

输出将类似于以下屏幕截图：

fold 和 reduce 在 foldRight 和 reduceRight 从最后一项开始迭代到第一项。

Implementing a functional list

借助我们在前两章中学习的所有内容，我们可以实现一个纯函数式列表：

sealed class FunList<out T> {
   object Nil : FunList<Nothing>()

   data class Cons<out T>(val head: T, val tail: FunList<T>) : FunList<T>()
}

FunList 类是密封类；只有两个可能的子类存在——Nil，一个空列表（在其他书籍中你可以看到它被定义为 Null 或 Empty) 和 Cons（一个结构，名称继承自 Lisp，包含两个值）。

T类型被标记为out；这是为了方差，我们将在以后的章节中讨论方差。

Nil 是一个对象（我们不需要 Nil 的不同实例）扩展 FunList< Nothing>（请记住，Nothing 是 Kotlin 类型层次结构的底部）。

Cons 值包含两个值——head，单个 T , 和 tail，一个 FunList<T>;因此，它可以是 Nil value 或另一个 Cons。

让我们创建一个列表实例，如下所示：

import com.packtpub.functionalkotlin.chapter02.FunList.Cons
import com.packtpub.functionalkotlin.chapter02.FunList.Nil

fun main(args: Array<String>) {
    val numbers = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
}

它是功能性的，但不是很可读。我们可以创建一个更好的初始化函数：

import com.packtpub.functionalkotlin.chapter02.FunList.Cons
import com.packtpub.functionalkotlin.chapter02.FunList.Nil

fun intListOf(vararg numbers: Int): FunList<Int> {
   return if (numbers.isEmpty()) {
      Nil
   } else {
      Cons(numbers.first(), intListOf(*numbers.drop(1).toTypedArray().toIntArray()))
   }
}

这里有很多新东西。 argument 数字被标记为 vararg，这意味着我们可以调用这个函数有尽可能多的参数。出于所有意图和目的， numbers 是一个 IntArray 值（一种特殊类型的数组）。如果 numbers 为空，我们可以返回 Nil。如果没有，我们可以提取第一个元素作为我们的 head value 并为 intLisfOf文字">尾值。为了提取 tail 值，我们使用 drop 方法并将其结果转换为 IntArray 值。但是我们不能直接将任何数组作为 vararg;因此，我们必须使用展开 (*) 运算符来单独传递数组的每个成员。

现在，我们可以创建我们的 FunList<Int> 值：

fun main(args: Array<String>) {
    val numbers = intListOf(1, 2, 3, 4)    
}

让我们实现 forEach 如下：

sealed class FunList<out T> {
   object Nil : FunList<Nothing>()

   data class Cons<out T>(val head: T, val tail: FunList<T>) : FunList<T>()

   fun forEach(f: (T) -> Unit) {
      tailrec fun go(list: FunList<T>, f: (T) -> Unit) {
         when (list) {
            is Cons -> {
               f(list.head)
               go(list.tail, f)
            }
            is Nil -> Unit//Do nothing
         }
      }

      go(this, f)
   }

}

forEach 实现类似于我们在递归部分中的 Factorial 和 Fibonacci 函数示例，包括 tailrec。

FunList 在技术上是一种代数数据类型 (<强>ADT）。 FunList 可以是 Nil 或 Cons，仅此而已。 Kotlin 的编译器可以使用此信息来检查当 FunList type 用作 when 控制结构中的参数：

fun main(args: Array<String>) {
    val numbers = intListOf(1, 2, 3, 4)

    numbers.forEach { i -> println("i = $i") }
}

实现 fold 将类似于以下代码：

sealed class FunList<out T> {

  /*Previous code here*/

   fun <R> fold(init: R, f: (R, T) -> R): R {
      tailrec fun go(list: FunList<T>, init: R, f: (R, T) -> R): R = when (list) {
         is Cons -> go(list.tail, f(init, list.head), f)
         is Nil -> init
      }

      return go(this, init, f)
   }
}

您是否注意到这些功能非常容易实现？让我们看一下下面的代码：

fun main(args: Array<String>) {
    val numbers = intListOf(1, 2, 3, 4)

    val sum = numbers.fold(0) { acc, i -> acc + i}
}

Kotlin 的列表和我们的功能列表之间的小竞赛怎么样？

fun main(args: Array<String>) {
    val funList = intListOf(1, 2, 3, 4)
    val list = listOf(1, 2, 3, 4)

    println("fold on funList : ${executionTime { funList.fold(0) { acc, i -> acc + i } }}")
    println("fold on list : ${executionTime { list.fold(0) { acc, i -> acc + i } }}")
}

输出将类似于以下屏幕截图：

哎哟!我们的实现慢了 10 倍。不用担心，Kotlin 的实现是一个经过高度优化的命令式解决方案，而我们的实现只是为了学习和获得乐趣（双关语）。

map 呢？要以 functional 方式实现 map 我们需要先实现其他功能.让我们从 reverse 开始。

reverse 是一个以相反顺序返回列表的函数：

sealed class FunList<out T> {

    /*previous code*/

    fun reverse(): FunList<T> = fold(Nil as FunList<T>) { acc, i -> Cons(i, acc) }
}

我们可以重用 fold 并在每次迭代中构建一个新的 Cons 值，使用 acc value 为 tail。这是函数式编程的一大优势——重用现有函数。

现在，我们可以实现 foldRight：

sealed class FunList<out T> {

    /*previous code*/

  fun <R> foldRight(init: R, f: (R, T) -> R): R {
   return this.reverse().fold(init, f)
  }
}

同样，我们正在重用现有功能。是时候实现我们的 map 函数了。在这一点上，我们将重用现有函数也就不足为奇了：

sealed class FunList<out T> {

 /*previous code*

 fun <R> map(f:(T) -> R): FunList<R> {
   return foldRight(Nil as FunList<R>){ tail, head -> Cons(f(head), tail) }
 }
}

foldRight 就是我们所需要的。如您所见，我们可以使用函数和其他基本概念作为构建块来实现一个完整的列表。这就是函数式编程的全部内容。

Summary

在本章中，我们介绍了函数式编程的基础知识，包括高阶函数、纯函数、递归函数和惰性求值。我们还介绍了函数式集合，并使用函数式编程风格实现了函数式集合。

在下一章中，我们将介绍函数式编程的基石——不变性。

vlambda博客
学习文章列表