Haskel筆記 10

這是Functionally Solving Problems一章的筆記。

Reverse Polish notation calculator

polish :: (Num a, Read a) => String -> a
polish =
  head . foldl folder [] . words
  where folder (x : y : xs) "+" = (y + x) : xs
        folder (x : y : xs) "*" = (y * x) : xs
        folder (x : y : xs) "-" = (y - x) : xs
        folder accu x = read x : accu

求解逆波蘭算數表達式。

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

之前的程序可以很容易的擴展，只需要加上合適的模式匹配即可。

Heathrow to London

這是一個簡化的最短路的問題。

難點就是數據結構的表示有點不太適應，和其它語言中的「面向對象」的形式不同。

創造函數的時候，首先想想這個函數的目的，然後確定這個函數的類型，其實非常有幫助。

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

type RoadSystem = [Section]

graph :: RoadSystem
graph = [ 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)]

roadStep :: (Path, Path) -> Section -> (Path, Path)
roadStep (xs, ys) (Section a b c) =
  let costA = sum . map snd $ xs
      costB = sum . map snd $ ys
  in -- 這裏寫的時候遇到了bug!!
  (if costA + a < costB + b + c then (A, a) : xs
   else (C, c) : (B, b) : ys,
   if costB + b < costA + a + c then (B, b) : ys
   else (C, c) : (A, a) : xs)


optimalPath :: RoadSystem -> Path
optimalPath roadSystem =
  let (optimal_a, optimal_b) =
        (foldl roadStep ([], []) roadSystem)
      costA = sum . map snd $ optimal_a
      costB = sum . map snd $ optimal_b
  in
    if costA < costB then reverse optimal_a
    else reverse optimal_b


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


main = do
  contents <- getContents
  let triple = groupsOf 3 (map read . lines $ contents)
      roadSystem = map (\ [a, b, c] -> Section a b c) triple
      path = optimalPath roadSystem
      pathString = concat . map (show . fst) $ path
      pathCost = sum . map snd $ path
  putStrLn $ "The best path is: " ++ pathString
  putStrLn $ "The price is: " ++ show pathCost