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

今日はBufferについて。 bufferという単語はよく聞くしなんとなく理解していたつもりだったのだけど、全然うまく使えていないので調べてみた。 Bufferとは そもそもBufferとはvimにおける「メモリ上のファイル」のことである。 ハードディスク上のファイルに…

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

「C++は基本的に型安全。コンパイルするなら本来unsafeなことはしない」とはじまるこの項目。本当か？ 「キャストしなければ・・・」と続くわけだが、それにしたって今まで読んできた中にもどれだけundefined behaviourをうっかり踏みそうな地雷を見てきたと…

第６章は証明について。まずは数学的帰納法による証明を説明し、それを元に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…

Thinking Functionally with Haskellがすこし進んできたので、ちょっと今まで出てきた概念と関連するところまで圏論について調べてみた。まごうことなき私的勉強メモ。 圏Cは以下の三つの要素をあわせた概念： Object（対象）の集まり Cに含まれる対象間のmo…

古き良きCの作法だと使う変数はすべて関数の一番最初に宣言しておくものだった。 モダンなCだとその必要はないが、C++だとむしろ強く非推奨になる。 いくつかの理由がある。 一つには、変数宣言はその場でコンストラクタの実行を伴い、またスコープから出る…

Rでツイートに収まりきる文字数でアート、というブログ記事があった： www.r-bloggers.com いろいろな数式を使ってきれいなパターンをグラフ機能で表示させる、というもの。 残念ながらそこまで文字数を制限することはできなかったが、とりあえずライブラリ…

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

今回はスクリーン移動系 H,M,L 現在見せている文書の範囲はまったく変えずに、カーサだけをウィンドウの一番上([H]igh)、真ん中([M]iddle)、一番下([L]ow)に移動する。 zt, zz, zb, C-E, C-Y 文書内でのカーサの現在地は変化させずに、見せている文書の範囲…

C++にはpimplというイディオムがある。 何か大きなデータを持つオブジェクトがある場合、単純にデータメンバとしてしまうと（例えば関数にデータを渡したりする時に）コピーが発生するとコストが高い。 そういう場合には、データを実際に保持するクラスと、…

数式で表せる曲線を描いてみる。 元ネタ Proce55ing.walker,blog » Blog Archive » 図形を描く数式の使い方 毎度のことながらProcessing Advent Calendar。こういう記事がまとまっている場所があるのは、習作アイディアをもらうのにすごく便利で、参加された…

ごくたまに暗黙の型変換が役にたつ時がある。特定の数字を表現するクラスを定義する時などである。 class Rational { private: const int numerator, denominator; public: Rational(int numerator = 0, int denominator = 1); const Rational operator*(con…

SFやアニメのコンピュータスクリーンによく出てくる、円状のものがクルクルと違うスピードで回ってるやつ。 こちらが元ネタ： labs.uechoco.com Quil版： Quil -L7vYVzO6uheSLTyNizI q/arcがほぼ使い物にならないレベルでガタガタだったので、表示しているの…

例によってProcessing Advent CalendarからQuilで作るネタを漁っている。 今回はこの記事： Proce55ing.walker,blog » Blog Archive » マトリックスのアレを作ってみよう このかたは2011年のProcessing Advent Calendar記事の大半を書いていてすごい。今後も…

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

昔のProcessing Advent Calendarをいろいろ漁っていたらこんな記事があった： qiita.com 上記の記事の冒頭の絵は で表されるアトラクターである。 以下の参考サイトにはもっと例が載っている。 Clifford Attractors まさにClojureのiterate関数の使いどころ…

クラス内のデータはpublicでもprotectedでもなくprivateにしよう。という話。 ポイントは三つ 構文の統一 データアクセスレベルのコントロール カプセル化 構文の統一 オブジェクトのAPIはすべて関数（か演算子）になり、a.somethingだったかa.something()だ…