活动模式小例（三）

作者: 顾远山 | 来源:发表于2021-01-10 22:59 被阅读0次

Applied Active Pattern in F# (3)

原创：顾远山
著作权归作者所有，转载请标明出处。

前文提要

活动模式允许你通过定义命名分区对输入数据进行分割，并在模式匹配表达式中如可区分联合一般使用。命名分区可直观地描述输入数据是什么，而分割则决定输入数据如何被利用。活动模式是F#语言的一个特性，它可用于按需把数据分割成不同模式继而被后续模式匹配逻辑所利用，灵活且强大。
《活动模式小例（一）》

在实际项目中，活动模式的应用场景很多，包括各类解析器，比如日志解析器、网页解析器、XML解析器、JSON解析器等，这些工具能助力后续的数据分析任务。另外，活动模式也广泛用于领域特定语言编译器的实现，其本质也是解析器，不过它在此场景解析的是操作指令。
《活动模式小例（二）》

小例（一）仅对活动模式进行了介绍。小例（二）利用活动模式实现了一个日期解析器把短日期格式的字符串分割转换成预定义的日期格式。接下来本文将通过活动模式实现一个简单的操作指令解析器以演示活动模式在特定领域语言编译器实现中的便捷之处。

问题描述

本例借用Day 12 - Advent of Code 2020的第二部分作为问题，通过活动模式实现的指令解析器作为解决方案。题目原文略长（详见文末），为方便理解，笔者对其简述如下：

现有船一艘、航路点一只，航路点仅相对船移动或旋转，船仅朝航路点方向相对原点移动。系统通过执行导航指令集操控航路点和船在海上航行。导航指令集由一系列指令串联而成，每个指令分为两部分：方向和给定值，其中方向是大写字母一只，给定值是整数一只。全部指令类型如下：

N表示将航路点相对船向北移动给定值。
S表示将航路点相对船向南移动给定值。
E表示将航路点相对船向东移动给定值。
W表示将航路点相对船向西移动给定值。
L表示将航路点绕船向左（逆时针）旋转给定度数。
R表示将航路点绕船向右（顺时针）旋转给定度数。
F表示将船相对原点朝航路点方向（前）移动给定值的倍数。

船始于原点，航路点始于船以东10个单位长度以北1个单位长度。完整导航指令集如下：

完整的导航指令集

求导航指令集被执行完毕后船相对原点的曼哈顿距离。

高阶设计

实际上这个问题的逻辑非常清晰，可简单分解成下列步骤：

输入船和航路点的当前位置；
执行一条导航指令；
输出船和航路点的新位置；
重复步骤1-3，直到所有导航指令执行完毕；
根据船的最终位置计算曼哈顿距离。

逻辑的关键是步骤1-3，而关键中的关键则是步骤2。步骤2可继续分解成更小的子步骤：

2.1 解析导航指令

2.2 根据指令类型，操控航路点和船的移动

由于指令本身是个字符串，具体又分成七种类型，且每种类型的指令对应的导航操控各不相同，这正是活动模式典型的应用场景，于是思路跃然纸上：

通过活动模式进行指令数据的分割，抽取出指令中的方向和给定值；
通过模式匹配为不同的活动模式（指令类型）实现导航操控逻辑，以移动航路点和船。

综上，易得高阶设计如下：

高阶设计

图中最核心的部分就是针对指令类型的七个活动模式。

利用活动模式实现

本例基于活动模式的指令解析器只是定义分割转换数据的手段，它在整个设计中起到承上启下的作用。上有读入指令，下有操控船和航路点移动（转动），基于函数调用的次序，我们先实现需要被活动模式调用的操控逻辑——移动航路点、转动航路点和移动船。

为了操控航路点的移动和转动，我们需要定义方向类型Direction如下：

type Direction = North|South|East|West|Left|Right //航路点的移动和转动只有东南西北左右六个方向

航路点只能朝东南西北四个方向移动给定值的距离，易得函数moves如下：

let moves direction distance waypoint = 
    let x, y = waypoint           //通过模式匹配得到航路点的横坐标与纵坐标
    match direction with          //对东南西北四个方向进行模式匹配
    | North -> x, y + distance    //向北移动，纵坐标加上给定值的距离
    | South -> x, y - distance    //向南移动，纵坐标减去给定值的距离
    | East -> x + distance, y     //向东移动，横坐标加上给定值的距离
    | West -> x - distance, y     //向西移动，横坐标减去给定值的距离

其中direction为移动的方向，distance为移动的距离，航路点的横坐标x和纵坐标y的值随着移动方向的不同而变化。

另外，航路点只能朝左右两个方向旋转给定的度数，易得函数rotates如下：

let rec rotates direction degrees waypoint = 
    let rotateOnce direction waypiont =                 //子函数，实现旋转一次的逻辑
        let x, y = waypiont                             //通过模式匹配得到航路点的横坐标与纵坐标
        match direction with                            //对左右两个方向进行模式匹配
        | Left  -> y * (-1), x                          //向左旋转，更新横坐标和纵坐标
        | Right -> y, x * (-1)                          //向右旋转，更新横坐标和纵坐标
    match degrees with                                  //本函数开始，对旋转的度数进行模式匹配
    | 0 -> waypoint                                     //旋转角度为0，跳出递归
    | _ -> waypoint |> rotateOnce direction             //旋转一次
                    |> rotates direction (degrees - 90) //旋转角度递减90°重新调用本函数继续旋转

这是个递归函数。由于旋转的度数总是90°的倍数，所以我们把旋转一次的逻辑抽取出来成为子函数rotateOnce，而旋转多次则在旋转一次之后继续调用它自身，只是后续旋转的度数按90°逐次递减，当旋转的度数减为0之时，跳出递归。

船的移动相对简单，只能朝航路点方向移动相对位置给定值的倍数，易得函数movesBy如下：

let movesBy waypoint distance ship = 
        let (x, y), (x', y') = ship, waypoint    //通过模式匹配得到船和航路点的横坐标和纵坐标
        x + x' * distance, y + y' * distance     //根据相对位置和给定值更新船的横坐标和纵坐标

需要留意的是，同样都是横坐标和纵坐标，船(x,y)以原点为中心，而航路点(x',y')以船为中心，故航路点和船的相对位置恰为其坐标。

船和航路点的操纵逻辑实现完毕，我们就可以通过活动模式把它们和导航指令关联起来了。

导航指令总是一行行类似N12或R270的字符串，为了让解析过程更便捷，我们不妨先引入两个简单的辅助活动模式如下：

正则表达式匹配活动模式(|RegexMatch|_)（代码略，详见《小例（二）》）
整型活动模式 let (|INT|) (str:string) = str |> int

于是针对指令类型的七个活动模式可以定义如下：

let (|N|S|E|W|L|R|F|) instruction = 
    match instruction with                //对目标指令进行模式匹配
    | RegexMatch @"^(.)(\d+)$"            //用正则表达式匹配，第一个分组的值代表指令方向
        [_;direction;INT value] ->        //第二个分组的值被整型活动模式匹配并抽取成整型
        match direction with              //对指令方向进行模式匹配
        | "N" -> N value                  //返回代表指令方向向北的活动模式N和给定值
        | "S" -> S value                  //返回代表指令方向向南的活动模式S和给定值
        | "E" -> E value                  //返回代表指令方向向东的活动模式E和给定值
        | "W" -> W value                  //返回代表指令方向向西的活动模式W和给定值
        | "L" -> L value                  //返回代表指令方向向左的活动模式L和给定值
        | "R" -> R value                  //返回代表指令方向向右的活动模式R和给定值
        | _ -> F value                    //返回代表指令方向向前的活动模式F和给定值

需要区分清楚以下几点：

North（Direction类型）是航路点的移动方向
"N"（string类型）是指令方向是导航指令N12的一部分
N（Choice<int>类型）是活动模式(|N|S|E|W|L|R|F|)的一部分

虽然从某些角度理解它们有一定的通性，但仅限于语义层面，对于计算机而言，它们是完全不同的概念。

活动模式定义完毕之后，我们就可以把指令解析为活动模式，并把它们和后端的处理逻辑连接起来，故得单步指令执行函数step如下：

let step instruction ship waypoint =         
    match instruction with
    | N distance -> ship, waypoint |> moves North distance        //航路点向北移动给定值距离
    | S distance -> ship, waypoint |> moves South distance        //航路点向南移动给定值距离
    | E distance -> ship, waypoint |> moves East distance         //航路点向东移动给定值距离
    | W distance -> ship, waypoint |> moves West distance         //航路点向西移动给定值距离
    | L degrees  -> ship, waypoint |> rotates Left degrees        //航路点向左旋转给定值角度
    | R degrees  -> ship, waypoint |> rotates Right degrees       //航路点向右旋转给定值角度
    | F distance -> ship |> movesBy waypoint distance, waypoint   //船向航路点移动给定值倍数

上述函数中instruction为字符串类型的导航指令，通过活动模式进行模式匹配，按照不同的指令类型关联操控船和航路点的移动和转动。step函数返回一个（二元）元组类型，第一部分为单步指令执行后船相对原点的位置，第二部分为单步指令执行后航路点相对船的位置。

我们再通过一个递归函数walkFrom调用单步指令执行函数step，把导航指令集中所有指令顺序逐个执行，如下：

let rec walkFrom startPostitions instructions = 
    let ship, waypoint = startPostitions            //通过模式匹配得到船和航路点的起始位置
    match instructions with                         //对导航指令集进行模式匹配
    | [] -> ship                                    //导航指令集为空，跳出递归，返回船的终末位置
    | firstInstruction :: restInstructions ->       //通过模式匹配得到第一条指令及其余指令集
        let nextPositions = step firstInstruction ship waypoint //执行单步指令得到船和航路点的新位置
        walkFrom nextPositions restInstructions     //调用自身以船和航路点的新位置为起始位置执行其余指令集

最后由船相对原点的位置，我们可以通过getManhattanDistance函数得到题目要求的曼哈顿距离，如下：

let getManhattanDistance position =
    match position with                                    //通过船的位置进行模式匹配
    | x, y when x < 0  && y < 0  -> x * (-1) + y * (-1)    //第三象限
    | x, y when x < 0  && y >= 0 -> x * (-1) + y           //第二象限
    | x, y when x >= 0 && y < 0  -> x + y * (-1)           //第四象限
    | x, y -> x + y                                        //第一象限

上面的逻辑直接用绝对值函数亦可实现。

至此，题目的答案呼之欲出，如下：

let start = (0,0),(10,1)
let instructions = /* ... 略 */
let answer = walkFrom start instructions

题目本身可以直接用if-else实现逻辑，之所以利用活动模式，是因为它可以把前端的指令解析和后端的操纵逻辑解耦，换来更大的灵活性。

另外，得益于F#语言内建的类型推断和模型匹配，以上解决方案的实现代码噪音少，相当接近自然语言（英文），易读性强，非常适用于技术人员与业务人员的交流。

笔者选了GitHub上对此问题中单步指令执行逻辑用其他编程语言下（星标最多）的实现代码，仅作对比。

上述C#的代码虽然已经用上了.NET 5上C# 9最新的模式匹配，但仍存在不少噪音，干扰代码的易读性。

Python

Python

上述Python代码足够简单，但笔者相信，不符合业务逻辑的一层套一层的if-else，加上各种语言特定的运算符，业务人员应该不易看懂。

我们再回过头来看看F#的代码：

let step instruction ship waypoint =         
    match instruction with
    | N distance -> ship, waypoint |> moves North distance        //航路点向北移动给定值距离
    | S distance -> ship, waypoint |> moves South distance        //航路点向南移动给定值距离
    | E distance -> ship, waypoint |> moves East distance         //航路点向东移动给定值距离
    | W distance -> ship, waypoint |> moves West distance         //航路点向西移动给定值距离
    | L degrees  -> ship, waypoint |> rotates Left degrees        //航路点向左旋转给定值角度
    | R degrees  -> ship, waypoint |> rotates Right degrees       //航路点向右旋转给定值角度
    | F distance -> ship |> movesBy waypoint distance, waypoint   //船向航路点移动给定值倍数

waypoint moves north distance（中文：航路点向北移动某段距离）
waypoint rotates left degrees（中文：航路点向左旋转某个角度）
ship moves by waypoint distance（中文：船向航路点移动某段距离）

差不多接近直白的自然语言，会点英文的业务人员基本能看懂。

当然，想让别人看不懂，F#的step函数随时可以变成下面这样，本质不变，只是换个名字而已，看客瞬间就能抓瞎。

所以无论如何还是尽量保持良好的代码规范比较合适，这样代码的可读性更高一些。

结语

企业项目实践中，活动模式可用于前端输入和后端逻辑的解耦
前端输入通过活动模式解析后可以利用模式匹配连接后端逻辑
利用F#的语言特性，解耦的代码可以接近业务的领域专用语言

附：问题原文

--- Day 12: Rain Risk ---

Your ferry made decent progress toward the island, but the storm came in faster than anyone expected. The ferry needs to take evasive actions!

Unfortunately, the ship's navigation computer seems to be malfunctioning; rather than giving a route directly to safety, it produced extremely circuitous instructions. When the captain uses the PA system to ask if anyone can help, you quickly volunteer.

The navigation instructions (your puzzle input) consists of a sequence of single-character actions paired with integer input values.

Almost all of the actions indicate how to move a waypoint which is relative to the ship's position:

Action N means to move the waypoint north by the given value.
Action S means to move the waypoint south by the given value.
Action E means to move the waypoint east by the given value.
Action W means to move the waypoint west by the given value.
Action L means to rotate the waypoint around the ship left (counter-clockwise) the given number of degrees.
Action R means to rotate the waypoint around the ship right (clockwise) the given number of degrees.
Action F means to move forward to the waypoint a number of times equal to the given value.

The waypoint starts 10 units east and 1 unit north relative to the ship. The waypoint is relative to the ship; that is, if the ship moves, the waypoint moves with it.

For example:

F10
N3
F7
R90
F11

These instructions would be handled as follows:

F10 moves the ship to the waypoint 10 times (a total of 100 units east and 10 units north), leaving the ship at east 100, north 10. The waypoint stays 10 units east and 1 unit north of the ship.
N3 moves the waypoint 3 units north to 10 units east and 4 units north of the ship. The ship remains at east 100, north 10.
F7 moves the ship to the waypoint 7 times (a total of 70 units east and 28 units north), leaving the ship at east 170, north 38. The waypoint stays 10 units east and 4 units north of the ship.
R90 rotates the waypoint around the ship clockwise 90 degrees, moving it to 4 units east and 10 units south of the ship. The ship remains at east 170, north 38.
F11 moves the ship to the waypoint 11 times (a total of 44 units east and 110 units south), leaving the ship at east 214, south 72. The waypoint stays 4 units east and 10 units south of the ship.

After these operations, the ship's Manhattan distance from its starting position is 214 + 72 = 286.

Figure out where the navigation instructions actually lead. What is the Manhattan distance (sum of the absolute values of its east/west position and its north/south position) between that location and the ship's starting position?

实在看不懂可以用谷歌翻译，不过出来的结果基本上是塑料中文，仅供参考。

活动模式小例（三）

Applied Active Pattern in F# (3)

前文提要

问题描述

高阶设计

利用活动模式实现

结语

附：问题原文

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

架构算法设计模式和编程理论

函数式编程 FP Functional Progamming · Lambda 演算 · Y 组合子

F#