Arantium Maestum

プログラミング、囲碁、読書の話題

Thinking Functionally with Haskell勉強メモ: 第2章問題

Exercise C

単語の頭文字をすべて大文字化するmodernise関数

modernise :: String -> String
modernise = unwords . map capitaliseWord . words

capitaliseWord :: String -> String
capitaliseWord "" = ""
capitaliseWord (c:cs) = (toUpper c):cs

Exercise D

Lazyだとhead . map fで問題ないがEagerだとf . headにする必要がある。

Lazyだとhead . filter pで問題ないがEagerだと

first :: (a -> Bool) -> [a] -> a
first p xs
  | null xs  = error "Empty list"
  | p x  = x
  | otherwise = first p (tail xs)
  where x = head xs

のような関数を使う必要がある。

Lazyだとhead . filter p . map fで問題ないがEagerだとf . first (p . f)(fが比較的軽い計算の場合)あるいは

firstf :: (a -> Bool) -> (b -> a) -> [b] -> a
firstf p f xs
  | null xs  = error "Empty list"
  | p x  = x
  | otherwise = firstf p f (tail xs)
  where x = f (head xs)

のような関数を使う必要がある。

Exercise E

いきなりdata declarationというフレースが出てくる。type declarationと非常に似ているようだが・・・ とにかくMaybe typeをdata declarationでEqOrdからderivingしている。

firstの再定義:

first :: (a -> Bool) -> [a] -> Maybe a
first p xs
  | null xs  = Nothing
  | p x  = x
  | otherwise = first p (tail xs)
  where x = head xs

pを満たす要素がなかった場合Nothingを返す。Lispnilなどを返すような感じか。

Exercise F

累乗の関数:

exp x n
  | n==0  = 1
  | n==1  = x
  | even n = exp (x*x) (n/2) 
  | odd n = x * exp (x*x) ((n-1)/2)

この実装だと乗算の数がO(n)ではなくO(log n)になる。

Exercise G

Date tupleから文字列として日付を表示する関数。"31st January, 2018"のように表示させたい。

showDate :: Date -> String
showDate (x, y, z) = showDay x :: " " :: showMonth y :: ", " :: showYear z

showDay :: Int -> String
showDay n = show n :: suffix n

suffix :: Int -> String
suffix n
  | (10 <= n) && (n < 20)  = "th"
  | m==1  = "st"
  | m==2  = "nd"
  | m==3  = "rd"
  | otherwise  = "th"
  where m = n `mod` 10

showMonth :: Int -> String
showMonth n = months !! n

months = ["", "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"]

showYear :: Int -> String
showYear = show

Exercise H

銀行カードなどでのチェックサムの実装。最後の2桁が最初の8桁の合計になっている誤り検出符号。

まずは8桁の数字を表す文字列から、チェックサムも加わった10桁の数字を表す文字列へ変換する関数:

type CIN = String

addSum :: CIN -> CIN
addSum cs = cs ++ checksum cs

checksum :: CIN -> CIN
checksum = show . sum . map getDigit

getDigit :: Char -> Int
getDigit c = read [c]

10桁の数字を表す文字列がチェックサムの条件に合致しているか調べる関数:

valid :: CIN -> Bool
valid cs = sumFirstEight cs == lastTwo cs

sumFirstEight :: CIN -> Int
sumFirstEight = sum . map getDigit . take 8

lastTwo :: CIN -> Int
lastTwo cs = (read cs :: Int) `mod` 100

追記: 間違えた、チェックサムが1桁になってしまう場合を想定していなかった・・・ (1桁の数字8つの合計なので必ず1~2桁に収まる)

Exercise I

IO型関数で書く、回文判定の対話式プログラム:

palindrome :: IO ()
palindrome = do {
  putStrLn "Enter a string:";
  cs <- getLine;
  putStrLn (response cs)
}

response :: String -> String
response cs
  | cleaned==reverse cleaned = "Yes!"
  | otherwise = "No!"
  where cleaned = clean cs

clean :: String -> String
clean = map toLower . filter isAlpha