Scala Learning(4): Currying柯里化的推演

本文展示加法和乘法的两个例子,最后使用MapReduce的思想把两者统一成一个带Currying的表达形式。

从high-order functions推演到Currying

原始方法

def sum(f: Int => Int, a: Int, b: Int): Int =
  if (a > b) 0
  else f(a) + sum(f, a + 1, b)

表示从a到b,把每个int做一次f处理,把所有结果累加起来。

对应”加法”、”立方”、”阶乘”,实现三个funtion

def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
def fact(x: Int): Int = if (x == 0) 1 else fact(x - 1)

把这三个方法填充到原始的sum方法里,得到三个新方法

def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubes(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)

将前两个简化,把function匿名地传入sum里,得到

def sumInts(a: Int, b: Int) = sum(x => x, a, b)
def sumCubes(a: Int, b: Int) = sum(x => x * x * x, a, b)

写起来更简短一些。

进一步的,我们注意到a: Int,b: Int这俩参数在各个实现里都是从左到右带过去的,可以简化地重新实现原始的sum方法

def sum(f: Int => Int): (Int, Int) => Int = {
  def sumF(a: Int, b: Int): Int =
    if (a > b) 0
    else f(a) + sumF(a + 1, b)
  sumF
}

如此,新的sum方法传入一个f,返回值也是一个function,借助新的sum,上面三个方法可以这样实现

def sumInts = sum(x => x)
def sumCubes = sum(x => x * x * x)
def sumFactorials = sum(fact)

使用如

sumCubes(1, 10) + sumFactorials(10, 20)

本质上就是Currying的形式了,展开是:

def sum(f: Int => Int)(a: Int, b: Int): Int = ...

类型是什么呢?
类型是

(Int => Int) => (Int, Int) => Int

右侧也就是Int,即

Int => Int => Int

Int => (Int => Int)

MapReduce例子

回到加法的例子:

MapReduce例子

回到加法的例子,用Currying的方式改写为:

def sum(f: Int => Int)(a: Int, b: Int): Int =
  if (a > b) 0
  else f(a) + sum(f)(a + 1, b)

用Currying类似写一个乘法:

def product(f: Int => Int)(a: Int, b: Int): Int =
  if (a > b) 1
  else f(a) * product(f)(a + 1, b)

注意到,两者在初始值、else分支的计算处理上有所不同,使用MapReduce的思想把两个计算统一起来:

def mapReduce(f: Int => Int, combine: (Int, Int) => Int, initValue: Int)(a: Int, b: Int) : Int = 
  if (a > b) initValue
  else combine(f(a), mapReduce(f, combine, initValue)(a+1, b))

把product套进去,可以表示为

def product(f: Int => Int)(a: Int, b: Int): Int =
  mapReduce(f, (x, y) => x*y, 1)(a, b)

把sum套进去,可以表示为

def sum(f: Int => Int)(a: Int, b: Int): Int =
  mapReduce(f, (x, y) => x+y, 0)(a, b)

全文完 :)

上一篇:全球首例!通过植入电极向腿部发射信号,让瘫痪者重新行走、游泳、骑行


下一篇:GraphX实现N度关系