硝烟中的函数式编程 – 一个例子

综合编程 2016-02-28

在之前的两篇函数式编程语言特性的文章(上篇和下篇)中简单介绍了一些基本的函数式编程的概念。对函数式编程有了一些基本的概念,那现实中的函数式编程是什么样子的呢?这里就选取一个比较简单的问题,使用Haskell尝试解决一下,以求近距离的感受下函数之美。

问题

这里采用的是我司一个废弃了很久的面试题目MarsRover,题目内容如下:

A squad of robotic rovers are to be landed by NASA on a plateau on Mars. This plateau, which is curiously rectangular, must be navigated by the rovers so that their on-board cameras can get a complete view of the surrounding terrain to send back to Earth. A rover’s position and location is represented by a combination of x and y co-ordinates and a letter representing one of the four cardinal compass points. The plateau is divided up into a grid to simplify navigation. An example position might be 0, 0, N, which means the rover is in the bottom left corner and facing North. In order to control a rover, NASA sends a simple string of letters. The possible letters are ‘L’, ‘R’ and ’M’. ‘L’ and ‘R’ makes the rover spin 90 degrees left or right respectively, without moving from its current spot. ’M’ means move forward one grid point, and maintain the same heading.

Assume that the square directly North from (x, y) is (x, y+1).

大意是

在直角坐标系内,有一个探测器,探测器有三个状态,X和Y标记探测器所在位置,Direction标记了探测器的前进方向。科学家发送指令L, R, M给探测器,分别表示左转90度,右转90度和前进。 问题就是给定一个初始条件,和一系列命令,求解探测器最终状态。

下面我们看使用Haskell如何解决上述问题。

求解

首先,我们需要定义一些基本的数据类型。

-- 北,东,南,西
data Direction = N | E | S | W
    deriving (Show)

-- 左转,右转,和移动
data Command = L | R | M
    deriving (Show)

-- 位置
type Point = (Int, Int)

-- 探测器
data MarsRover = MarsRover Point Direction
    deriving (Show)

上述定义中的deriving (Show)类似于我们常见的toString。Haskell中定义的类型只有加了上述定义后,才会把对应的数据结构转换成字符串,输出到控制台,才能方便调试以及查看结果。

然后,我们可以定义三个函数turnLeft、turnRight和move,分别对应对探测器的三个操作。

turnLeft :: MarsRover -> MarsRover
turnLeft rover = case rover of
        MarsRover p N -> MarsRover p W
        MarsRover p W -> MarsRover p S
        MarsRover p S -> MarsRover p E
        MarsRover p E -> MarsRover p N

turnRight :: MarsRover -> MarsRover
turnRight rover =
    case rover of
        MarsRover p N -> MarsRover p E
        MarsRover p W -> MarsRover p N
        MarsRover p S -> MarsRover p W
        MarsRover p E -> MarsRover p S

move :: MarsRover -> MarsRover
move rover =
    case rover of
        MarsRover (x, y) N -> MarsRover (x, y+1) N
        MarsRover (x, y) E -> MarsRover (x+1, y) E
        MarsRover (x, y) W -> MarsRover (x-1, y) W
        MarsRover (x, y) S -> MarsRover (x, y-1) S

三个函数定义都是我们之前提到的 纯函数
,函数中使用了 模式匹配
以获取结构体中数据。下述模式匹配的部分实现虽略有繁琐,但逻辑清晰明了。与我们常用的if-else或者switch语句相比较,模式匹配的语法也更简洁。MarsRover类型也是 不可变
的,每次操作都会返回一个新的实例。

我们下面再定义个execute函数,略微做下封装。execute函数本身并没有太多逻辑,只是针对不同command做分发,调用对应的操作函数。

execute :: MarsRover -> Command -> MarsRover
execute rover command =
    case command of
        L -> turnLeft rover
        R -> turnRight rover
        M -> move rover

上述定义了我们所需函数,到了展示我们工作成果的时候了:

main :: IO()
main = do
    putStrLn $ show $ move.turnLeft.move.turnRight.move $ MarsRover (0, 0) S
    -- 输出结果: MarsRover (-1,-2) S

上面我们给定了探测器的初始条件为 坐标(0,0)南向
,然后执行了下列操作:

  1. 前移
  2. 右转
  3. 前移
  4. 左转
  5. 前移

然后我们将探测器的状态转换为字符串输出至控制台,结果为MarsRover (-1,-2) S, 完全正确。

太棒了,简单43行代码,我们就用Haskell完成了题目的功能。我们完成了以下任务:

  • 定义了基本几个 数据类型
  • 定义一系列 纯函数
  • 使用了 模式匹配
    来实现代码功能。
  • 在最后验证的部分,我们利用了函数式编程中 高阶函数
    的特性,使用Haskell中的 函数组合
    函数(.)把对探测器的多步操作组合为一个函数。 比起Java等其他语言中一个一个的函数调用是不是酷帅多了?

有兴趣看代码的同学,可以查看 完整代码

这里我们只实现了部分功能,后续我们将用尝试一些更有意思的事情!

您可能感兴趣的

Higher Kinded Types in Typescript Higher kinded types are not currently possible in typescript but first of all let’s explain why they exist. In functional programming there is the ...
python3 第二十章 – 函数式编程之Higher-order function(高... 什么是高阶函数?把函数作为参数传入,这样的函数称为高阶函数,函数式编程就是指这种高度抽象的编程范式。 在前面的章节中,我们知道可以用abs()这个函数来得到一个数的绝对值,如: print('abs(-100):', abs(-100))以上代码,输出: abs(-10...
python函数式编程之yield表达式形式 先来看一个例子 def foo(): print("starting...") while True: res = yield print("res:",res)g = foo() next(g) 在上面的例子里,因为foo函数中有yie...
函数式编程 101 (续) 上一篇提到了函数式编程语言的两个特点。这里书接上回,我们继续探讨函数式编程语言的其他特点。 尾递归 递归是我们在编程中处理集合时经常用的到的一个技巧,使用递归相对于循环来说可以更容易的实现功能。比如说求一个整数num的阶乘,采用递归可以实现如下: private static In...
Introduction to the suite of JuliaFin packages (pa... As we roll outJuliaPro v0.6.0.1 (now supporting Julia 0.6), we see it as the best time to introduce our old users and new to our productJuliaFin, ...
0
子不语

责编内容来自:子不语 (本文源链)
阅读提示:酷辣虫无法对本内容的真实性提供任何保证,请自行验证并承担相关的风险与后果!
本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。