Thinking Functionally with Haskell全１２章の折り返し地点に到達。第７章は最適化に関する話題。 メモリと計算量のトレードオフ Haskellの評価戦略は完全にナイーブではない： sqr (sqr (3+4)) = (sqr (3+4)) * (sqr (3+4)) = ((3+4) * (3+4)) * ((3+4) * …

Exercise K 第一部 takePrefix pをリストxsに適用すると、xsの頭から連続してpを満たし続ける最も長いセグメントを返す。 takePrefix :: ([a] -> Bool) -> [a] -> [a] takePrefix nondec [1, 3, 7, 6, 8, 9] = [1, 3, 7] -- リストの先頭から上がり続ける最…

Exercise J Maximum Subsequence Sumが以下のように定義されている： mss :: [Int] -> Int mss = maximum . map sum . subseqs subseqs :: [a] -> [[a]] subseqs [] = [[]] subseqs (x:xs) = xss ++ map (x:) xss where xss = subseqs xs より効率のいい定義…

Exercise F 第一部 任意の有限リストxsについて、以下の等式が成り立つことを証明せよ： foldl f e xs = foldr (flip f) e (reverse xs) 帰納法で解く。 Case [] 左辺 foldl f e [] = {foldlの定義} e Case [] 右辺 foldr (flip f) e (reverse []) = {revers…

Exercise A 自然数が以下のとおりに定義されている： mult :: Nat -> Nat -> Nat mult Zero y = Zero mult (Succ x) y = mult x y + y mult (x+y) z = mult x z + mult y zを証明せよ： case 0 左辺 mult (x+0) z = {x+0 = x} mult x z case 0 右辺 mult x z…

第６章の最後はJohn BentleyのProgramming Pearlsに出てくる「Maximum Segment Sum」を今までのような式変換と証明で解く、という演習。 Maximum Segment Sum問題 あるリスト（は整数）の中にある連続部分の和の最大値を求める関数mssを定義せよ ただし空の…

foldl関数 foldrに似たfoldl関数を定義したい。挙動は以下のとおり（@は任意の演算子）： foldr (@) e [a, b, ... y, z] = (a @ (b @ ... (y @ (z @ e)))) foldl (@) e [a, b, ... y, z] = (( ... ((e @ a) @ b) ... @ y) @ z) lisp系やpythonでいうところの…

foldr関数 sum、concat、filter、mapは似ている。 リストを受け取る 空リストが停止条件 (x:xs)が引数の場合、（mapやfilterの場合は何か関数適用した）xと、xsに対して再帰的処理した結果とを、なんらかの方法で結合する。 そして例えばsum (xs ++ ys) = su…

第６章は証明について。まずは数学的帰納法による証明を説明し、それを元にfoldl、foldrといった高階関数の性質を証明し、今後は個別の処理について証明するときの論理をfoldlとfoldrの性質を使って簡略化・普遍化する。 今回は数学的帰納法の話。 自然数 数…

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 :: Mat…

前回のsolveは「すでに確定したマスの値を使って枝刈り」の後に「残った各マスの取り得る値の全探索」という解決方法だった。 これでも相当な効率化が図られているが、「残った各マスの取り得る値の全探索」のほうにまだまだ改善の余地が残されている。例え…

非常に非効率だが問題文に誠実に宣言的に書いているので正しさが（ほぼ）自明なプログラムに対して、ここから成り立つと証明できる法則を使って、結果が同一なことを担保しつつ効率が上がるような変換を行っていく。 前回の数独ソルバーは981-kものGridを一…

第５章は数独ソルバーの実装を通してHaskell/関数型プログラムの書き方（の一つ）を紹介するというもの。 まずは問題をできるだけ宣言的に解くコードを記述して、その後最適化していく。 この記事は第一段階の非常に非効率な宣言的コードの説明まで。 データ…

Exercise J 以下のものの意味を考え、間違っているものを見つけよ： map f . take n = take n . map f リストの先頭からからn個の要素を取ってfを適用するのと、リストのすべての要素にfを適用してできた新しいリストの先頭からn個の要素を取るのは等しい。…

Exercise F data List a = Nil | Snoc (List a) a というリストの別定義があったとする。 headとlast関数を定義せよ： last :: List a -> a last (Snoc xs x) = x head :: List a -> a head (Snoc Nil x) = x head (Snoc xs x) = head xs toListとfromListを…

Exercise A null :: [a] -> Bool null [] = True null _ = False という定義を null = (==[]) と変えても大丈夫か？という問題。 実際使ってみると大丈夫そうなのだが： Prelude> null = (==[]) Prelude> null [] True Prelude> null [1] False Prelude> nul…

zipWith ふたつのリストから一要素ずつ取って関数を適用するzipWith関数： zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys zipWith f _ _ = [] この定義はちょっと面白い。再帰を書く場合、いつも停止条…

リストに対する処理の性質・法則、Functorに対するの一般化、性質の証明法についてメモ： まずはconcat、map、filterの定義： concat :: [[a]] -> [a] concat [] = [] concat (xs:xss) = xs ++ concat xss map :: (a -> b) -> [a] -> [b] map _ [] = [] map …

Haskellでは Prelude> [1..5] [1,2,3,4,5] Prelude> [(+1) x | x <- [1..5]] [2,3,4,5,6] のように[a..b]と[f x | x <- xs]といった簡単にリストを作成できる記法がサポートされている。 後者は特に便利で Prelude> [x*y | x <- [1..10], x `mod` 2 == 0, y …

3.149 :: Fractional a => a This type and the earlier type Num a => a for 42 explains why we can form a legitimate expression such as 42 + 3.149, adding an integer to a floating-point number. Both types are members of the Num class and all …

Type関連で混乱してきたので、ちょっと一旦第２章に戻ってメモをまとめていく。 "In Haskell every well-formed expression has, by definition, a well-formed type. Each well-formed expression has, by definition, a value." まず、式には型と値がある…

Thinking Functionally with Haskellに”all numbers are instances of the type class Num”とあるが、”all number types are instances of the type class Num”の間違い？— zehnpaard (@zehnpaard) 2018年3月8日 というわけで第３章を読み返していて腑に落ち…

数について。 Int, Integer, Float, Complexなど多くの数の型がある。すべてtype class Numに属している。 NumはEqとShowのsubclass。Ordは？と一瞬思ったが複素数は順序が定義されていない。 Haskellでユーザが0以上の整数として自然数を定義する場合： dat…

Exercise C 単語の頭文字をすべて大文字化するmodernise関数 modernise :: String -> String modernise = unwords . map capitaliseWord . words capitaliseWord :: String -> String capitaliseWord "" = "" capitaliseWord (c:cs) = (toUpper c):cs Exerci…

章のタイトルは「式、型、値」。いかにも静的型付き関数型プログラミングっぽい。 面白かった・気になった点： (+1)などのSectionが関数として使えるのは便利そう。(-1)が使えないという点で萎えるけど（関数ではなく単なる負の整数として扱われる） ラムダ…

Exercise A 右辺と左辺の等価性の「証明」 sum . map double = double .sum 分配法則 (distributative property)でc*a + c*b = c * (a + b) sum . map sum = sum . concat 結合法則 (associative property)で(a+b)+(c+d) = (a+b+c+d) sum . sort = sort 交換…

第１章は「関数型言語とは？」という問いへの著者なりの答えから始まる。 Richard Birdの「関数型プログラミング」定義は： 関数とその適用を重視するプログラミング（命令とその実行ではなくて） 簡明な数学的記法で問題を記述することができる 数学的な裏…

2月から少しずつRichard BirdのThinking Functionally with Haskellを読み進めている。 こちらも章ごとにメモを書いていきたい&章末の問題を解いていきたい。ちなみに章末の問題はすべて本にも模範解答が載っている。とりあえず今回は序文についてのメモ。 "…