Arantium Maestum

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

Thinking Functionally with Haskell

Thinking Functionally with Haskell勉強メモ: 第7章1 メモリ、計算量、`seq`

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

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

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

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

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 より効率のいい定義…

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

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…

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

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…

Thinking Functionally with Haskell勉強メモ: 第6章4 Maximum Segment Sum

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

Thinking Functionally with Haskell勉強メモ: 第6章3 foldlとscanl

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でいうところの…

Thinking Functionally with Haskell勉強メモ: 第6章2 foldr

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

Thinking Functionally with Haskell勉強メモ: 第6章1 数学的帰納法による証明

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

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

Thinking Functionally with Haskell勉強メモ: 第5章3 不確定なマスを再帰的に「みなし確定」させて枝刈り

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

Thinking Functionally with Haskell勉強メモ: 第5章2 確定したマスの情報をベースにフィルタ

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

Thinking Functionally with Haskell勉強メモ: 第5章1 数独ソルバー最適化以前

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

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

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

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

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を…

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

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

Thinking Functionally with Haskell勉強メモ: 第4章3 zipWithとmerge sortの実装

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

Thinking Functionally with Haskell勉強メモ: 第4章2 concat/map/filter、functorと自然変換、同一性の証明

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

Thinking Functionally with Haskell勉強メモ: 第4章1: List Comprehensionの定義

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 …

Thinking Functionally with Haskell勉強メモ: 第3章続続 integer/floatとInteger/Float

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 …

Thinking Functionally with Haskell: 第2章再読 TypeとType Classメモ

Type関連で混乱してきたので、ちょっと一旦第2章に戻ってメモをまとめていく。 "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勉強メモ: 第3章続 Type? Type Class?

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日 というわけで第3章を読み返していて腑に落ち…

Thinking Functionally with Haskell勉強メモ: 第3章

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

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 Exerci…

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

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

Thinking Functionally with Haskell勉強メモ: 第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 交換…

Thinking Functionally with Haskell勉強メモ: 第1章

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

Thinking Functionally with Haskell勉強メモ: 序文

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