书接上回。在上篇文章中,我们的火星探测器已经可以解析命令字符串,并且按照命令执行探测任务。新的功能要求我们在这个基础上,增加记录探测器历史位置信息的功能,以保留一份活动位置记录,以避免后期在某个区域重复探测。
分析
使用我们主流的编程语言,上述功能可以很简单的实现,比如采用如下两个方式:
- 定义一个全局变量,保存历史位置信息,每次移动探测器时,添加最近的位置信息
- 在 MarsRover 类中新添一个变量,保存历史位置信息,每次移动都将最近的位置信息添加到变量中
上述两种方式都可以正确的实现功能。但是在我们函数式编程的大背景下,使用是上述任一种方式,都是与函数式编程的理念相违背的: 纯函数的实现是没有副作用的,即不会修改全局状态,也不会修改参数的状态。那有什么办法呢?
不论使用何种范式的编程语言,有一些公共的问题都是在程序中需要解决的,例如异常处理,IO,全局状态等需要副作用的场景。只是不同的语言解决问题的方式不同。函数式编程在解决如上述问题时,有自己的思路。Monad就是函数式编程语言用来解决上述问题的利器。
Monad
从本质上理解 Monad,需要范畴论(Category Theory)的知识,这也导致了 Monad 不太容易理解。简单的讲,Monad 是封装了一个计算上下文(Computation Context), 正是因为这一点,monad 也被称为“可编程的分号”。
有一个类型的 Monad,大部分人都应该都有过了解。那就是Maybe Monad。Maybe 在很多语言里面都有对应的实现。Java 8 中对应的实现为java.util.Optional。Optional 代表一个可能存在的值,针对两种不同的存在状态,同一个方法调用会有不同的执行逻辑, 例如:
Optional<Integer> integer = Optional.of("123").map(str -> Integer.parseInt(str));
Optional<Integer> empty = Optional.<String>empty().map(str -> Integer.parseInt(str));
如果我们查看 Optional 的源码,可以看到 map 方法的实现,针对了两种不同的存在状态做了不同的处理。这就是 Optional 所包含的所谓计算上下文,也是 Monad 的价值所在。
public<U> Optional<U> map(Function<? super T, ? extends U> mapper) {
Objects.requireNonNull(mapper);
if (!isPresent())
return empty();
else {
return Optional.ofNullable(mapper.apply(value));
}
}
类似的,我们也可以通过 Monad 来实现保存 MarsRover 的历史位置数据。
实现
首先,我们先定义 Log 数据类型。 按照功能要求,我们的 Log 是一些列的坐标点。
然后,我们定义一个自己的 monad:
newtype Logger a = Logger (a, Log)
deriving (Show)
execLogger :: Logger a -> (a, Log)
execLogger (Logger (a, log)) = (a, log)
record :: MarsRover -> Logger MarsRover
record marsRover = Logger (marsRover, [point])
where point = getPosition marsRover
我们定义的 monad 是一个新的数据类型 Logger,包含了 MarsRover 实例,和它对应的历史位置信息。同时,我们定义了:
-
execLogger 方法
用来从 Logger 中提取出 rover 和历史位置数据。
-
record 方法
记录 rover 当前位置信息,返回包含当前 rover 和当前坐标的 Logger 对象
下面是 Logger monad 的实现:
instance Monad Logger where
return a = Logger (a, [])
m >>= k = let (a, x) = execLogger m
n = k a
(b, y) = execLogger n
in Logger (b, x ++ y)
我们实现了两个 monad typeclass 定义的方法:
-
return
用来将 MarsRover,转换成一个 Logger,也是我们 monad 实例的创建函数
-
(»=)
这里封装了我们的计算上下文,也就是累积保存位置信息的逻辑。(»=)函数接受两个参数,第一个参数是 Logger,亦即当前状态数据(rover+历史位置数据)。第二个参数是下一步要执行的操作。从(»=)的实现来看,首先使用 execLogger 提取出当前状态,历史状态信息保存为 x,rover 信息保存为 a;然后,执行下一步操作,操作结果为 n;再次用 execLogger 提取出操作结果,得到这一步产生的状态信息 y 和新的 rover 信息 b,然后将最终结果 b 和累积的位置数据 x++y 返回出去。
定义好了我们的 monad 后,对应的我们的 run 方法也要做些许的修改:
run :: Maybe Command -> MarsRover -> Logger MarsRover
run command rover =
case command of
Just L -> return $ turnLeft rover
Just L -> return $ turnRight rover
Just M -> (move' rover) >>= record
Nothing -> return rover
where move' rover = return (move rover)
在新版本的 run 方法中,方法的返回值改成了我们的 Logger 类型,毕竟返回值里面是要包含我们的历史位置信息的。内部实现上并没有太大的变化,只是通过 return 来把返回值转换为 Logger,对于 move 操作来说,move 之后,记录下当前位置。
因为我们是要解析命令字符串,执行一系列指令,我们定义了一个用来将一系列指令顺序在 rover 上执行的方法 apply:
apply :: Logger MarsRover -> [MarsRover -> Logger MarsRover] -> Logger MarsRover
apply rover actions = case actions of
[] -> rover
(x:xs) -> apply (rover >>= x) xs
apply 函数接受 2 个参数,第一个是一个 Logger 对象,包含 rover 的初始状态。第二个参数是一个数组,代表要执行在 rover 上的指令。返回的是 Logger 对象,包含了 rover 的最终状态和历史位置信息。
我们可以通过如下方式验证结果:
main :: IO()
main = do
let rover = MarsRover (0, 0) S
let actions = map run $ map parse "MLMRMLMRM"
let result = apply (record rover) actions
putStrLn $ show result
-- Logger (MarsRover (2,-3) S,[(0,0),(0,-1),(1,-1),(1,-2),(2,-2),(2,-3)])
上述输出中的[(0,0),(0,-1),(1,-1),(1,-2),(2,-2),(2,-3)]即为探测器的历史位置信息。
查看完整代码,看这里
本篇文章是函数式编程系列之一:
- 函数式编程 101
- 函数式编程 101 (续)
- 函数式编程初体验 一
- 函数式编程初体验 二
- 函数式编程初体验 三