# 函数式地思考来解决问题

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

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


import Data.List

solveRPN :: (Num a) => String -> a
solveRPN expression = head (foldl foldingFunction [] (words expression))
where   foldingFunction stack item = ...


import Data.List

solveRPN :: (Num a) => String -> a
solveRPN = head . foldl foldingFunction [] . words
where   foldingFunction stack item = ...


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


ghci> solveRPN "10 4 3 + 2 * -"
-4
ghci> solveRPN "2 3 +"
5
ghci> solveRPN "90 34 12 33 55 66 + * - +"
-3947
ghci> solveRPN "90 34 12 33 55 66 + * - + -"
4037
ghci> solveRPN "90 34 12 33 55 66 + * - + -"
4037
ghci> solveRPN "90 3 -"
87


import Data.List

solveRPN :: String -> Float
solveRPN = head . foldl foldingFunction [] . words
where   foldingFunction (x:y:ys) "*" = (x * y):ys
foldingFunction (x:y:ys) "+" = (x + y):ys
foldingFunction (x:y:ys) "-" = (y - x):ys
foldingFunction (x:y:ys) "/" = (y / x):ys
foldingFunction (x:y:ys) "^" = (y ** x):ys
foldingFunction (x:xs) "ln" = log x:xs
foldingFunction xs "sum" = [sum xs]
foldingFunction xs numberString = read numberString:xs


ghci> solveRPN "2.7 ln"
0.9932518
ghci> solveRPN "10 10 10 10 sum 4 /"
10.0
ghci> solveRPN "10 10 10 10 10 sum 4 /"
12.5
ghci> solveRPN "10 2 ^"
100.0


ghci> solveRPN "43.2425 0.5 ^"
6.575903


## 路径规划

50
10
30
5
90
20
40
2
25
10
8
0


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


data Node = Node Road Road | EndNode Road


data Node = Node Road (Maybe Road)


data Section = Section { getA :: Int, getB :: Int, getC :: Int } deriving (Show)


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


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


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


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


提示：把 (Path, Path) -> Section -> (Path, Path) 当作 left fold 用的二元函数，fold 要求的型态是 a -> b -> a。

roadStep :: (Path, Path) -> Section -> (Path, Path)
roadStep (pathA, pathB) (Section a b c) =
let priceA = sum $map snd pathA priceB = sum$ map snd pathB
forwardPriceToA = priceA + a
crossPriceToA = priceB + b + c
forwardPriceToB = priceB + b
crossPriceToB = priceA + a + c
newPathToA = if forwardPriceToA <= crossPriceToA
then (A,a):pathA
else (C,c):(B,b):pathB
newPathToB = if forwardPriceToB <= crossPriceToB
then (B,b):pathB
else (C,c):(A,a):pathA
in  (newPathToA, newPathToB)




optimalPath :: RoadSystem -> Path
in  if sum (map snd bestAPath) <= sum (map snd bestBPath)
then reverse bestAPath
else reverse bestBPath


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


groupsOf :: Int -> [a] -> [[a]]
groupsOf 0 _ = undefined
groupsOf _ [] = []
groupsOf n xs = take n xs : groupsOf n (drop n xs)


import Data.List

main = do
contents <- getContents
let threes = groupsOf 3 (map read $lines contents) roadSystem = map (\[a,b,c] -> Section a b c) threes path = optimalPath roadSystem pathString = concat$ map (show . fst) path
pathPrice = sum $map snd path putStrLn$ "The best path to take is: " ++ pathString
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 而得到一个路径跟对应的代价，之后再印出来。 我们将下列文本存成文件。 50 10 30 5 90 20 40 2 25 10 8 0  存成一个叫 paths.txt 的文件然后喂给我们的程序。 $ cat paths.txt | runhaskell heathrow.hs
The best path to take is: BCACBBC
The price is: 75


• #### 安卓逆向系列教程

wizardforcel android 20页 2018年5月3日
87

• #### 计算与推断思维

Kivy Developers From China cplusplus 19页 2018年5月3日
243

• #### pyspider中文文档

aaronhua123 python 18页 2019年5月12日
1

• #### 什么是 Markdown

frank-lam markdown 38页 2021年10月24日
0

• #### 《Spring参考文档》中文翻译 基于4.3.5 RELEASE

wangjingjing spring 98页 2018年6月24日
9

• #### Netty 4.x 用户指南

waylau netty 20页 2018年5月3日
1131