Ensuing to the discussion that we had on the functionally solving problems that we had before. Where we have Reverse Polish notation calculator, we have yet another problem to solve, which is called Heathrow to London
basically the problem is that there are certains means to take from Heathrow to Londo, they start at the initial locatoin at A lane, at node 1, and then it will progress either forward at the same lane, or take a route to another lane. and we know each route has certain weight, the solution is to find the most effective way to travel from Heathrow to London in the shortest path.
There is some general guide on how to solve problems with Haskell.
- Forget Haskell for a minute and think about how we’d solve the problem by hand
- Think about how we’re going to represent our data in Haskell
- Fig Figure out how to operate on that data in Haskell so that we produce at a solution
First we will define some data to helps us tackle the problem.
data Section = Section { getA :: Int, getB :: Int, getC :: Int } deriving (Show)
type RoadSystem = [Section]
we repsent a group called section, which has three route, one is to A, another to B, and the last is to C (which means goes another route to another lane).
before this solution, we might have come up some solution which may define data structure as below.
data Node = Node Road Road | EndNode Road
data Road = Road Int Node
or even like this , if you prefer to use Maybe data.
data Node = Node Road ( Maybe Road )
data Road = Road Int Node
Since we have define the datascture to represent the path and the the RoadSystem, we might start to work out some solution, to aid us to do that ,we might define some data that enables us to track the current state and the path we will take along the way.
here are the datas.
data Label = A | B | C deriving ( Show )
type Path = [( Label , Int )]
with that, we may represent the solution by the following.
[(B ,10) ,(C ,30) ,(A ,5) ,(C ,20) ,(B ,2) ,(B ,8)]
we might has some helper function, which keeps track the optimal path to A node at section N or the optimal path to B nodes at section N... Here is the code that helps to find what it is .
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)
with that, we can find the optimal solution by the following.
<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->
optimalPath :: RoadSystem -> Path
optimalPath roadSystem =
let (bestAPath, bestBPath) = foldl roadStep ([],[]) roadSystem
in if sum (map snd bestAPath) <= sum (map snd bestBPath)
then reverse bestAPath
else reverse bestBPath
and we now need to parse the input and feed that into the optimalPath solution so that it can solve that partical problem. we create a function called groupOf, which can split the list into groups of the same size. here is the code that does it.
groupsOf :: Int -> [a] -> [[a]]
groupsOf 0 _ = undefined
groupsOf _ [] = []
groupsOf n xs = take n xs : groupsOf n (drop n xs)
and it is the main method which does the work .
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
相关推荐
Atom-haskell-ghc-mod.zip,haskell-ghc-mod atom packagehaskell ghc mod atom包,atom是一个用web技术构建的开源文本编辑器。
haskell-mode emacs haskell-mode emacs
Atom-ide-haskell-hoogle.zip,在光标下显示符号的滚动信息艾德·哈斯克尔·胡格尔,atom是一个用web技术构建的开源文本编辑器。
Haskell-Data-Analysis-Cookbook, Haskell数据分析 cookbook的附带源代码 Haskell-Data-Analysis-Cookbook这是 Haskell数据分析 cookbook的附带源代码。最新的源代码可以在GitHub上获得: ...
从1.0.0开始,haskell-ghc-mod提供haskell-completion-backend服务。 注意:在1.0.0之前,提供了ide-backend服务。 它已被废弃以支持ide-haskell的UPI。 您可以在找到描述 执照 版权所有:copyright:2015 Atom-...
Programming-in-Haskell-2nd-Edition.pdf
haskell-ghc-mod原子包 该软件包主要用作后端。 Haskell ghc-mod打开通往ghc-modi的管道,并查询类型,信息并检查错误。 安装与配置 请参考官方文档站点 服务中心API 从1.0.0版本开始,haskell-ghc-mod提供...
Get Programming with HASKELL-2018-英文版
用于 haskell-relational-record 的 MySQL 驱动程序 这个项目被合并到 。 准备 $ git clone git@github.com:khibino/haskell-relational-record.git $ git clone git@github.com:bos/hdbc-mysql.git $ git clone ...
演示医疗用例的参考DAML应用程序 -Haskell-TypeScript-下载
haskell-chart, haskell的2D 图表库 图 haskell的2D 图表库进一步的信息可以在关联的 wiki中找到。
Server Metaprogramming Ruby-Pyton-Groovy-Haskell-Erlang.pdf
A History of Haskell - Being Lazy With Class
描述函数式编程语言haskell的论文,讲述如何把haskell编译成java语言实现
Atom-ide-haskell-cabal.zip,Cabal backend provider for ide-haskellIDE Haskell Cabal套餐,atom是一个用web技术构建的开源文本编辑器。
haskell-brainfuck 解释 haskel-brainfuck 作为库分发,但它也包含一个可执行文件来运行 Brainfuck 程序。 你可以在找到 haskell-brainfuck用法图书馆 import HaskBF.Evalimport qualified Data.ByteString.Lazy as ...
haskell-lsp-client 该软件包适用于希望使其文本编辑器与兼容的文本编辑器的开发人员。 我已经开发了此软件包,并计划将其集成到。 示例客户端 该存储库中包含一个示例客户端。 此示例客户端仅运行并打开在命令行...
Atom-atom-haskell-scry.zip,De-emphasize qualified Haskell identifiers.SCRY,atom是一个用web技术构建的开源文本编辑器。
Atom-atom-haskell-pointfree.zip,atom包:将选择转换为无点或有点表示Haskell无点包,atom是一个用web技术构建的开源文本编辑器。
Haskell - The Craft of Functional Programming, 2ed (Addison-Wesley, 1999) by Tantanoid 已加书签