関数型言語について質問です。

自分は、静的型付け言語と動的型付け言語でプログラムする時で発想段階から違うと感じます。

設計をしている時に、解いている問題の性質を色々考えますよね。動的型付けの場合は、「値から発想」することが多いです。入力にこんな値が来て、それをこう加工してこういう値にくっつけて、すると出力はこんな値になって…と、具体的な値に近いところから発想して、それを一般的なケースに広げて行く感じ。

それが静的型付けの場合は、「型から発想」になります。入力のデータはこんな性質Xがある。処理の中身は今まだわからないけど、最終的な出力はこの性質Zを満たすはずだ。ということは、入力をまず性質Yを満たす中間出力に変換して、次にYからZに変換する何かを噛ませてやれば良さそうだ…と、データが満たすべき性質とその関係を出発点にして、徐々に具体的な動作へと広げてゆく感じです。

適当に例をでっちあげてみます。(Haskell最近書いてないので不自然かもしれません。Haskellerの方々、突っ込んでください)

* 何かのデータの集まりがある。そのデータを、データ中のあるキーの大小に応じて並べた時に中央に来るデータを取り出したい

なんて問題があるとします。

* 入力の個々のデータの具体的な形はまだよくわからないので、とりあえず型aとしておこう。処理の入力の型はaのリスト、つまり[a]だ。
* キーの具体的な形もまだよくわからないので、キーの型をとりあえずbとしておく。そしたら各データからキーを取り出す関数の型は a -> b だな。
* bはソートできなければならない、ということは二つのbが比較可能であるということだ。bが比較可能であるというのはOrd bと書く。Ord bの性質を持つ型には、比較関数 b -> b -> Ordering が定義されてる。
* 出力は一個のデータだから、型はaだ。あ、でも入力が空だと出力が出てこないな。「無いかもしれない」という性質を表すにはMaybe aと書く。

ここまで考えると、この処理全体の型がこう書けます。

getMedian :: Ord b => (a -> b) -> (b -> b -> Ordering) -> [a] -> Maybe a
getMedian key compare xs = undefined

処理の中身を考える前にここまで書いてしまいます。中身はまだわからないので
undefinedと書いておきますが、このままでもコンパイルは通せるので、
より大きな処理の中に組み込んで型の整合性だけチェックすることはできます。

ここから、処理の中身を分割してゆきます。

* まずキーを取り出してソート出来るようなリストにしないとな。入力データからキーを取り出して各要素にくっつけてやる処理がいるな。こんな処理。

[a] -> (a -> b) -> [(b,a)]

* これはmapの型 [a] -> (a -> b) -> [b] に良く似てる。mapを使って結果を[(b,a)]にするには
[a] -> (a -> (b,a)) -> [(b,a)] とすればいい。ってことは、
key :: a -> b から addKey :: a -> (b,a) を作ってやればいい。

addKey :: a -> (b,a)
addKey x = (key x, x)

* で、[(b,a)]のリストをsortByでソートする。sortByに渡す比較関数は要素を直接比べるから
(b,a) -> (b,a) -> Ordering でないとならない。今、compare:: b -> b -> Ordering が
渡されてるのでそれを(b,a) -> (b,a) -> Ordering に変換しないとな。(b,a)からbを取り出すのはfst。

cmp :: (b,a) -> (b,a) -> Ordering
cmp p q = compare (fst p) (fst q)

* そしたらこれをくっつけると、キーでソートされた(b,a)のリストができる。

ys :: [(b,a)]
ys = sort cmp $ map addKey xs

* 中央のインデックスはysの長さを1bit右シフトしてやればいい。

k :: Int
k = shift (length ys) (-1)

* リストysからk番目の要素を取り出すのは ys !! k。この型は(b,a)だから、aを取り出すsndを噛ませて、さらにMaybe型で値があることを表すJustで包んでやる。入力が空の場合はNothingを返す。全部合わせるとこの通り。

import Data.List
import Data.Bits

getMedian :: Ord b => (a -> b) -> (b -> b -> Ordering) -> [a] -> Maybe a
getMedian key compare [] = Nothing
getMedian key compare xs = let addKey x = (key x, x)
cmp p q = compare (fst p) (fst q)
ys = sortBy cmp $ map addKey xs
k = shift (length ys) (-1)
in Just $ snd $ ys !! k

このくらいの規模なら型を考えなくても動的型付け言語でさくっと書けるかもしれませんが、問題が複雑になると、まず型を合わせておいて後から具体的な実装を考えるという方法はなかなか強力です。

私は動的型付け言語がホームグラウンドなのでついつい具体的なデータを渡して確かめたくなってしまうのですが、型の達人は具体的なデータを触る前に型でもって大きな足場を組み上げちゃうような印象がありますね。

うわあインデントが消えちゃった。上のgetMedianのコードはそのままコピペしてもインデントが揃ってないので動きません。コメントでインデント保持するのってどうすんだろ。