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

Exercise A

Matrix Intのすべての要素に１を足す関数：

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する必要がある。