函数式地思考来解决问题

在这一章中,我们会查看几个有趣的问题,并尝试用函数式的方式来漂亮地解决他们。我们并不会介绍新的概念,我们只是练习我们刚学到的写程序的技巧。每一节都会探讨不同的问题。会先描述问题,然后用最好的方式解决他。

运算逆波兰表示法(Reverse Polish notation form)

我们在学校学习数学的时候,我们多半都是用中置(infix)的方式来写数学式。例如说,我们会写 10 - (4 + 3) * 2+, *, - 是中置运算子(infix operators)。在 Haskell 中就像是 +elem 一样。这种写法对于人类来说很容易阅读与理解,但缺点是我们必须用括号来描述运算的优先级。

逆波兰表示法是另外一种数学式的描述方法。乍看之下显得怪异,但他其实很容易理解并使用。因为我们不需要括弧来描述,也很容易放进计算机里面运算。尽管现在的计算机都是用中置的方式让你输入,有些人仍坚持用 RPN 的计算机。前述的算式如果表达成 RPN 的话会是 10 4 3 + 2 * -。我们要如何计算他的结果呢?可以想想堆叠,基本上你是从左向右阅读算式。每当碰到一个数值,就把他堆上堆叠。当我们碰到一个运算子。就把两个数值从堆叠上拿下来,用运算子运算两个数值然后把结果推回堆叠中。当你消耗完整个算式的时候,而且假设你的算式是合法的,那你就应该只剩一个数值在堆叠中,

函数式地思考来解决问题 Functionally Solving Problems - 图1

我们再接着看 10 4 3 + 2 * -。首先我们把 10 推到堆叠上,所以堆叠现在是 10。下一个接着的输入是 4,我们也把他推上堆叠。堆叠的状态便变成 10, 4。接着也对下一个输入 3 做同样的事,所以堆叠变成 10, 4, 3。然后便碰到了第一个运算子 +。我们把堆叠最上层的两个数值取下来(所以堆叠变成 10)把两个数值加起来然后推回堆叠上。堆叠的状态便变成 10, 7。我们再把输入 2 推上堆叠,堆叠变成 10, 7, 2。我们又碰到另一个运算子,所以把 72 取下,把他们相乘起来然后推回堆叠上。72 相乘的结果是 14,所以堆叠的状态是 10, 14。最后我们碰到了 -。我们把 1014 取下,将他们相减然后推回堆叠上。所以现在堆叠的状态变成 -4。而我们已经把所有数值跟运算子的消耗完了,所以 -4 便是我们的结果。

现在我们知道我们如何手算 RPN 运算式了,接下来可以思考一下我们写一个 Haskell 的函数,当他接到一个 RPN 运算式,像是 "10 4 3 + 2 * -" 时,他可以给出结果。

这个函数的型别会是什么样呢?我们希望他接受一个字串当作参数,并产出一个数值作为结果。所以应该会是 solveRPN :: (Num a) => String -> a

  1. 小建议:在你去实作函数之前,先想一下你会怎么宣告这个函数的型别能够帮助你厘清问题。在 Haskell 中由于我们有够强的型别系统,光从函数的宣告就可以得到许多信息。

函数式地思考来解决问题 Functionally Solving Problems - 图2

当我们要实作一个问题的解法时,你可以先动手一步一步解看看,尝试从里面得到一些灵感。我们这边把每一个用空白隔开的数值或运算子都当作独立的一项。所以把 "10 4 3 + 2 * -" 这样一个字串断成一串 list ["10","4","3","+","2","*","-"] 应该会有帮助。

接下来我们要如何应用这个断好的 list 呢?我们从左至右来走一遍,并保存一个工作用的堆叠。这样有让你想到些什么可以用的吗?没错,在 folds 的那一章里面,我们提到基本上当你需要从左至右或由右至左走过一遍 list 的时候并产生些结果的时候。我们都能用 fold 来实作他。

在这个 case 中由于我们是从左边走到右边,所以我们采取 left fold。accumulator 则是选用堆叠,而 fold 的结果也会是一个堆叠,只是里面只有一个元素而已。

另外要多考虑一件事是我们用什么来代表我们的堆叠?我们可以用 list 来代替,list 的 head 就可以当作是堆叠的顶端。毕竟要把一个元素加到 list 的 head 要比加到最后要有效率多。所以如果我们有一个堆叠,里面有 10, 4, 3,那我们可以用 [3,4,10] 来代表他。

现在我们有了足够的信息来写出我们的函数。他会接受一个字串 "10 4 3 + 2 * -",随即用 words 来断成 list ["10","4","3","+","2","*","-"]。接下来我们做一个 left fold 来产生出只有一个元素的堆叠,也就是 [-4]。我们把这个元素从 list 取出便是最后的结果。

来看看我们的实作:

  1. import Data.List
  2. solveRPN :: (Num a) => String -> a
  3. solveRPN expression = head (foldl foldingFunction [] (words expression))
  4. where foldingFunction stack item = ...

我们接受一个运算式并把他断成一串 List。然后我们用一个 folding 函数来 fold 这串 list。注意到我们用 [] 来当作起始的 accumulator。这个 accumulator 就是我们的堆叠,所以 [] 代表一个空的堆叠。在运算之后我们得到一个只有一个元素的堆叠,我们调用 head 来取出他并用 read 来转换他。

所以我们现在只缺一个接受堆叠的 folding 函数,像是可以接受 [4,10]"3",然后得到 [3,4,10]。如果是 [4,10]"*",那就会得到 [40]。但在实作之前,我们先把我们的函数改写成 point-free style,这样可以省下许多括号。

  1. import Data.List
  2. solveRPN :: (Num a) => String -> a
  3. solveRPN = head . foldl foldingFunction [] . words
  4. where foldingFunction stack item = ...

看起来好多了。我们的 folding 函数会接受一个堆叠、新的项,并回传一个新的堆叠。我们使用模式匹配的方式来取出堆叠最上层的元素,然后对 "*""-" 做匹配。

  1. solveRPN :: (Num a, Read a) => String -> a
  2. solveRPN = head . foldl foldingFunction [] . words
  3. where foldingFunction (x:y:ys) "*" = (x * y):ys
  4. foldingFunction (x:y:ys) "+" = (x + y):ys
  5. foldingFunction (x:y:ys) "-" = (y - x):ys
  6. foldingFunction xs numberString = read numberString:xs

我们用展开成四个模式匹配。模式会从第一个开始尝试匹配。所以 folding 函数会看看目前的项是否是 "*"。如果是,那就会将 [3,4,9,3] 的头两个元素绑定到 xy 两个名称。所以 x 会是 3y 等于 4ys 便会是 [9,3]。他会回传一个 list,只差在 xy 相乘的结果为第一个元素。也就是说会把最上层两个元素取出,相乘后再放回去。如果第一个元素不是 "*",那模式匹配就会比对到 "+",以此类推。

如果项并未匹配到任何一个运算子,那我们就会假设这个字串是一个数值。如果他是一个数值,我们会用 read 来把字串转换成数值。并把这个数值推到堆叠上。

另外注意到我们加了 Read a 这像 class constraint,毕竟我们要使用到 read 来转换成数值。所以我们必须要宣告成他要属于 NumRead 两种 typeclass。(譬如说 Int,Float 等)

我们是从左至右走过 ["2","3","+"]。一开始堆叠的状态是 []。首先他会用 []"2" 来喂给 folding 函数。由于此项并不是一个运算子。他会用 read 读取后加到 [] 的开头。所以堆叠的状态变成 [2]。接下来就是用 [2]["3"] 来喂给 folding 函数,而得到 [3,2]。最后再用 [3,2]"+" 来调用 folding 函数。这会堆叠顶端的两个数值,加起来后推回堆叠。最后堆叠变成 [5],这就是我们回传的数值。

我们来试试看我们新写的函数:

  1. ghci> solveRPN "10 4 3 + 2 * -"
  2. -4
  3. ghci> solveRPN "2 3 +"
  4. 5
  5. ghci> solveRPN "90 34 12 33 55 66 + * - +"
  6. -3947
  7. ghci> solveRPN "90 34 12 33 55 66 + * - + -"
  8. 4037
  9. ghci> solveRPN "90 34 12 33 55 66 + * - + -"
  10. 4037
  11. ghci> solveRPN "90 3 -"
  12. 87

看起来运作良好。这个函数有一个特色就是他很容易改写来支持额外的运算子。他们也不一定要是二元运算子。例如说我们可以写一个运算子叫做 "log",他会从堆叠取出一个数值算出他的 log 后推回堆叠。我们也可以用三元运算子来从堆叠取出三个数值,并把结果放回堆叠。甚至是像是 "sum" 这样的运算子,取出所有数值并把他们的和推回堆叠。

我们来改写一下我们的函数让他多支持几个运算子。为了简单起见,我们改写宣告让他回传 Float 型别。

  1. import Data.List
  2. solveRPN :: String -> Float
  3. solveRPN = head . foldl foldingFunction [] . words
  4. where foldingFunction (x:y:ys) "*" = (x * y):ys
  5. foldingFunction (x:y:ys) "+" = (x + y):ys
  6. foldingFunction (x:y:ys) "-" = (y - x):ys
  7. foldingFunction (x:y:ys) "/" = (y / x):ys
  8. foldingFunction (x:y:ys) "^" = (y ** x):ys
  9. foldingFunction (x:xs) "ln" = log x:xs
  10. foldingFunction xs "sum" = [sum xs]
  11. foldingFunction xs numberString = read numberString:xs

看起来不错,没有疑问地 / 是除法而 ** 是取 exponential。至于 log 运算子,我们只需要模式匹配一个元素,毕竟 log 只需要一个元素。而 sum 运算子,我们只回传一个仅有一个元素的堆叠,包含了所有元素的和。

  1. ghci> solveRPN "2.7 ln"
  2. 0.9932518
  3. ghci> solveRPN "10 10 10 10 sum 4 /"
  4. 10.0
  5. ghci> solveRPN "10 10 10 10 10 sum 4 /"
  6. 12.5
  7. ghci> solveRPN "10 2 ^"
  8. 100.0

由于 read 知道如何转换浮点数,我们也可在运算适中使用他。

  1. ghci> solveRPN "43.2425 0.5 ^"
  2. 6.575903

有这样一个容易拓展到浮点数而且动到的代码又在十行以内的函数,我想是非常棒的。

有一件事要留意的是这个函数对于错误处理并不好。当我们碰到非法输入的时候,他就会直接当掉。之后我们碰到 Monad 的时候我们会写一个容错的版本,他的型别会是 solveRPN :: String -> Maybe Float。当然我们现在也可以写一个,不过那会有点麻烦,因为会有一大堆检查 Nothing 的动作。如果你希望挑战的话,也可以尽管尝试。(提示:你可以用 reads 来看看一次 read 是否会成功)

路径规划

我们接下来的问题是:你的飞机刚刚降落在英格兰的希思罗机场。你接下来有一个会议,你租了一台车希望尽速从机场前往伦敦市中心。

从希思罗机场到伦敦有两条主要道路,他们中间有很多小路连接彼此。如果你要走小路的话都会花掉一定的时间。你的问题就是要选一条最佳路径让你可以尽快前往伦敦。你从图的最左边出发,中间可能穿越小路来前往右边。

函数式地思考来解决问题 Functionally Solving Problems - 图3

你可以从图中看到,从希思罗机场到伦敦在这个路径配置下的最短路径是先选主要道路 B,经由小路到 A 之后,再走一小段,转到 B 之后继续往前走。如果采取这个路径的话,会花去 75 分钟。如果选其他道路的话,就会花更多时间。

我们任务就是要写一个程序,他接受道路配置的输入,然后印出对应的最短路径。我们的输入看起来像是这样:

  1. 50
  2. 10
  3. 30
  4. 5
  5. 90
  6. 20
  7. 40
  8. 2
  9. 25
  10. 10
  11. 8
  12. 0

我们在心中可以把输入的数值三个三个看作一组。每一组由道路 A,道路 B,还有交叉的小路组成。而要能够这样组成,我们必须让最后有一条虚拟的交叉小路,只需要走 0 分钟就可以穿越他。因为我们并不会在意在伦敦里面开车的成本,毕竟我们已经到达伦敦了。

正如我们在解 RPN 计算机的问题的时候,我们是用三步骤来解题:

  • 首先忘掉 Haskell,想想我们自己是怎么一步步解题的。
  • 想想如何在 Haskell 中表达我们的数据。
  • 在 Haskell 中要如何对这些数据做运算来产生出解答。

在介绍 RPN 计算机的章节中,我们首先自己用人脑计算表达式,在心中维持一个堆叠然后一项一项处理。我们决定用一个字串来表达我们的表达式。最后,我们用 left fold 来走过我们这一串 list,并算出结果。

究竟我们要怎么用手算出从希思罗机场到伦敦的最短路径呢?我们可以观察整章图片,猜测哪一条是最短路径然后希望我们有猜对。这样的作法对于很小的输入可以成功,但如果我们的路径超过 10000 组呢?这样我们不知道我们的解法是不是最佳解,我们只能说可能是。

所以那并不是一个好作法。这边有一张简化过后的图。

函数式地思考来解决问题 Functionally Solving Problems - 图4

你能想出来到道路 A 上第一个交叉点的最短路径吗?(标记成 A1 的点)这太容易了。我们只要看看从道路 A 出发或是从道路 B 出发穿越至道路 A 两种作法哪种比较短就好。很明显的,从道路 B 出发的比较短,只要花费 40 分钟,然而从道路 A 则要花费 50 分钟。那到交叉点 B1 呢?同样的作法可以看出从道路 B 出发只要花费 10 分钟,远比从道路 A 出发然后穿越小路要花费少,后者要花费 80 分钟!

现在我们知道要到达 A1 的最短路径是经由 B 然后邹小路到达,共花费 40。而我们知道要达到 B1 的最短路径则是直接走 B,花费 10。这样的知识有办法帮助我们得知到下一个交叉点的最短路径吗?可以的。

我们来看看到达 A2 的最短路径是什么。要到达 A2,我们必须要从 A1 走到 A2 或是从 B1 走小路。由于我们知道到达 A1 跟 B1 的成本,我们可以很容易的想出到达 A2 的最佳路径。到达 A1 要花费 40,而从 A1 到 A2 需要 5。所以 B, C, A 总共要 45。而要到达 B1 只要 10,但需要额外花费 110 分钟来到达 B2 然后走小路到达 A2。所以最佳路径就是 B, C, A。同样地到达 B2 最好的方式就是走 A1 然后走小路。

  1. 也许你会问如果先在 B1 跨到道路 A 然后走到 A2 的情况呢?我们已经考虑过了从 B1 A1 的情况,所以我们不需要再把他考虑进去。

现在我们有了至 A2 跟 B2 的最佳路径,我们可以一直重复这个过程直到最右边。一旦我们到达了 A4 跟 B4,那其中比较短的就是我们的最佳路径了。

基本上对于第二组而言,我们只是不断地重复之前的步骤,只是我们考虑进在前面的最佳路径而已。当然我们也可以说在第一步就考虑进了前面的最佳路径,只是他们都是 0 而已。

总结一下。要得到从希思罗机场到伦敦的最短路径。我们首先看看到达下一个道路 A 上的交叉点的最短路径。共有两种选择的路径,一是直接从道路 A 出发然后走到交叉点,要不然就是从道路 B 出发,走到第一个交叉点然后走小路。得到结果后记住结果。接着再用同样的方法来得到走到道路 B 上下一个交叉点的最短路径,并也记住结果。然后我们看看要走到再下一个道路 A 上的交叉点,究竟是从这个道路 A 上的交叉点往前走,或是从对应的道路 B 上的交叉点往前走再走到对面,两种选择哪种比较好。记下比较好的选择,然后也对对应的道路 B 上的交叉点做一次这个过程。做完全部组之后就到达最右边。一旦到达最右边,最佳的选择就是我们的最短路径了。

基本上当我们到达最右边的时候,我们记下了最后停在道路 A 的最短路径跟最后停在道路 B 的最短路径。其中比较短的是我们真正的最短路径。现在我们已经知道怎么用手算出答案。如果你有闲工夫,你可以拿纸笔对于任何一组道路配置算出他的最短路径。

接下来的问题是,我们要如何用 Haskell 的型别来代表这里的道路配置呢?一种方式就是把起始点跟交叉点都当作图的节点,并连到其他的交叉点。如果我们想像其实起点也有一条长度为 1 的虚拟道路连接彼此,那每个交叉点或是节点就都连接对面的节点了。同时他们也连到下一个交叉点。唯一的例外是最后一个节点,他们只连接到对面。

  1. data Node = Node Road Road | EndNode Road
  2. data Road = Road Int Node

一个节点要码是一个普通的节点,他包含有通往下一个交叉点的路径信息,还有往对面道路的信息。或是一个终端点,只包含往对面节点的道路信息。一条道路包含他多长,还有他指向哪里。例如说,道路 A 的第一个部份就可写成 Road 50 a1。其中 a1Node x y 这样一个节点。而 xy 则分别指向 B1 跟 A2。

另一种方式就是用 Maybe 来代表往下一个交叉点走的路。每个节点有指到对面节点的路径部份,但只有不是终端节点的节点才有指向下一个交叉点的路。

  1. data Node = Node Road (Maybe Road)
  2. data Road = Road Int Node

这些是用 Haskell 来代表道路系统的方式,而我们也能靠他们来解决问题。但也许我们可以想出更简单的模型?如果我们想想之前手算的方式,我们每次检查都只有检查三条路径的长度而已。在道路 A 的部份,跟在道路 B 的部份,还有接触两个部份并将他们连接起来的部份。当我们观察到 A1 跟 B1 的最短路径时,我们只考虑第一组的三个部份,他们分别花费 50, 10 跟 30。所以道路系统可以用四组来表示:50, 10, 305, 90, 2040, 2, 2510, 8, 0

让我们数据型别越简单越好,不过这样已经是极限了。

  1. data Section = Section { getA :: Int, getB :: Int, getC :: Int } deriving (Show)
  2. type RoadSystem = [Section]

这样很完美,而且对于我们的实作也有帮助。Section 是一个 algebraic data type,包含三个整数,分别代表三个不同部份的道路长。我们也定义了型别同义字,说 RoadSystem 代表包含 section 的 list。

  1. 当然我们也可以用一个 tuple ``(Int, Int, Int)`` 来代表一个 section。使用 tuple 对于一些简单的情况是比较方便,但对于比较复杂的情况定义自己的 algebraic data type 会比较好。他让型别系统获得比较多的信息。``(Int, Int, Int)`` 毕竟也可能被使用在定义三维空间中的一个矢量,只用 tuple 让我们可能把这两种情形混杂起来使用。如果我们用 ``Section`` ``Vector`` 的话就不会不小心搞混了。

从希思罗机场到伦敦的道路系统便可以这样表示:

  1. heathrowToLondon :: RoadSystem
  2. heathrowToLondon = [Section 50 10 30, Section 5 90 20, Section 40 2 25, Section 10 8 0]

我们现在要做的就是用 Haskell 实作我们先前的解法。所以我们应该怎样宣告我们计算最短路径函数的型别呢?他应该接受一个道路系统作为参数,然后回传一个路径。我们会用一个 list 来代表我们的路径。我们定义了 Label 来表示 A, BC。并且也定义一个同义词 Path

  1. data Label = A | B | C deriving (Show)
  2. type Path = [(Label, Int)]

而我们的函数 optimalPath 应该要有 optimalPath :: RoadSystem -> Path 这样的型别。如果被喂给 heathrowToLondon 这样的道路系统,他应该要回传下列的路径:

  1. [(B,10),(C,30),(A,5),(C,20),(B,2),(B,8)]

我们接下来就从左至右来走一遍 list,并沿路上记下 A 的最佳路径跟 B 的最佳路径。我们会 accumulate 我们的最佳路径。这听起来有没有很熟悉?没错!就是 left fold。

当我们手动做解答的时候,有一个步骤是我们不断重复的。就是检查现有 A 跟 B 的最佳路径以及目前的 section,产生出新的 A 跟 B 的最佳路径。举例来说,最开始我们的最佳路径是 [][]。我们看过 Section 50 10 30 后就得到新的到 A1 的最佳路径为 [(B,10),(C,30)],而到 B1 的最佳路径是 [(B,10)]。如果你们把这个步骤看作是一个函数,他接受一对路径跟一个 section,并产生出新的一对路径。所以型别是 (Path, Path) -> Section -> (Path, Path)。我们接下来继续实作这个函数。

  1. 提示:把 ``(Path, Path) -> Section -> (Path, Path)`` 当作 left fold 用的二元函数,fold 要求的型态是 ``a -> b -> a``
  1. roadStep :: (Path, Path) -> Section -> (Path, Path)
  2. roadStep (pathA, pathB) (Section a b c) =
  3. let priceA = sum $ map snd pathA
  4. priceB = sum $ map snd pathB
  5. forwardPriceToA = priceA + a
  6. crossPriceToA = priceB + b + c
  7. forwardPriceToB = priceB + b
  8. crossPriceToB = priceA + a + c
  9. newPathToA = if forwardPriceToA <= crossPriceToA
  10. then (A,a):pathA
  11. else (C,c):(B,b):pathB
  12. newPathToB = if forwardPriceToB <= crossPriceToB
  13. then (B,b):pathB
  14. else (C,c):(A,a):pathA
  15. in (newPathToA, newPathToB)

函数式地思考来解决问题 Functionally Solving Problems - 图5

上面的程序究竟写了些什么?首先他根据先前 A 的最佳解计算出道路 A 的最佳解,之后也如法炮制计算 B 的最佳解。使用 sum $ map snd pathA,所以如果 pathA[(A,100),(C,20)]priceA 就是 120forwardPriceToA 就会是我们要付的成本。如果我们是从先前在 A 上的交叉点前往。那他就会等于我们至先前交叉点的最佳解加上目前 section 中 A 的部份。crossPriceToA 则是我们从先前在 B 上的交叉点前往 A 所要付出的代价。他是先前 B 的最佳解加上 section 中 B 的部份加上 C 的长。同样地方式也可以决定 forwardPriceToBcrossPriceToB

现在我们知道了到 A 跟 B 的最佳路径,我们需要根据这些信息来构造到 A 跟 B 的整体路径。如果直接走到 A 耗费较少的话,我们就把 newPathToA 设置成 (A,a):pathA。这样做的事就是把 Label A 跟 section 的长度 a 接到最佳路径的前面。要记得 A 是一个 label,而 a 的型别是 Int。我们为什么要接在前面而不是 pathA ++ [(A,a)] 呢?因为接在 list 的前面比起接在后端要有效率多了。不过这样产生出来的 list 就会相反。但要把 list 再反过来并不难。如果先走到 B 再穿越小路走到 A 比较短的话,那 newPathToA 就会包含这样走的路线。同样的道理也可以套用在 newPathToB 上。

最后我们回传 newPathToAnewPathToB 这一对结果。

我们把 heathrowToLondon 的第一个 section 喂给我们的函数。由于他是第一个 section,所以到 A 跟 B 的最佳路径就是一对空的 list。

  1. ghci> roadStep ([], []) (head heathrowToLondon)
  2. ([(C,30),(B,10)],[(B,10)])

要记住包含的路径是反过来的,要从右边往左边读。所以到 A 的最佳路径可以解读成从 B 出发,然后穿越到道路 A。而 B 的最佳路径则是直接从 B 出发走到下一个交叉点。

  1. 优化小技巧:当我们写 ``priceA = sum $ map snd pathA`` 的时候。我们是在计算每步的成本。如果我们实作 ``roadStep`` ``(Path, Path, Int, Int) -> Section -> (Path, Path, Int, Int)`` 的话就可以不必那么做。其中的整数型别代表 A B 上的最小成本。

现在我们有了一个函数他接受一对路径跟一个 section,并产生新的最佳路径。我们可以用一个 left fold 来做。我们用 ([],[]) 跟第一个 section 来喂给 roadStep 并得到一对最佳路径。然后他又被喂给这个新得到的最佳路径跟下一个 section。以此类推。当我们走过全部的 section 的时候,我们就会得到一对最佳路径,而其中比较短的那个就是解答。有了这样的想法,我们便可以实作 optimalPath

  1. optimalPath :: RoadSystem -> Path
  2. optimalPath roadSystem =
  3. let (bestAPath, bestBPath) = foldl roadStep ([],[]) roadSystem
  4. in if sum (map snd bestAPath) <= sum (map snd bestBPath)
  5. then reverse bestAPath
  6. else reverse bestBPath

我们对 roadSystem 做 left fold。而用的起始 accumulator 是一对空的路径。fold 的结果也是一对路径,我们用模式匹配的方式来把路径从结果取出。然后我们检查哪一个路径比较短便回传他。而且在回传之前也顺便把整个结果反过来。因为我们先前提到的我们是用接在前头的方式来构造结果的。

我们来测试一下吧!

  1. ghci> optimalPath heathrowToLondon
  2. [(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]

这正是我们应该得到的结果!不过跟我们预期的结果仍有点差异,在最后有一步 (C,0),那代表我们已经在伦敦了仍然跨越小路。不过由于他的成本是 0,所以依然可以算做正确的结果。

我们找出最佳路径的函数,现在要做的只需要从标准输入读取文本形式道路系统,并把他转成 RoadSystem,然后用 optimalPath 来把他跑一遍就好了。

首先,我们写一个函数,他接受一串 list 并把他切成同样大小的 group。我们命名他为 groupOf。当参数是 [1..10] 时,groupOf 3 应该回传 [[1,2,3],[4,5,6],[7,8,9],[10]]

  1. groupsOf :: Int -> [a] -> [[a]]
  2. groupsOf 0 _ = undefined
  3. groupsOf _ [] = []
  4. groupsOf n xs = take n xs : groupsOf n (drop n xs)

一个标准的递归函数。对于 xs 等于 [1..10]n 等于 3,这可以写成 [1,2,3] : groupsOf 3 [4,5,6,7,8,9,10]。当这个递归结束的时候,我们的 list 就三个三个分好组。而下列是我们的 main 函数,他从标准输入读取数据,构造 RoadSystem 并印出最短路径。

  1. import Data.List
  2. main = do
  3. contents <- getContents
  4. let threes = groupsOf 3 (map read $ lines contents)
  5. roadSystem = map (\[a,b,c] -> Section a b c) threes
  6. path = optimalPath roadSystem
  7. pathString = concat $ map (show . fst) path
  8. pathPrice = sum $ map snd path
  9. putStrLn $ "The best path to take is: " ++ pathString
  10. putStrLn $ "The price is: " ++ show pathPrice

首先,我们从标准输入获取所有的数据。然后我们调用 lines 来把 "50\n10\n30\n... 转换成 ["50","10","30"..,然后我们 map read 来把这些转成包含数值的 list。我们调用 groupsOf 3 来把 list 的 list,其中子 list 长度为 3。我们接着对这个 list 来 map 一个 lambda (\[a,b,c] -> Section a b c)。正如你看到的,这个 lambda 接受一个长度为 3 的 list 然后把他变成 Section。所以 roadSystem 现在就是我们的道路配置,而且是正确的型别 RoadSystem。我们调用 optimalPath 而得到一个路径跟对应的代价,之后再印出来。

我们将下列文本存成文件。

  1. 50
  2. 10
  3. 30
  4. 5
  5. 90
  6. 20
  7. 40
  8. 2
  9. 25
  10. 10
  11. 8
  12. 0

存成一个叫 paths.txt 的文件然后喂给我们的程序。

  1. $ cat paths.txt | runhaskell heathrow.hs
  2. The best path to take is: BCACBBC
  3. The price is: 75

执行成功!你可以用你对 Data.Random 的了解来产生一个比较大的路径配置,然后你可以把产生的乱数数据喂给你的程序。如果你碰到堆叠溢出,试试看用 foldl' 而不要用 foldlfoldl' 是 strict 的可以减少内存消耗。