150102(2)

Haskell


すごいH本

第10章10.2

--道路網のデータ構造
data Section = Section { getA :: Int, getB :: Int, getC :: Int}
    deriving (Show)
type RoadSystem = [Section]

--道路網を引数として取って，経路を返す関数
data Label = A | B | C deriving (Show)
type Path = [(Label, Int)]

roadStep :: (Path, Path) -> Section -> (Path, Path)
roadStep (pathA, pathB) (Section a b c) =
    let timeA = sum (map snd pathA) -- Aまでの所要時間
        timeB = sum (map snd pathB)

        forwardTimeToA = timeA + a     --次のAまでの時間 直進
        crossTimeToA   = timeB + b + c --次のAまでの時間 道路を曲がる
        forwardTimeToB = timeB + b
        crossTimeToB   = timeA + a + c

        --AとBへの新しい経路を生成する
        newPathToA = if forwardTimeToA <= crossTimeToA
                        then (A, a) : pathA         --前から追加
                        else (C, c) : (B, b) :pathB

        newPathToB = if forwardTimeToB <= crossTimeToB
                        then (B, b) : pathB
                        else (C, c) : (A, a) :pathA

    in (newPathToA, newPathToB)
   
--最短経路を求める．
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

--ヒースロー空港からロンドンまでの道路網
heathrowToLondon :: RoadSystem
heathrowToLondon = [
                    Section 50 10 30,
                    Section  5 90 20,
                    Section 40  2 25,
                    Section 10  8  0]

Prelude> :l 10.2
[1 of 1] Compiling Main             ( 10.2.hs, interpreted )
Ok, modules loaded: Main.
*Main> optimalPath heathrowToLondon
[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]