Thinking Functionally with Haskell勉強メモ: 第5章問題
Exercise A
Matrix Int
のすべての要素に1を足す関数:
addOneToAll = map (map (+1))
Matrix Int
のすべての要素の和:
sumAll = sum . sum sum :: Row Int -> Int sum [] = 0 sum x:xs = x + sum xs
二つのMatrix Int
の各要素を足す関数:
addMatrix :: Matrix Int -> Matrix Int -> Matrix Int addMatrix = zipWith (zipWith (+))
Matrix multiplication:
matMul :: Matrix Int -> Matrix Int -> Matrix Int matMul m1 m2 = map (vecMatMul tm2) m1 where tm2 = transpose m2 vecMatMul m v = map (mulVecs v) m mulVecs = sum . zipWith (*)
Exercise B
transpose :: [[a]] -> [[a]] transpose [xs] = [[x] | <- xs] transpose (xs:xss) = zipWith (:) xs (transpose xss)
transpose [xs] = [[x] | <- xs]
をtranspose []
に変えるとしたら
transpose [] = repeat []
zipWith
がxs
の要素分しか回さないので、停止ケースが無限リストでも大丈夫。
あるいは
transpose ([]:xss) = [] transpose xss = map head xss :transpose (map tail xss)
Exercise C
any p = not . all (not p)
解釈:「リストのいずれかの要素がpを満たすか」というのは「すべての要素がpを満たさない」の否定である。
any null = null . cp
解釈:空リストをふくむリストの直積は空リストである。
Exercise D
sort
関数が存在すると仮定して、同じ要素が二回リストに登場するか調べるnodups :: (Ord a) => [a] -> Bool
を定義せよ:
nodups = check . sort where check [x] = True check (x:y:ys) | x != y = False | otherwise = check y:ys
Exercise E
ダブった要素を取り除く関数nub :: (Eq a) => [a] -> [a]
を定義せよ:
nub [] = [] nul (x:xs) = x : nub (filter (/= x) xs)
要素の順番は不同でもいいとしてnub :: (Ord a) => [a] -> [a]
を定義せよ:
nub = nib . sort nib [] = [] nib (x:xs) = x : dropWhile (==x) xs
Exercise F
takeWhile
とdropWhile
を定義せよ:
takeWhile :: (Eq a) => [a] -> [a] takeWhile _ [] = [] takeWhile p (x:xs) | p x = x : takeWhile p xs | otherwise = [] dropWhile :: (Eq a) => [a] -> [a] dropWhile _ [] = [] dropWhile p (x:xs)@xs' | p x = dropWhile p xs | otherwise = xs'
文字列を単語のリストに変換するwords :: String -> [Word]
を定義せよ:
words [] = [] words x:xs | whitespace x = words (dropWhile whitespace xs) | otherwise = (x : takeWhile (not whitespace) xs) : words (dropWhile (not whitespace) xs
Exercise G
minimum :: (Ord a) -> [a] -> a
の定義:
minimum [x] = x minimum (x:xs) = smaller x (minimum xs) where smaller y z = z if y > z else y
Exercise H
数独のsolve
関数を以下のように定義できない理由を述べよ:
solve = search . choices search m | not (safe m) = [] | complete m = [extract m] | otherwise = process m where process = concat . map search . expand1 . prune
expand1
関数がすべてのマスが確定したMatrix [Digit]
を引数に受け取るとエラーを起こすので、prune
した結果はまずcomplete m
とパターンマッチするか確認して、マッチしないものだけexpand1
する必要がある。