Haskellにおけるたった一つのデザインパターン
デザインパターンを作らないこと。型とクラスがあんたの武器だ。
出、出~~wwwww銀行員待行列解説奴~wwwwwww
銀行員待行列(Banker's deque)、二つのリストで構成奴~~wwwww
入奴と出奴~wwwwwwwww
↓入奴
三(^o^)ノ [(^o^)ノ, (^o^)ノ, (^o^)ノ]
ヽ(^o^)三 [ヽ(^o^), ヽ(^o^), ヽ(^o^)]
↑出奴
追加は入奴にcons、取り出しは出奴にuncons奴~wwwリストなので基本定数時間奴~wwwwww
リスト枯渇防止の為、リストの長さに以下の条件課奴~~~wwwwww
length (入奴) <= length (出奴) * 3 + 1
length (出奴) <= length (入奴) * 3 + 1
条件充足不能場合、|length (入奴) - length (出奴)| <= 1
なるよう余剰分反転後短い側の末尾に結合して調整奴~wwwww時間計算量O(length (入奴) + length (出奴))必要~~~~wwwwww
動作奴~wwww個数nのリストを[n]
表記奴~wwwwwww
入、入~~wwwww調整奴~~wwwwww
[1][1]
入、入、入~wwwww調整不要~wwwwwwww
[4][1]
入~~wwwwwここで調整奴~~wwwwwww
[5][1] → [3][3]
入、入、入、入、入入入入~wwwwww再度調整奴~wwwwww
[11][3] → [7][7]
入入入入入入入入入入入入入入入入wwwwwwww調整必要奴~wwwwwww
[23][7] → [15][15]
入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入~~wwwwwww調整奴~wwwwwww
[47][15] → [31][31]
入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入~~wwwwwwwやっと調整奴~wwwwwww
[95][31] → [63][63]
調整間隔指数関数的増大奴~wwwwwwwww
相対的調整コスト、限りなく0に漸近奴~~~wwwww
収束故、償却定数時間奴~~~~wwwwwwwww
取り出しも同様奴~wwwwwww
出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出~~~~wwwwwww
[63][20] → [41][40]
出出出出出出出出出出出出出出出出出出出出出出出出出出出出出~wwwwww
[40][12] → [26][26]
長ければ長いほど調整コスト相殺奴~~wwwwwwwwww
実装簡単、効率的データ構造奴~~~wwww
参考文献奴~wwwww
- Chris Okasaki (1999). Purely Functional Data Structures
ぼくのかんがえた最強の拡張可能レコード
注意(2018/04) かなり古い記事なので、extensibleの最新のバージョンとはまったく互換性がない
__
動機
GHCに、OverloadedRecordFields(ORF)という拡張の導入が提案されている。
(Records/OverloadedRecordFields/Design – GHCより) Haskellのレコードの深刻な欠点は、フィールドをオーバーロードできないことだ。例えば、
data Person = Person { personId :: Int, name :: String } data Address = Address { personId :: Int, address :: String }
と定義したとき、personId
はどちらを参照すべきかわからない。よくある対策としてデータ型に接頭辞をつけるという方法があるが、コードやフィールド間の関係が不明瞭になる。モジュール単位で修飾するという方法もあるが、レコードごとにモジュールを作るのは非実用的だ。
そこで、personId
をその型によって解決するような、多相なフィールドの写像を扱いたい。r { x :: t }
で、r
はx
という名前の、型t
のフィールドを持つことを表す、新しい形の制約の記法が必要となる。そうすれば、以下のような記述が可能になる。
getPersonId :: r { personId :: Int } => r -> Int getPersonId e = personId e
問題点
最も大きな問題は、フィールドがファーストクラスでないことである。 lensなどのライブラリは、フィールドをデータとして表すことにより、合成などの演算を可能にしている。しかし、ORFのフィールドの概念は制約としてのみ現れる。残念ながら、Haskellは制約レベルのプログラミングは得意ではないため、非常に扱いにくいのだ。
解決
ならばORFに代わる最強の多相レコードを作ってやろう、と私は立ち上がった。仕様は以下の通りだ。
- フィールドは値であり、フィールド名と、それが指し示す対象を型によって決めることができる。
- レコードの型は、フィールド名の集まりによって決まる。
- フィールドはLensとして扱える(重要)。
- レコードの構築にフィールドを使える。必要なフィールドが欠けている場合、型エラーになる。
まず、フィールド名を型に対応させるために型族を用いる。
type family FieldValue (s :: Symbol) :: *
Symbol
は型レベル文字列の型(DataKinds拡張を使う)で、*
は値の型である。
type instance FieldValue "foo" = Bar
と定義すれば、名前"foo"に型Barを対応させることができる。
そして、フィールドの型を以下のように定義する。
data Field (s :: Symbol) = Field { getField :: FieldValue s }
そして、Field
の拡張可能な集まりとして、レコードを実現する。「拡張可能な集まり」のために、拙作のextensibleを利用した。
extensibleパッケージでは、積の表現として(:*)
という型を定義している。型h :* [a, b, c, …]
(型レベルリストを使用していることに注意されたい)は、(h a, h b, h c, …)
のタプルに相当する。直接(a, b, c, …)
と対応させない理由は、すぐに明らかになる。
積を扱うのに必要なAPIはこの3つだ。
Nil :: h :* [] (<:*) :: h x -> h :* xs -> h :* (x : xs) sector :: (x ∈ xs) => Lens' (h :* xs) (h x)
Nilと(<:*)はnilとcons、sector
は、積の特定の要素に対するLens
である。x ∈ xs
は、型レベルリストxs
の中にx
がただ一つ存在することを表す。
ちなみに、x
がない場合、Couldn't match type ‘Missing x’ with ‘Expecting one’
、x
が重複している場合は‘Couldn't match type ‘Ambiguous x’ with ‘Expecting one’
というエラーが出る。地味な売りの一つだ。
そんなわけで、Field :* '["foo", "bar", "baz"]
とすると、(Field "foo", Field "bar", Field "baz")
相当になり、その中身は、foo, bar, bazがFieldValue
が指し示す型になるのだ。レコードの型を以下のように定義しよう。
type Record = (:*) Field
FieldValue
のインスタンスと、Lens (x ∈ xs) => Lens' (Record xs) (FieldValue x)
はできれば一緒に生成したいが、こんなのはTemplate Haskellをちょいと練ればすぐにできるだろう。
mkField "personId" [t|Int|] -- personId :: ("personId" ∈ xs) => Lens' (Record xs) Int mkField "name" [t|String|] mkField "address" [t|String|]
getPersonId
はORF版と同じくらいシンプルに表現でき、言語自体を拡張する必要もない。
getPersonId :: ("personId" ∈ xs) => Record xs -> Int getPersonId = view personId
さて、問題は最後の要件だ。定義したLensをそのまま使い、こんな風に書ければ理想的ではある。
(@=) :: ((s ∈ xs) => Lens' (Record xs) (FieldValue s)) -> FieldValue s -> Field s (@=) _ = Field fubuki :: Record '["personId", "name"] fubuki = personId @= 1 <:* name @= "吹雪" <:* Nil
しかし、mkField
によって生成されるLensと、型族FieldValueは、どちらもフィールド名を具体化するのには使えず、(@=)
は作れないのだ!この世の終わりだー!
諦めるのはまだ早い。実は、既存のLensのインターフェイスを損なうことなく、フィールド名をLensに忍ばせることが可能なのである。
ちょっとした型クラスを用意する。
class Labelable s p where unlabel :: proxy s -> p a b -> a -> b instance Labelable s (->) where unlabel _ = id {-# INLINE unlabel #-}
フィールドの型を以下のように定義し直す。比較のため、普通のLens'
の場合をその下に書く。
type FieldLens s = forall f p xs. (Functor f, Labelable s p, s ∈ xs) => p (FieldValue s) (f (FieldValue s)) -> Record xs -> f (Record xs) -- Lens' (Record xs) (FieldValue s) = forall f. (Functor f) -- => (FieldValue s -> f (FieldValue s)) -> Record xs -> f (Record xs) -- field f = sector (fmap Field . unlabel f . getField)のような形になる(実際は型アノテーションが必要)
(->)
をLabelable p => p
に一般化しているのがポイントだ。これを使うことによって、以下のように単相な「代表」を構成し、フィールド名の曖昧性を排除できるのだ!
data LabelPhantom s a b instance (s ~ t) => Labelable s (LabelPhantom t) where unlabel _ = error "Impossible" type FieldName s = LabelPhantom s (FieldValue s) (Proxy (FieldValue s)) -> Record '[s] -> Proxy (Record '[s])
これのおかげで、無事に(@=)
コンビネータを定義できる。
(@=) :: FieldName s -> FieldValue s -> Field s (@=) _ = Field
めでたしめでたし…いや、志の高い諸君ならば、束縛の順番を入れ替えても大丈夫なようにしたいだろう。そんなときのために、Data.Extensible.Inclusion
のshrink
関数が使える。
shrink :: (xs ⊆ ys) => h :* ys -> h :* xs
前に定義したように、Record
は単なる型シノニムなので、shrink
を適用することによって順番を自由に入れ替えられる(し、一部を切り出すこともできる)。もちろん、型エラーの読みやすさは損なわれていないので、気になる人は試してみるとよいだろう。
fubuki :: Record '["personId", "name"] fubuki = shrink $ name @= "吹雪" <:* personId @= 1 <:* Nil
こうして、街に平和が訪れためうー!型レベルプログラミングのおかげだね!
このアイデアの実装はGitHubのextensibleのリポジトリにあり、次のextensibleのリリースに組み込む予定だ。
結論
OverloadedRecordFieldsなんていらんかったんや!
オブジェクト指向関連の不満な点
また遅れてしまった…オブジェクト指向 Advent Calendar11日目。
最近いろいろオブジェクト指向について調べていて、やっぱりこの概念はいかがなものか、と思ったことを軽く書く。
継承
まずこれ。オブジェクト指向において「AがBを継承している」というのは、外延的には「任意のBのメソッドはAのメソッドである」であり、実装としては「AはBが持つ内部状態やメソッドの実装を利用できる」ことが多い。しかし、Twitterにも似たようなことを書いたが、「車クラスが乗り物クラスを継承している」みたいなゆるふわな使い方が目立つ。クラス、インターフェイスの用語と、それらの継承の定義ははっきりさせたい。則のない関係に意味なし。
抽象クラス、抽象メソッド
実装のない「抽象メソッド」と実装のあるメソッドをごちゃ混ぜにできるような仕様は害があると考えている。インターフェイスがあるにもかかわらずこのような中途半端な仕組みを作るのは、不完全な抽象化と複雑化の原因になりうる。
多重継承
暗黙に何もかも引き継いでしまう仕様と、複数の概念から引き継ぐ仕様は本質的に両立しない。言語の簡単さを犠牲にして小難しいテクニックを導入するより、どこから引き継ぐのか明示したほうが楽に見える。
デザインパターン
デザインパターンは「道具」ではなく、「よくあるパターン」である。なぜそのパターンになったかを感覚的に理解せずに、デザインパターンを「使おう」としてもうまくいかないのに、なぜありがたがっている人が多いのかよくわからない。また、言語設計者はデザインパターンを不要にしていく方向への努力が必要だと考えている。
オブジェクト指向
すべてオブジェクトで扱うのが正義という風潮、これはよくない。オブジェクト指向は、内部状態を持った概念に対する操作の列(メインループでUpdateメソッドを繰り返し呼ぶなど)を抽象化するとき初めて必要になるものだと私は考えている。オブジェクト指向の表現力が高いのは確かだが、だからといって基本的な型や関数をおろそかにするのは本末転倒だ。
私が満足できるようなオブジェクト指向プログラミングができる言語はまだ存在しない。近いうちに理想的なオブジェクト指向プログラミング言語を作って、オブジェクト指向はどうあるべきか、また考えてみたい。
状態、手続き、OOP
これはオブジェクト指向 Advent Calendar 2014の7日目の記事です。
入力によって変化する状態をうまく扱うことはプログラミングにおいて重要である。この記事では、状態や手続きを扱うさまざまなアプローチを紹介、比較する。
手続き型プログラミング
命令の列である手続きを「定義」「呼び出し」する記述力を提供する。命令の結果として得られた値に依存して、次に行う手続きを決定するという性質が肝である。
コルーチン
手続きに区切りを設けることで、「途中まで実行された手続き」を値として扱う。手続きが持つ潜在的な状態を閉じ込めることができるため、柔軟性が高い。
第一級手続き型プログラミング
手続きをデータ構造の一つとして表現し、呼び出すだけではなく、手続きそのものに対する操作も可能にする。「手続きの結果として得られた値に依存して、次に行う手続きを決定する」性質に対応するものとしてモナドがある。モナドはHaskellやPureScriptでは非常によく使われている。
構造体とフィールド
複数の値をまとめて一つの値として扱うための構造。フィールドを指定して、値を取得したり更新したりできる。
第一級フィールド
フィールドを値で表現することにより、より柔軟に構造に対してアクセスできるようにする。第一級フィールドの利点は、それが対象とする構造と強く結びつけられていないことであり、例えばRGBを格納する構造に対し、色相、彩度、明度のフィールドを定義することも可能である。lensはもっとも完成された第一級フィールドの実装であり、フィールド同士の合成や、データ型からの自動生成などができる。
オブジェクト指向
「オブジェクト」と「メソッド」の仕組みを新たに提供する。オブジェクトに対してメソッドを呼び出すと、メソッドに関連付けられた手続きが呼び出され、オブジェクトの内部状態が変化する。オブジェクトの内部状態を表現するのに構造体の仕組みがよく使われている。また、インターフェイスがあれば内部状態の持ち方が異なっても同じように扱えるため、複雑な状態を持つアプリケーションの記述に特に有用である。
第一級オブジェクト指向
オブジェクト指向の諸概念を言語に組み込むのではなく、あくまでデータ構造で表現することで、より自由にオブジェクトを扱う。第一級オブジェクト指向においては、オブジェクトは手続きを手続きに変換するオートマトン、インターフェイスはメソッドの集合であり、継承はメソッドの集合の包含関係で表される。オブジェクト自体が合成可能であるほか、メソッドをモナドにすることで、メソッドを合成可能にもできる。従来のオブジェクト指向と異なり、副作用が常に表現できるわけではないため、ゲームのロジックなどを安全に記述するDSLに応用できる。第一級オブジェクト指向の実装としてobjectiveがある(作った)。
FRP(Functional Reactive Programming)
Behavior(時間によって連続的に変化する値)とEvent(飛び飛びの時間で発生する値)を扱う。BehaviorでEventを振り分けたり、Eventを畳み込んでBehaviorにしたりする関数を組み合わせてプログラムを記述する。入力と出力がはっきりしていれば、信号の流れを非常にきれいに表現できる。一方、手続き的な考え方との相性は良くないので注意する必要がある。FRPの実装として、netwire、Yampa、elerea、sodium、reactive-banana、ordreaなどがある。
まとめ
一般に、言語の組み込み機能として何かの機能を提供するより、型と値を用いて目的のものを実装するほうがより柔軟性が高い。目的が何であれ、型と値の記述力を重視するのが、最高のプログラミング体験への鍵であるとして、この記事を締め括ろう。
大洗に行ってきたよ
はるアイコン鯖 Advent Calendar 2014 - Adventar
※現実で。
※現実で。
※現実で。
海岸
大洗磯前神社入口
絵馬
痛絵馬は西側に偏っている模様。
神社から見える水平線
石が置かれまくっている像
大洗駅内にて
大洗を3つの言葉で表すとすれば、「海」「レンガ」「ガールズ&パンツァー」だ。
この経験を生かし、はるアイコン鯖の大洗にレンガの建物をもっと増やし、ついでに石を置かれまくっている像も作りたい。
はるアイコン鯖の鳥取に製鉄プラントを作る計画が進行中ですが、最近忙しくてインできていないです。すみません…
関数型プログラミングとオブジェクト指向の抜き差し可能な関係について整理して考える
Googleで適当に検索すると
とズラリと出てくる。
関数型とオブジェクト指向という一見相反するプログラミングパラダイムの併用について理解した
プログラマが知るべき97のこと/関数型プログラミングを学ぶことの重要性
新人プログラマに知っておいてもらいたい人類がオブジェクト指向を手に入れるまでの軌跡
関数型プログラミングとオブジェクト指向の抜き差しならない関係について整理して考える
とそれなりに参考になりそうな情報はあるものの、無駄に複雑化されたオブジェクト指向をストローマンにするような記事ばかり(それだけ今までのオブジェクト指向にみんなうんざりさせられているのだろう)で、そろそろきちんと自分自身「関数型プログラミングとオブジェクト指向の切り離され方」についてはっきりさせておきたい、と考え、概念整理した結論を書きます。
まず端的な結論
結論を端的に言うと、
ストリーム変換器 + 手続きの自然変換*1 ⇔ オブジェクト指向
の関係になっている。
「関数型プログラミングとオブジェクト指向を臨機応変に併用する」
だとか、
「関数型プログラミングとオブジェクト指向のマルチパラダイムである」
とすると、今まで見えていなかった部分で概念の重複が起こり、いろいろややこしいことになる、理解においても実践においても混乱を招く、実際混乱を招いている、ということになります。
関数そのものから考える
茶番はここまで。ある純粋な関数fを考えてみよう。:の左は識別子名、右は型シグネチャである。
f : A → B
fは具体的な型Aの値を受け取り、Bを返す。fは純粋なので、いつ値を渡そうと、日本の首都が鳥取になろうと、同じ値を渡せば同じ値が返ってくる。
ところが実用上は、今までに受け取った値に応じて今後の動作を変えたい場面が多々ある。パーサーやWebアプリケーションなどがその例だ(Aに文字やリクエスト、Bにデータやレスポンスが入る)。それを表現するにはどうすればよいだろうか?Bだけではなく、「次のわたし」も一緒に返せばよいのだ。
data TransAB where TransAB : (A → (B, TransAB)) → TransAB runTransAB : TransAB → A → (B, TransAB)
このように、入力によって出力と次の状態が決まる概念をミーリマシン(mealy machine)と呼ぶ。
「次のわたしがある」という制約によって、関数の表現力が増したのだ。
さて、HaskellやPureScriptなどの一部の言語では、手続きそのものをデータ構造として扱うことが一般的に行われている。ある程度の型の表現力があれば、手続きと、手続きの間の関数も定義できる。
もっとも簡単な手続きを定義してみよう。
data Yo x where Yo : Yo Result
見たとおり、Yoしかないので、Yoを超えることはできない。「Yoの結果に対して演算を行う」はできず、「Yoを2回」ももちろん無理。ましてや「前のYoが成功したらYoしない」など夢のまた夢だ。
これをなんとかするために、「モナド」という概念が作られた。下のようにYoの機能を増やすと、前のYoに依存したYoが可能になる。PureとBindの導入については、モナドとはモナドであるも参照されたい。
data Yo x where Pure : a → Yo a Bind : Yo a → (a → Yo b) → Yo b Yo : Yo Result
Yoを具体的な動作に変換する、Haskellに非常に近い言語による実装を示した。
runYo : ∀ x. Yo x → IO x runYo Yo = do print "Yo" return Success runYo (Pure a) = return a runYo (Bind m k) = runYo m >>= runYo . k
手続きの変換を言葉で表すと「手続きの結果が何であっても、中身の構造を保つ関数」となる。最初に扱った純粋な関数と比べると、任意の結果に対応しなければならない分、より表現力が強い。圏論ではこういった変換を自然変換(natural transformation)と呼ぶ。ただ、runYoは純粋なので、いつYoを変換しても、具体的に行われる内容は変わらない。
ここまで紹介した、2種類の関数の発展を地図に描いてみよう。
変換器を「手続きへの適用」方向に伸ばし、自然変換を「状態依存」方向に伸ばした先に宝物がある気がしてこないだろうか?
変換器の領域を緩やかに進んでいた私に、「取舵一杯」となにかが告げた。そして、突如としてそれは姿を現した(表記の統一のために一般化された代数的データ型(GADT)を用いたが、実装に必須ではない)。
data Treasure m n where Treasure : (∀ x. m x → n (x, Treasure m n)) → Treasure m n runTreasure : Treasure m n → m x → n (x, Treasure m n)
ある手続きを受け取ると、その結果と次の状態を返す手続きを生み出す。初めて目にするが、とてもわかりやすい、不思議な感覚。
とりあえず、ミュータブルな変数を作ってみよう。
data Identity x where Identity : a → Identity a data GetSet s x where Get : GetSet s s Set : s → GetSet s () variable : s → Treasure (GetSet s) Identity variable s = Treasure (handle s) handle :: s → GetSet s a → Identity (a, Treasure (GetSet s) Identity) handle s Get = Identity (s, variable s) handle s (Set s') = Identity ((), variable s')
状態を保持する能力を確認できた。次に、この概念が関数のような性質を持つか確かめてみた。まず、恒等関数相当。
echo : Functor m ⇒ Treasure m m echo = Treasure (map (λx → (x, echo)))
(Haskellの場合、mapはfmapと読み替えてほしい)
続いて、合成。$はみんな大好き関数適用演算子(f x $ g y = f x (g y)
)。
(>>>) : Functor n ⇒ Treasure l m → Treasure m n → Treasure l n Treasure m >>> Treasure n = Treasure $ λe → map (λ((x, m'), n') → (x, m' >>> n')) (n (m e))
確かに関数のようにふるまうようだ。
この構造は私に既視感を感じさせたが、その正体がわかった。OOPにおけるオブジェクトのようにふるまうのだ。
オブジェクトは内部状態を持ち、呼ばれたメソッドに応じて、必要があれば内部状態を更新し、副作用を引き起こす――ちょうど、手続きの変換とミーリマシンの両方の性質を持っている。
result = obj.Foo(x, y)
をこのやり方で解釈すると、
(result, obj') ← runTreasure obj (Foo x y)
という表現になる。
共通する性質は、「メソッドレベルの『手続き』を、実装レベルの『手続き』に変換」しつつ、「自分の状態を更新」するという点だ。
TreasureをObjectに改名して、典型的なOOPとの対応をまとめてみよう。
典型的OOP | 関数型OOP |
---|---|
プログラム | IO 型の値 |
クラス | Object M IO 型の値の定義 |
インスタンス | Object M IO 型の参照*2 |
コンストラクタ | Object M IO を生成する関数 |
インターフェース | M |
メソッド | M 型の値 |
フィールド | get : M s とset : s → M () の存在 |
継承 | Object M' M との合成 |
オーバーライド | Object M' Mの実装の一例 |
菱形継承 | メソッドへのパターンマッチ |
ダックタイピング | 存在量化 |
カプセル化 | メソッド以外のアクセス手段なし |
This | 不要 |
不可能 | IOを制限されたクラス(Object M Limited ) |
不可能 | クラスの実装そのものへの操作((>>>t) ) |
オブジェクト指向の仕組みが、たった一つの型の特殊な場合として表現できるのは、なかなか魅力的ではないだろうか。
応用
さっそく、ObjectのHaskellによる実装を作った。Object型に加え、Objectのインスタンスとして利用するためのユーティリティ関数も備えている。
現在、callというゲームエンジンへの応用を試みている。リンク先のコードのように、いかにもオブジェクト指向らしい記述を実際に可能にしている。
結論
オブジェクト指向は、関数型プログラミングと相容れない何かではなく、実装するものだ。