2018-03-19

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

Haskell Thinking Functionally with Haskell

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

前回の数独ソルバーは9^81-kものGridを一つ一つ作成してはルールに従ってフィルタしていくものだった。Grid作成過程でどうにかして作る数を減らさなければ、実際的な時間内で計算が終わらない。

今回はもっとも簡単なアイディアである「確定したマスの行、列、箱の他のマスが、確定した値を含まないようフィルタする」を実装し、それがもとのプログラムと同一の結果を返すことを証明する。

prune :: Matrix [Digit] -> Matrix [Digit]
filter valid . expand . choices = filter valid . expand . prune . choices

となるようなprune関数を求めたい。

Matrix Digit型の問題文をchoicesでMatrix [Digit]型の「各マスに入る可能性のあるDigitのリストのMatrix」に変換したわけだが、その「入る可能性のあるDigit」をexpandする前に減らしておく、という戦略である。

`pruneRow`関数

まずRowに対してフィルタするpruneRowを考えてみる。

pruneRow :: Row [Digit] -> Row [Digit]
pruneRow row = map (remove fixed) row
               where fixed = [d | [d] <- row]

この定義、とくにfixedの部分が面白い。[d | [d] <- row]でrowの中身に対してパターンマッチを行っていて、要素１のリストだけをフィルタしてその要素を摘出している。too cleverな気もするけど・・・

remove :: [Digit] -> [Digit]
remove _ [x] = [x]
remove ds xs = filter (`notElem` ds) xs

[x]な（つまり確定している）マス以外は、確定した値を含まないようフィルタする。remove _ [x] = [x]がないと確定したマスが空になってしまう。

とここで

The function pruneRow satisfies the equation

filter nodups . cp = filter nodups . cp . pruneRow

とさらっと書いてあって、「自明か？自明なのか？」と数学書でおなじみのアレになる。いや、やっていることを考えれば成り立つとは思うんだけど証明しなくていいのか？

これから使う等式

さて、ここでいくつか他にも重要な等式を列挙しておこう。

`rows, cols, boxs`は対合

rows . rows = id
cols . cols = id
boxs . boxs = id

boxsケースの証明は意外と簡単。colsつまりtransposeは自明っぽいけど（transposeしてtransposeしたらもとに戻る）証明はTFwHのここまでの説明だけでは無理らしい。

group . ungroup = id --すでにgroupされているMatrixに対して
ungroup . group = id

まあ自明。これを使ってboxsの対合性を証明できる。

`expand`と`rows...`の関係

map rows . expand = expand . rows
map cols . expand = expand . cols
map boxs . expand = expand . boxs

boxの定義上9x9のMatrixが引数な場合に限り、だと思う（本ではN^2xN²となっていたがその場合boxの定義も変える必要があるはず）

`cp`の特性

map (map f) . cp = cp . map (map f)
filter (all p) . cp = cp . map (filter p)

最初の式は自然変換。cpは要素に対してなにも働きかけないので、fを各要素に適用するのがcpの前か後かで結果は変わらない。

二番目の式はちょっとややこしい。

左辺は直積をとってできた[[a]]から、[a]の全要素がpを満たしているリストのみを摘出している
右辺は直積をとる前にそもそも[a]からpを満たさない要素を抜いている

その結果が等しいということは、直積する前にフィルタしてしまって効率化を図れるということ。

対合と`filter/map`

-- f . f = idの場合
filter (p . f) = map f . filter p . map f
filter (p . f) . map f = map f . filter p

まあ自明。第４章ですべてのp, fにおいて

filter p . map f = map f . filter (p . f)

を証明したのを使えば楽に証明できる。

`pruneRow`の等価性の証明

以上の等式を使って、filter valid . expand . completions = filter valid . expand . prune . completionsが成り立つようなpruneをpruneRowを使って書けることを証明する。

まずfilter validを、validの定義から以下のように書き直す：

filter valid = filter (all nodups . rows) . filter (all nodups . cols) . filter (all nodups . boxs)

この変換も自明として扱われている。

p x = p1 x && p2 x
filter p = filter p1 . filter p2 = filter p2 . filter p1

が成り立つのは自明だろうか？直感的にはわかるが・・・

さて、これで

filter valid . expand = filter (all nodups . rows) . filter (all nodups . cols) . filter (all nodups . boxs) . expand

になるので

filter (all nodups . boxs) . expand
filter (all nodups . cols) . expand
filter (all nodups . rows) . expand

を一つ一つみていく（というのは嘘で最初のやつを解いたらまったく同じロジックであとの二つも解ける）。

filter (all nodups . boxs) . expand

= {filter (p . f) = map f . filter p . map f   -- f . f = id}
map boxs . filter (all nodups) . map boxs . expand

= {map boxs . expand = expand . boxs}
map boxs . filter (all nodups) . expand . boxs

= {expand = cp . map cp}
map boxs . filter (all nodups) . cp . map cp . boxs

= {filter (all p) . cp = cp . map (filter p)}
map boxs . cp . map (filter nodups) . map cp . boxs

= {functor law of map}
map boxs . cp . map (filter nodups . cp) . boxs

= {filter nodups . cp = filter nodups . cp . pruneRow}
map boxs . cp . map (filter nodups . cp . pruneRow) . boxs

ここまででpruneRowを等価な変換で登場させることに成功した。

あとは左側にfilter (all nodups . boxs) . expandが戻ってくるように逆変換していく：

map boxs . cp . map (filter nodups . cp . pruneRow) . boxs

= {functor law of map}
map boxs . cp . map (filter nodups) . map cp . map pruneRow . boxs

= {filter (all f) . cp = cp . map (filter f)}
map boxs . filter (all nodups) . cp . map cp . map pruneRow . boxs

= {expand = cp . map cp}
map boxs . filter (all nodups) . expand . map pruneRow . boxs

= {filter (p . f) . map f = map f . filter p  -- f . f = id}
filter (all nodups . boxs) . map boxs . expand . map pruneRow . boxs

= {map boxs . expand = expand . boxs}
filter (all nodups . boxs) . expand . boxs . map pruneRow . boxs

これで

filter (all nodups . boxs) . expand = filter (all nodups . boxs) . expand . boxs . map pruneRow . boxs

という等式が成り立つことが証明できた。まったく同じ理屈で

filter (all nodups . rows) . expand = filter (all nodups . rows) . expand . rows . map pruneRow . rows
filter (all nodups . cols) . expand = filter (all nodups . cols) . expand . cols . map pruneRow . cols

も成り立つ。

boxs . map pruneRow . boxsは、Matrixをまず3x3の区切りの集まりに変換し、各集まりに対して確定したマスの数を取り除くpruneRowを適用し、またboxを適用する。boxを適用したMatrixにboxを再度適用すると形はもとに戻るので、最終的には「3x3の区切りをただしくpruneしただけ」という結果が残る。

なのでpruneBy f = f . map pruneRow . fを定義して

pruneBy boxsはMatrixの形を変えずにboxs単位で確定値をフィルタ
pruneBy colsはMatrixの形を変えずにcols単位で確定値をフィルタ
pruneBy rowsはMatrixの形を変えずにrows単位で確定値をフィルタ

とみなすことができる。

filter (all nodups . boxs) . expand = filter (all nodups . boxs) . expand . pruneBy boxs
filter (all nodups . rows) . expand = filter (all nodups . rows) . expand . pruneBy rows
filter (all nodups . cols) . expand = filter (all nodups . cols) . expand . pruneBy cols

とより簡単に表現できるようになる。

話をfilter valid . expandに戻すと：

filter valid . expand 

= {filter validの書き換え}
filter (all nodups . rows) . filter (all nodups . cols) . filter (all nodups . boxs) . expand

= {filter (all nodups . f) . expand = filter (all nodups . f) . expand . pruneBy f -- f in (rows, cols, boxs)}
filter (all nodups . rows) . filter (all nodups . cols) . filter (all nodups . boxs) . expand . pruneBy boxs

= {filter A . filter B = filter B . filter A}
filter (all nodups . rows) . filter (all nodups . boxs) . filter (all nodups . cols) . expand . pruneBy boxs

= {filter (all nodups . f) . expand = filter (all nodups . f) . expand . pruneBy f -- f in (rows, cols, boxs)}
filter (all nodups . rows) . filter (all nodups . boxs) . filter (all nodups . cols) . expand . pruneBy cols . pruneBy boxs

= {filter A . filter B = filter B . filter A}
filter (all nodups . cols) . filter (all nodups . boxs) . filter (all nodups . rows) . expand . pruneBy cols . pruneBy boxs

= {filter (all nodups . f) . expand = filter (all nodups . f) . expand . pruneBy f -- f in (rows, cols, boxs)}
filter (all nodups . cols) . filter (all nodups . boxs) . filter (all nodups . rows) . expand . pruneBy rows . pruneBy cols . pruneBy boxs

= {filter validの書き換え}
filter valid . expand . pruneBy rows . pruneBy cols . pruneBy boxs

と、filter valid . expandの後ろにrows/cols/boxsすべてのpruneBy fをつけても等価であることが証明できるので：

prune = pruneBy rows . pruneBy cols . pruneBy boxs

とpruneをpruneByを使って定義すれば：

filter valid . expand = filter valid . expand . prune
filter valid . expand . completions = filter valid . expand . prune . completions

を満たす。さらには：

filter valid . expand . completions = filter valid . expand . prune . prune . ... . prune . completions

とpruneを任意の回数入れても等価。pruneすることで確定したマスが出てきた場合、もう一度pruneすることでさらに絞り込みが可能になる場合も多い。

結果が変わらなくなるまでfを適用し続ける、という関数manyを

many :: (Eq a) => (a -> a) -> a -> a
many f x = if x == y then x else many y x
           where y = f x

と定義する。これを使えばsolveの定義を：

solve = filter . valid . expand . many prune . choices

と表現でき、これは

solve = filter . valid . expand . choices

と等価であることを証明できた。（manyの等価性担保は本当に自明か？）

まだ最適化の余地は大きい。次回はその話。

2018-03-18

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

Haskell Thinking Functionally with Haskell

第５章は数独ソルバーの実装を通してHaskell/関数型プログラムの書き方（の一つ）を紹介するというもの。

まずは問題をできるだけ宣言的に解くコードを記述して、その後最適化していく。

この記事は第一段階の非常に非効率な宣言的コードの説明まで。

データ型の定義

まずは問題の入力と出力を表すデータ構造を型として定義する：

data Matrix a = [Row a]
data Row a = [a]

type Grid = Matrix Digit
type Digit = Char

digits :: [Digit]
digits = ['1' .. '9']

blank :: Digit -> Bool
blank = (=='0')

Matrix型は[[a]]のalias。一枚の数独問題（回答前・後を問わず）はGrid型で表現する。GridはMatrix Digitのaliasであり、DigitはCharのalias。記入されていないマスは0で表される。

`solve`関数

solve :: Grid -> [Grid]
solve = filter valid . completions

valid :: Grid -> Bool
completions :: Grid -> [Grid]

数独を解く関数solveの定義。

問題をGridとして受け取り、正解回答となるGridすべてのリストを返す。completionsとvalidという二つの関数を組み合わせて作る。

まずはcompletions。問題Gridを受け取り、、空のマスに1から9までを当てはめていくことで問題を（間違っていてもいいので）埋めきったすべての（非常に多くの）パターンのGridのリストを返す。

validは埋めきったGridが数独のルールに従っているかを判定する。validでフィルタすることで、すべてのパターンから正解例のみを取り出す。

`completions`

定義は：

completions = expand . choices

構成要素である二つの関数の型は：

choices :: Grid -> Matrix [Digits]
expand :: Matrix [Digits] -> [Grid]

あるいはこちらのほうがわかりやすいかもしれない：

choices :: Matrix Digits -> Matrix [Digits]
expand :: Matrix [Digits] -> [Matrix Digits]

choicesはDigitsのMatrixである問題文から、確定しているマスは要素数１、空のマスは要素数９（1..9)のDigitsのリストのMatrixに変換する。

expandはその「各マスが取り得るDigit値を列挙したリストのMatrix」を引数にとり、「各マスの取り得る値の直積集合である『DigitのMatrixのリスト』」を返す。

`choices`

choices = map (map choice)
choice d
  | blank d    = digits
  | otherwise = [d]

個別のマスに対して、'0'以外ならその値のみ入っているリスト、'0'なら['1'..'9']を返すchoice関数を適用する。

例えば引数が

[['1', '2', '3', '4', '5', '6', '7', '0', '0'], ..., ......]

だった場合、以下を返す：

[[['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['1', '2', '3', '4', '5', '6', '7', '8', '9']], ..., ......]

`expand`

expandを定義するためにはまずcp関数を定義する。cpとは直積集合Cartesian Productの略。定義は：

cp :: [[a]] -> [[a]]
cp [] = [[]]
cp (xs:xss) = [x:ys | x <- xs, ys <- yss]
              where yss = cp xss

例えばcpの引数が

[['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['1', '2', '3', '4', '5', '6', '7', '8', '9']]

だった場合、以下を返す：

[['1', '2', '3', '4', '5', '6', '7', '1', '1'],
 ['1', '2', '3', '4', '5', '6', '7', '1', '2'],
 ['1', '2', '3', '4', '5', '6', '7', '1', '3'],
 ['1', '2', '3', '4', '5', '6', '7', '1', '4'],
 ...
 ['1', '2', '3', '4', '5', '6', '7', '9', '8'],
 ['1', '2', '3', '4', '5', '6', '7', '9', '9'],
 ]

map cpで一つ一つの行を「その行が取り得るすべての「９つのDigitのリスト」のリスト」に変換する。

それをさらにcpすることで、各行が取り得るすべての値の直積に変換する。それがマスを埋めたGridのパターンすべてを網羅したリストだ。

なのでexpandの定義は：

expand = cp . map cp

なのでcompletionsを展開していくと：

completions = expand . choices
              = cp . map cp . choices
              = cp . map cp . map (map choice)

となる。

`valid`

数独のルールに従ってvalidの定義は以下の通りになる：

valid g = all nodups (rows g) &&
          all nodups (cols g) &&
          all nodups (boxs g)

nodupsはno duplicatesの略。各行(rows)、各列(cols)、各3x3の区切り(boxs)にダブった数字がないことが正解の条件である。

`all`

all関数はリストのすべてがpを満たしているかチェックする：

all :: (a -> Bool) -> [a] -> Bool
all p = and . map p

`nodups`

あるリストに同じ要素が二回出てくるかチェックする関数。

nodups :: (Eq a) => [a] -> Bool
nodups [] = True
nodups (x:xs) = all (/=x) xs && nodups xs

一見O(n²)だがn=9なので気にしない。

`rows`

rowsはあるGridの行のリストを返す関数。

本には型はrows :: Matrix a -> Matrix aとあったが、個人的には意味的にrows :: Matrix a -> [[a]]ではないか？と思っている。

たまたまMatrix aは[Row a]なのでrowの定義は：

row = id

`cols`

colsはGridの列のリストを返す関数。

これと次のboxsはどう考えてもMatrix a -> Matrix aというよりMatrix a -> [[a]]じゃないか？

cols = transpose

transpose :: [[a]] -> [[a]]
transpose [xs] = [ [x] | x <- xs]
transpose (xs:xss) = zipWith (:) xs (transpose xss)

transposeは私が定義した。本の中ではtranspose関数はなく、直接colsをこの定義にしていた。ただ、colsという名前で書くのは（とくに次のboxsでも使う手前）不適当な気がしたのでいったんtransposeという名前で定義してcolsをaliasとした。

しかしこのtransposeの定義、一番最後のリストを一要素ずつのリストのリストにする、というのを再帰の終了条件にして、そのリストにzipWithで前のリストの要素を付け加えていく。理屈はわかるのだが自前で考えろと言われて書ける気が全くしない・・・

`boxs`

boxsは3マスx3マスの各区切りの中の数リストが９つ入ったリストを返す。

boxs :: Matrix a -> [[a]]
boxs = map ungroup . ungroup . map transpose . group . map group

group :: [a] -> [[a]]
group [] = []
group xs = take 3 xs : group drop 3 xs

ungroup :: [[a]] -> [a]
ungroup = concat

リストを「3つの要素ごとのリスト」のリストに変換する関数がgroup、それを元のリストに戻すのがungroup（実際の処理はただのconcat）。

挙動を理解するのがけっこうややこしい関数の組み合わせなので、4x4のMatrixを2x2の区切り内の要素のリストに変換する様を書いてみる。

まず入力：

[[a1, a2, a3, a4],
 [b1, b2, b3, b4],
 [c1, c2, c3, c4],
 [d1, d2, d3, d4]]

map group適用：

[[[a1, a2], [a3, a4]],
 [[b1, b2], [b3, b4]],
 [[c1, c2], [c3, c4]],
 [[d1, d2], [d3, d4]]]

中の４つの要素のリストが、２つの要素のリスト二つのリストに変換されている。

次はgroup適用：

[[[[a1, a2], [a3, a4]],
  [[b1, b2], [b3, b4]]],
 [[[c1, c2], [c3, c4]],
  [[d1, d2], [d3, d4]]]]

4x2x2要素のリストのリストのリストだったのが、2x2x2x2のリストx4になっている。

map transpose：

[[[[a1, a2], [b1, b2]],
  [[a3, a4], [b3, b4]]],
 [[[c1, c2], [d1, d2]],
  [[c3, c4], [d3, d4]]]]

[a3, a4]と[b1, b2]、[c3, c4]と[d1, d2]の位置が入れ替わった。

ungroup適用：

[[[a1, a2], [b1, b2]],
 [[a3, a4], [b3, b4]],
 [[c1, c2], [d1, d2]],
 [[c3, c4], [d3, d4]]]

2x2x2x2から4x2x2に。

map ungroup適用：

[[a1, a2, b1, b2],
 [a3, a4, b3, b4],
 [c1, c2, d1, d2],
 [c3, c4, d3, d4]]

4x4のリストのリストに戻っているが、最初のリストはa1, a2, b1, b2と左上にあった数字、次のリストは右上、次は左下、最後は右下、と2x2に分割した各区切りの数字のリスト４つになっていることがわかる。

これを3x3の区切りで9x9のGridに適用したのが上記のboxs。

結論

rowsもcolsもboxsもすべてのリストがvalidならそのGridは数独のルール上正しく記入されていることになる。なのでcompletionsの戻り値をvalidでフィルタすれば、正しい回答のリストが得られる。

が、completionsが返すリストは遅延評価とはいえ9^81-k （kは数字が知られているマスの数）もの結果を返し、それを一つ一つフィルタしていかなければいけない。現実的に不可能である。

なので次回はこの非常に効率の悪いコードに対しどのような等価な変換を加えていくことで最適化ができるか、というポイントを探っていく。

2018-03-18

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

Haskell Thinking Functionally with Haskell

Exercise J

以下のものの意味を考え、間違っているものを見つけよ：

map f . take n = take n . map f

リストの先頭からからn個の要素を取ってfを適用するのと、リストのすべての要素にfを適用してできた新しいリストの先頭からn個の要素を取るのは等しい。正しい。

map f . reverse = reverse . map f

リストを逆順にしてすべての要素にfを適用するのと、リストのすべての要素にfを適用してから逆順にするのは等しい。正しい。

map f . sort = sort . map f

リストをソートしてからすべての要素にfを適用するのと、リストの要素すべてにfを適用してからソートするのは等しい。間違い。a < bだからf a < f bとは限らないため。

map f . filter p = map fist . filter snd . map (fork (f, p))
fork :: (a -> b, a -> c) -> a -> (b, c)
fork (f, g) x = (f x, g x)

forkは二つの関数のtupleとひとつのナニカ（これって何て呼ぶべきなんだろう？オブジェクト？要素？）を引数にとり、そのナニカに二つの関数適用した結果をtupleとして返す。

あるリストを関数pでフィルタして、残った要素すべてにfを適用するのは、そのリストの各要素にfが適用された結果とpが適用された結果のtupleのリストをtupleの第二要素でフィルタして第一要素だけ取り出すのと等しい。正しい。

filter (p . g) = map (invertg) . filter p . map g
invertg . g = id

あるリストを、各要素にgとpをその順に適用した結果でフィルタするのは、そのリストの全要素にgを適用しpでフィルタしてからgの逆関数を残った要素すべてに適用するのと等しい。正しい。

reverse . concat = concat . reverse . map reverse

あるリストを統合してから逆順にするのは、そのリストの要素の中身を逆順にしてからリスト自体を逆順にして統合するのに等しい。正しい。

filter p . concat = concat . map (filter p)

リストを統合してからpでフィルタするのは、リストの中のリスト一つ一つをpでフィルタしてからすべて統合するのに等しい。正しい。

Exercise K

zipとcrossが以下のように定義されているとする：

unzip = fork (map fst, map snd)
cross (f, g) = fork (f . fst, g . snd)

unzipとcrossの型は？：

unzip :: [(a, b)] -> ([a], [b])
cross :: (a->b, c->d) -> (a, c) -> (b, d)

unzip、cross、forkなどに関して以下の等式が成り立つ：

cross (f, g) . fork (h, k) = fork (f . h, g . k)
fork (f, g) . h = fork (f . h, g . h)
fst . cross (f, g) = f . fst
snd . cross (f, g) = g . snd

上記の等式とfunctor law of mapsを使って

cross (map f, map g) . unzip = unzip . map (cross (f, g))

が成り立つことを証明せよ：

cross (map f, map g) . unzip
= {unzipの定義}
cross (map f, map g) . fork (map fst, map snd)
= {等式１：cross().fork()=fork()}
fork (map f . map fst, map g . map snd)
= {functor law of map}
fork (map (f . fst), map (g . snd))
= {等式３：fst . cross(f, g) = f . fst}
fork (map (fst . cross (f, g)), map (g . snd))
= {等式４：snd . cross(f, g) = g . snd}
fork (map (fst . cross (f, g)), map (snd . cross (f, g)))
= {functor law of map}
fork (map fst . map (cross (f, g)), map snd . map (cross (f, g)))
= {等式２：fork (f, g) . h = fork (f . h, g . h)}
fork (map fst, map snd) . map (cross (f, g))
= {unzipの定義}
unzip . map (cross (f, g))

Exercise L

cross (f, g) . cross (h, k) = cross (f . h, g . k)

を証明せよ：

cross (f, g) . cross (h, k)
= {crossの定義}
cross (f, g) . fork (h . fst, k . snd)
= {等式１：cross() . fork() = fork()}
fork (f . h . fst, g . k . snd)
= {crossの定義}
cross (f . h, g . k)

cross (id, id) = idの理由は？：

cross (id, id) = fork (id . fst, id . snd) = fork (fst, snd)=id

最後の一歩はforkの定義から自明な気がするが証明できていない・・・

Functorが一つの関数をとって要素に適用するfmapが定義されているデータ構造の型クラスだとしたら、Bifunctorは二つの関数をとって要素に適用するbimapが定義されている型クラスである。crossはbimapに非常に近いが、bimapの型は：

bimap :: (a -> c) -> (b -> d) -> bif a b -> bif c d

である。(bifはBifunctorインスタンスの型）

crossをbimapを使って定義するとcross (x, y) = bimap x yになる。

data Either a b = Left a | Right b

という型をBifunctorのインスタンスにしたい場合の定義は：

instance Bifunctor Either where
  bimap (f, g) Left a = f a
  bimap (f, g) Right b = g b

2018-03-17

Effective C++勉強メモ: Item 23 Non-Member Non-Friend関数をNamespaceで管理しよう

C++ Effective C++

前回の項目でカプセル化の重要性について書いてあったが、そのカプセル化を最大に実現するためには、内部実装に触れることのできる面積を最小化する必要がある。

つまり、メンバ関数、フレンド関数といった「クラス内部のデータメンバに直接アクセスできる関数」をなるべく減らすのがポイントになる。クラスに最小限のAPIを定義し、そのAPIを使ったNon-Member Non-Friend関数を使ってオブジェクトとやりとりする。

そのような関数を（たとえばJavaからきたプログラマは）別のユーティリティクラスのメンバ関数にすることも多いが、C++で自然な書き方はnamespaceを使って関連性のあるクラスと関数をまとめるやり方である。

例としては：

namespace WebBrowserStuff
{
class WebBrowser { ... };
void clearBrowser(WebBrowser& wb);
}

WebBrowserStuff::WebBrowser wb;
WebBrowserStuff::clearBrowser(wb);

と、本に書いてあることをまとめたが、個人的には少し微妙な気がする。APIに対する期待としてclearBrowserはWebBrowserオブジェクトのclearメンバ関数であってほしい。

直接内部データにアクセスしなくても実装できるならそのようにするべき（実装の問題）
そのオブジェクトのAPIはそのオブジェクトが保持するべき（プログラムの意味の問題）

というコンセプトがぶつかっている。この齟齬は、クラスという言語機構がデータアクセスと外部APIをかなり粒度の大きいレベルでしか扱っていないのが原因だろうか？

ここにすごく違和感を感じるのは、私がPythonという「データアクセスを制限する」側面を完全に放棄している言語に慣れ親しんでいるからかもしれない。

2018-03-17

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

Haskell Thinking Functionally with Haskell

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を実装せよ。例えばfromListは

[1, 2, 3] == fromList (Snoc (Snoc (Snoc Nil 1) 2) 3)

となる：

toList :: [a] -> List a
toList = toReverseList . reverse
  where toReverseList [] = Nil
        toReverseList (x:xs) = Snoc (toReverseList xs) x

fromList :: List a -> [a]
fromList = reverse . fromReverseList
  where fromReverseList Nil = []
        fromReverseList (Snoc xl x) = x : fromReverseList xl

Exercise G

length :: [a] -> Int
length [] = 0
length (x:xs) = 1 + length xs

というリストの長さを計算する関数のメモリ量は

length [1, 2, 3] = 1 + (1 + (1 + 0))

のようにO(n)である。それは定義が

length :: [a] -> Int
length xs = loop (0, xs)
  where loop (n, []) = n
        loop (n, (x:xs)) = loop (n+1, xs)

のようにかわっても同じ。何故かというと遅延評価で

length [1, 2, 3] = loop ((((0 + 1) + 1) + 1), [])

となるまで計算されないので、加算処理がO(n)でメモリに積みあがっていく。先行評価ならloopを使う方法だとO(1)になる。

Exercise H

takeとdropの再帰的な定義：

take :: Int -> [a] -> [a]
take _ [] = []
take 0 _ = []
take n (x:xs) = x : take (n-1) xs

drop :: Int -> [a] -> [a]
drop _ [] = []
drop 0 xs = xs
drop n (x:xs) = drop (n-1) xs

この定義だとtake undefined []は[]だがtake 0 undefinedはundefinedになる。なぜならtake _ []とマッチするか確認するためにtake 0 undefinedの二番目の引数を評価しないといけないからだ。

そう考えると、take _ [] = []とtake 0 _ = []の順番を入れ替えることによってtake undefined []とtake 0 undefinedのどちらかを[]にすることはできるが、かならずどちらかはundefinedになる。

splitAt :: Int -> [a] -> ([a], [a])の定義：

splitAt n xs = move n ([] xs)
  where move _ xst@(ys, []) = xst
        move 0 xst = xst
        move n (ys, (z:zs)) = move (n-1) (ys++[z], zs)

ただys++[z]って遅そう・・・

Exercise I

map (f .g) xs = map f (map g xs)

という等式に関して：

任意のリストxs (finite, partial, infinite)、任意の（型のあった）関数fとgにおいて成り立つ。なのでmap (f . g) = map f . map gと表すこともできる。
mapと.の定義から証明されなければいけない
右辺から左辺へと変換するのは最適化
遅延評価でmapがすべての要素に一気に適用されないとはいえ、二つの遅延リストが存在するより一つだけのほうが効率がいい

といった点が挙げられる。

2018-03-17

ClojureとQuilでClifford Attractor

Clojure Quil

昔のProcessing Advent Calendarをいろいろ漁っていたらこんな記事があった：

qiita.com

上記の記事の冒頭の絵は

${ (x_{n+1}, y_{n+1}) = (\sin(a y_n) + c \cos(a x_n), \sin(b x_n) + d \cos(b y_n) ) }$

で表されるアトラクターである。

以下の参考サイトにはもっと例が載っている。

Clifford Attractors

まさにClojureのiterate関数の使いどころという趣があるので、Quilで書いて並べてみた：

Quil -L7l8xEpZC6Ma1Qckc63

コードを簡単に説明する。

a, b, c, dのパラメータを受け取り、新たに無名関数を返す高階関数clifford。無名関数lはアトラクターの計算式を表している：

(defn clifford [[a b c d]]
  (fn [[x y]]
    [(+ (-> y (* a) q/sin)
        (-> x (* a) q/cos (* c)))
     (+ (-> x (* b) q/sin)
        (-> y (* b) q/cos (* d)))]))

その高階関数に９つの違うパラメータを渡して、９つの違うアトラクター関数を作成する：

(def clifs 
  (vec 
    (map clifford 
         [[-1.4 1.6 1.0 0.7]
         [1.6 -0.6 -1.2 1.6]
         [1.7 1.7 0.6 1.2]
         [1.5 -1.8 1.6 0.9]
         [-1.7 1.3 -0.1 -1.2]
         [-1.7 1.8 -1.9 -0.4]
         [-1.8 -2.0 -0.5 -0.9]
         [-1.4 -1.6 -1.0 -0.7]
         [1.8 -1.5 0.4 0.9]])))

各フレームでのアップデートでは、最後に描画した点の座標をアトラクター関数に渡し、その結果をまた同じアトラクター関数に渡し、と200回繰り返して出来た200個の座標をvectorとして保持する、というのを各アトラクターごとに（つまり９回）行う。

update-stateで９つの関数と9つのvectorをupdate-seriesにmapし、update-series内でアトラクターごとに新しい座標２００点を算出する：

(defn update-series [f vs]
  (->> vs last (iterate f) (take 200) vec))

(defn update-state [state]
  (vec (map update-series clifs state)))

ここでiterateを使っている。(iterate f x)は(f x) (f (f x)) (f (f (f x))) ...の無限リストなのでClifford Attractorを表現するには完璧。

あとは９つの座標リストを少しずつずらして描画するだけ：

(defn draw-state [state]
  (doseq [[i vs] (map-indexed vector state)]
    (q/with-translation [(-> i (mod 3) (* 200) (+ 150))
                         (-> i (/ 3) int (* 200) (+ 150))]
      (doseq [[x y] vs]
        (q/point (* 40 x)
                 (* 40 y))))))

けっこう数字をいじっても面白いパターンが現れやすいので楽しい。

2018-03-16

Effective C++勉強メモ: Item 22 データメンバは黙って`private`

C++ Effective C++

クラス内のデータはpublicでもprotectedでもなくprivateにしよう。という話。

ポイントは三つ

構文の統一
データアクセスレベルのコントロール
カプセル化

構文の統一

オブジェクトのAPIはすべて関数（か演算子）になり、a.somethingだったかa.something()だったか悩む必要がなくなる。

データアクセスレベルのコントロール

getter/setter関数を実装するかどうかで

read-write
read-only
write-only
hidden

の四つのアクセスレベルを簡単にコントロールできる。

カプセル化

データメンバに直接アクセスされる場合、内部での実装変更はAPI変更になり、その影響の範囲は限定できない。これはprotectedでも同じで、このクラスを継承するすべてのクラスを影響し得る以上、原則的には変更の影響範囲を限定することができない。

逆に外部、継承クラスに提供するものが関数のみであれば、getterだったものが実は別のデータをもとに計算するようになった、などの実装変更をAPI変更なしで行える。

データは黙ってprivate。

Arantium Maestum

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

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

`pruneRow`関数

これから使う等式

`rows, cols, boxs`は対合

`expand`と`rows...`の関係

`cp`の特性

対合と`filter/map`

`pruneRow`の等価性の証明

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

データ型の定義

`solve`関数

`completions`

`choices`

`expand`

`valid`

`all`

`nodups`

`rows`

`cols`

`boxs`

結論

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

Exercise J

Exercise K

Exercise L

Effective C++勉強メモ: Item 23 Non-Member Non-Friend関数をNamespaceで管理しよう

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

Exercise F

Exercise G

Exercise H

Exercise I

ClojureとQuilでClifford Attractor

Effective C++勉強メモ: Item 22 データメンバは黙って`private`

構文の統一

データアクセスレベルのコントロール

カプセル化

pruneRow関数

これから使う等式

rows, cols, boxsは対合

expandとrows...の関係

cpの特性

対合とfilter/map

pruneRowの等価性の証明

データ型の定義

solve関数

completions

choices

expand

valid

all

nodups

rows

cols

boxs

結論

Exercise J

Exercise K

Exercise L

Exercise F

Exercise G

Exercise H

Exercise I

構文の統一

データアクセスレベルのコントロール

`pruneRow`関数

`rows, cols, boxs`は対合

`expand`と`rows...`の関係

`cp`の特性

対合と`filter/map`

`pruneRow`の等価性の証明

`solve`関数

`completions`

`choices`

`expand`

`valid`

`all`

`nodups`

`rows`

`cols`

`boxs`