Haskellの型クラスを活用する

Haskellの型クラスは、うまく使えば高いパフォーマンスと抽象度を両立できる、優れた仕組みである。その使い方のコツは、決して理解の難しいものではない。

小さな性質、大きな恩恵

プログラマは大きなものを小さく見せがちだ。オブジェクト指向プログラミングに慣れている人がやりがちなアンチパターンとして、欲しい機能と、それを分割する基準が現実に寄りすぎていて、一つ一つが巨大というものがある。

普通のプログラミングではありえない例かもしれないが、たとえば家を作りたいことを考える。「ベッド」「箪笥」「台所」「冷蔵庫」「トイレ」「風呂」のように設備ごとに分けた抽象化をしたいと考えるだろう。確かにこれは理に適っているように見える。だが、これらの設備を型クラスでまとめるのは悪手だ。

風呂やトイレには水を利用できるという性質が、冷蔵庫には電気が必要だ。部屋と部屋は壁で仕切られ、場合によっては扉があるかもしれない。水を伝えるにはパイプで繋がなければいけない。電気を取り出すにはコンセントで繋ぎ、扉を取り付けるには蝶番がなければ。繋ぐと一言で言っても、その方法は様々である。「繋がれたものは安定して機能を果たせる」という論理的な共通点から、様々な操作を「繋ぐ」という言葉で抽象化している。このレベルの話でやっと型クラスが有用になってくる。

コンパイル時の定め

Semigroupという型クラスがsemigroupsパッケージで定義されている。これは半群という代数的構造を表すクラスで、二項演算(<>)を持つ。

class Semigroup a where
    (<>) :: a -> a -> a

ただし、正当なSemigroupになるには条件があり、どんなa, b, cに対してもa <> (b <> c) == (a <> b) <> cが成り立たななければいけない。

Semigroupの例として、リストとその結合、数値の足し算や掛け算などがある。()の場合は何もしない。

instance Semigroup () where () <> () = ()
instance Semigroup [] where (<>) = (++)
instance Num a => Semigroup (Sum a) where Sum a <> Sum b = Sum (a + b)
instance Num a => Semigroup (Product a) where Product a <> Product b = Product (a * b)

型さえはっきりしていれば、コンパイル時にインスタンスが選択され、(<>)はふさわしい実装で置き換えられる。これに関してパフォーマンスで心配する必要はないし、繰り返し使うのにも適している。一方、仮に風呂が型クラスのメソッドだったとしても、風呂をたくさん置く家はあまりないだろう。

実行の前奏曲

GHC 7.10以前は、Preludeのfoldrなどの関数はリスト専用だった。7.10以降は、Foldableメソッドとして一般化されている。これによって今までのコードが遅くなる心配をする必要はない。実際にリストに対するfoldrを含むプログラムを-ddump-rule-rewritesオプションをつけてコンパイルすると、リスト専用のfoldrに置換されるのを確認できる。

Rule fired
    Rule: Class op foldr
    Before: Data.Foldable.foldr
              TyArg []
              ValArg Data.Foldable.$fFoldable[]
              TyArg GHC.Types.Int
              TyArg GHC.Types.Int
              ValArg GHC.Num.$fNumInt_$c+
              ValArg GHC.Types.I# 0
              ValArg GHC.Enum.$fEnumInt_$cenumFromTo (GHC.Types.I# 0) i_aqJ
    After:  GHC.Base.foldr
    Cont:   Stop[BoringCtxt] GHC.Types.Int

コンパイル時の置換をより積極的に利用した例としてlensパッケージも挙げられる。Lensはゲッターとセッターの対から構築されるアクセサである。

lens :: Functor f => (s -> a) -> (s -> b -> t) -> (a -> f b) -> s -> f t
lens getter setter f s = fmap (setter s) (f (getter s))

viewsetは、Lensが使うfmapConstIdentityのために特殊化することでゲッター、セッターとしての機能を取り出している。

view :: ((a -> Const a a) -> s -> Const a s) -> s -> a
view l = getConst . l Const

set :: ((a -> Identity b) -> s -> Identity t) -> b -> s -> t
set l b = runIdentity . l (Identity . const b)

実際に式を変形するとその挙動は明らかだ。lensパッケージはcoerceなども併用することで、以下の変形をコストなしで実現している。なんたる業前か!

view (lens getter setter) s
= getConst $ fmap (setter s) (Const (getter s))
= getConst $ Const (getter s) -- fmap _ (Const x) = Const x
= getter s

set (lens getter setter) b s
= runIdentity $ fmap (setter s) (Identity (const b (getter s)))
= runIdentity $ fmap (setter s) (Identity b)
= runIdentity $ Identity (setter s b) -- fmap f (Identity a) = Identity (f a)
= setter s b

こうしてみると、型クラスは「複雑な処理をまとめる」というよりは「特定の性質を持つ処理を最適な形で具体化する」ものと見ることができる。たいていの型クラスは半群や関手のような代数的な構造であり、ライブラリとして既に定義されている場合がほとんどである。その観点では、ユーザーである私たちは、あえて新しいクラスを定義する必要は基本的にないのだ。私はHaswerkというMinecraftクローンを開発しているが、今のところ独自のクラスは宣言しておらず、これから作る予定もない。

まずは、Haskellのエコシステムに鎮座する型クラスの数々を最大限に活用しよう。型クラスは抽象化のポータル(玄関口)である。クラスのメソッドを使うことで、あるいはインスタンスを定義することで、互いに再利用できるコードが生まれる――インスタンスが満たす「性質」を頼りにして。

最近やったこと

最近やったことのまとめ。

CPSモナド変換子

fumieval.hatenablog.com

で作ったmtl-cの塵を払い、Hackageにリリースした

StateTやWriterTは中でタプルを作ったり壊したりしているが、CPS変換するとそれがなくなり、しかも(>>=)も最適化されるためそれなりのパフォーマンスの向上が期待できる。モナドガチユーザにおすすめだ。

補足 GHC 7.10.1現在、StateTに関しては最適化がうまく効くらしく、Lazy、Strict、CPS版のパフォーマンスはほぼ同じだった。一方、CPS版WriterTは正格にしているためか、Strictの4倍、Lazyの8倍の速度を発揮した。なお、CPS版はベースのモナドが重いときには特に効果的に働く。

後悔なく具現化できるモナド

monad-skeletonというパッケージを公開した。インターフェイスとしては普通のOperationalモナドだが、実装に一工夫がされており、(>>=)が左結合になってもパフォーマンスが落ちにくい特長がある。

基本となる型Skeleton tは、命令tの列がなすモナドである。命令を持ち上げるにはbone :: t a -> Skeleton t a、命令を取り出すときはunbone :: Skeleton t a -> MonadView t (Skeleton t) aを使い、MonadViewに対するパターンマッチによってSkeletonインタプリタを書ける。

data MonadView t m x where
  Return :: a -> MonadView t m a
  (:>>=) :: t a -> (a -> m b) -> MonadView t m b

命令を集めて君だけのモナドを作ろう!

吹きすさび要素を枯らすイテレータ

witherableの新しいバージョンをリリースした。

Traversableクラスのtraverseは作用を伴った要素のマッピングをするが、このパッケージで定義されているWitherabletraverseの能力に加え要素の削除も抽象化する。Witherableのメソッドを見ればわかりやすい。

class Traversable t => Witherable t where
    wither :: Applicative f => (a -> f (Maybe b)) -> t a -> f (t b)
    mapMaybe :: (a -> Maybe b) -> t a -> t b
    catMaybes :: t (Maybe a) -> t a
    filterA :: Applicative f => (a -> f Bool) -> t a -> f (t a)
    filter :: (a -> Bool) -> t a -> t a

幅広く使えそうだが、元々は定命のオブジェクト(死ぬオブジェクト)の集まりを管理する関数apprisesの実装のためだけに作った。 あえてリストで返さずに継続を使う理由については、モノイドと継続渡しの道具箱も参照されたい。

apprises :: (Witherable t, Monad m, Monoid r)
    => f a -- メッセージ
    -> (a -> r) -- 結果を回収
    -> (b -> r) -- もしくはオブジェクトの亡骸を回収
    -> StateT (t (Mortal f m b)) m r -- 定命のオブジェクトのコンテナへの操作

拡張可能なデータ構造

extensibleを更新した。なんといってもextensibleの売りは、今までの拡張可能系ライブラリとは一線を画し、どんな種でも扱えることだ。

extensibleが提供する拡張可能レコードおよびバリアントは以下の種を持っている。

RecordOf :: (v -> *) -> [Assoc k v] -> *
VariantOf :: (v -> *) -> [Assoc k v] -> *

v -> *のパラメータを利用すれば、*でも* -> *でも* -> * -> *でも、レコードおよびバリアントの対象になる。そのおかげで、単純なレコードだけでなく、多相型も使えるExtensible effects、ファーストクラスパターンマッチ、objectiveと組み合わせればクラスベースオブジェクト指向も実装できるぞ。以下はextensibleとaesonを組み合わせ、要素に型の付けられるJSONパーサを実装する例。

gist.github.com

objective

Michael Snoyman先生のおかげでインスタンスが例外安全になった(https://github.com/fumieval/objective/commit/ffffc5b7afba88155be9c08c1b8204b7cadfe0a4)。もしオブジェクトが例外を投げたとき、例外を発生させる前のオブジェクトにロールバックする。これによって不正な状態の発生を防ぐことができる。オブジェクト指向の実装で、このようにしてオブジェクトの整合性を保つのはなかなか新しいアイデアだと思う。

また、extensibleと組み合わせてExtensible effectsの実現も試みている。山本和彦さん曰くobjective以外でOperationalモナドが本当に役立つ例を見たことがないそうなので、おそらくobjectiveパッケージの一部として提供することになる。

謎のひも

ファイルから音声を読み込むなど、シーク可能なデータを扱いたい場面がある。相対的なものと絶対的なものを合わせればシーク操作はモノイドになるという点に着目し、実験段階だがtapesというものを実装したが、終端の扱いにまだ疑問が残る。開いたり閉じたりする概念は本質的に難しい。

Haskellでいかに多態を表すか

オブジェクト指向を行使する心 ではオブジェクト指向の必要性と仕組みについて議論した。

インスタンスは言語によって様々な実装方法があるが、大きく分けて「クラス(処理)のインデックス」か「処理そのもの」のどちらかがインスタンスの内部に隠れている。

と述べたが、Haskellの場合、クラスのインデックスに基づいた表現では、インターフェイスは型クラス、クラスはインスタンスインスタンス存在量化された型の値に対応する。…といってもややこしいことこの上ないので、実装例を考えてみよう。

まず、問題となっている愚直な実装は、Haskellではこんな感じだ。

data World = World { … }
data SceneId = Menu | Map | Battle

draw :: SceneId -> World -> IO World
draw Menu = …
draw Map = …
draw Battle =

Worldは描画に必要なすべての情報が入っている、グローバル変数のようなものと考えてよい。新しいシーンを追加するにはSceneIddrawを両方書き換える必要があるため扱いにくく、シーンではなくキャラクターなどを管理するとなればなおさらだ。

存在量化を用いると以下のように書ける。

data Menu = Menu
data Map = Map
data Battle = Battle

class Scene a where
    draw :: a -> World -> IO World

instance Scene Menu where
    draw =instance Scene Map where
    draw =instance Scene Battle where
    draw =instance Scene SomeScene where
    draw (SomeScene a) = draw a

data SomeScene = forall a. Scene a => SomeScene a

data Menu = Menuのくだりは若干ばかげているようにも見えるが、定義にシーン固有の値を追加してもよい。各シーンを表す値であるMenuMapBattleSomeSceneで包むと、内部にはインスタンスを識別するためのタグが入り、型を共通にしつつ実行時に処理を切り替えられる。標準ライブラリのControl.Exceptionではこの方法を採用しており、便利ではあるがSomeSceneのようなものを毎回作らなければならないのがいまいちだ。

インスタンスに直接処理を格納するアプローチとしてはHaskell's overlooked object system*1HListがある。異なった型の要素を持てるリストを用い、操作の直接的な集まりとしてインスタンスを表す。

import Data.HList

draw = Label :: Label "draw"

type Scene = Record '[Tagged "draw" (World -> IO World)]

sceneMenu :: Scene
sceneMenu = draw .=..*. emptyRecord
sceneMap :: Scene
sceneMap = draw .=..*. emptyRecord
sceneBattle :: Scene
sceneBattle = draw .=..*. emptyRecord

こちらはシーンを値として定義できるのが魅力だ。演算子(#) :: HasField l r v => r -> Label l -> vdrawの処理を呼び出せる。しかしその裏の仕組みがとても複雑なうえ、IORefなどを用いないと状態をまともに扱えないのが難点である。

objectiveはそのどちらでもなく、オブジェクトの中身は「操作を解釈する関数」になっている。

newtype Object f g = Object { runObject :: forall x. f x -> g (x, Object f g) }

あくまで操作とオブジェクトは別の概念として扱うのが特徴で、種が* -> *ならば任意のデータ型を操作として利用できる。Scene型のオブジェクトはSceneOpを受け取りStateT World IOの型のアクションを生み出す。

import Control.Object

data SceneOp a where
    Draw :: SceneOp ()

type Scene = Object SceneOp (StateT World IO)

sceneMenu :: Scene
sceneMenu = Object $ \Draw -> …

sceneMap :: Scene
sceneMap = Object $ \Draw -> …

sceneBattle :: Scene
sceneBattle = Object $ \Draw ->

runObjectにオブジェクトとDrawを渡すと、オブジェクトはDrawの結果と次のオブジェクトを返す。これをそのまま使ってもよいが、new :: Object f g -> IO (Instance f g)を用いてインスタンスを生成することもできる。(.-) :: Instance f g -> f x -> g xを使うと、インスタンスは次のオブジェクトで置き換わるため、広く使われているメソッド呼び出しも可能だ。

オブジェクトは関数と同様のコンポーザビリティを持ち、既存のオブジェクト指向の実装を超える拡張方法も提供する。具体的な利用については以下のちゅーんさんの記事で詳しく述べられているので、こちらも参照されたい。

tune.hateblo.jp

tune.hateblo.jp

存在量化、HList、objectiveは多態を実現するが、それぞれ表現方法は全く異なる。純粋、ファーストクラス、合成可能、この言葉にピンときたらobjectiveを是非使ってみてほしい。

*1:Oleg Kiselyov, Ralf Lämmel , http://arxiv.org/pdf/cs/0509027.pdf, 2008

オブジェクト指向を行使する心

今日、とあるツイートでプログラミングにおけるよくある問題が顕現していた。

奇妙な行コメントには目を瞑るとして、このコードは要約すれば以下のような処理を実現していることが窺える。

  • ゲームプログラミングでは、現在のシーンによって処理を切り替える必要がある。メニュー画面ならメニューの処理を、戦闘画面なら戦闘を、マップならマップの表示をそれぞれ行う。
  • 現在のシーンの種類は変数によって与えられる。
  • その変数の値によって、対応する処理を選ぶ。

こうしてみると単純だが、caseによる単純な分岐では扱いにくい。新しいシーンを作るたびに場合分けを書き換えなければならないし、何よりそれは「処理」と「処理を表す値」の一覧表を作るという面白みのない処理だからだ。

一つの(そして、よく用いられる)解決法はオブジェクト指向プログラミングである。各シーンをオブジェクトとして扱うことにより、問題となっている分岐を扱う必要がなくなる。

新たに、操作の集まりによって定義される「インターフェイス」という構造を導入する。以下の疑似コードでは、Sceneとして扱う型は、drawという処理が使えることを示している。

interface Scene:
    draw()

インターフェイスによって定められた操作を実装するのが「クラス」である。MenuMapBattleという3つのクラスを定義し、それぞれ異なるdrawの実装を持っている。

class Scene ⇒ Menu:
    draw():
        …

class Scene ⇒ Map:
    draw():
        …

class Scene ⇒ Battle:
    draw():
        …

これらの処理を実際に使うには「インスタンス」を用いる。

s ← new Menu()

これはMenuの実体を持つインスタンスを生成し、sに代入する操作を表す。ここで得られたインスタンスsSceneの型を持つ(サブタイピングがあれば、Menuの型を持ってもよいが、Sceneであることがここでは重要である)。

s.draw()Sceneが保証しているdrawの処理を実行する。MenuインスタンスなのでMenudrawが実行されるが、仮にnew Map()で生成した場合はMapdrawになる。ここで注目すべきは、コードや型は一緒でも、実際に行われる処理は動的に決まるという点だ。今までは、シーンを表す値を見て処理を自分で選択しなければならなかったが、その必要がなくなっているのがわかる。したがってシーンの種類が増えても、drawを呼ぶ部分を修正する必要はない。

なぜこのようなことを可能にしているのか?そのからくりはインスタンスに宿っている。インスタンスは言語によって様々な実装方法があるが、大きく分けて「クラス(処理)のインデックス」か「処理そのもの」のどちらかがインスタンスの内部に隠れている。

前者の場合、s.draw()は、sの中身のインデックスを元に、対応するクラスのdrawを取り出して実行する。new Menu()で作ったインスタンスには、Menuを表すインデックスが入っており、new Battle()で作ればBattleを表す値が入っている(文字列でも数値でも、一意に対応させられれば何でもよい)。今までの方法と実は全く同じだが、自動化されていると言える。

後者はより簡単で、インスタンスにはインターフェイスが保証する処理の実装がすべて入っている。s.draw()は、sの中に入っているdrawの処理を取り出しているに過ぎない。

C++などの静的型付きの言語は前者を、Pythonなどの動的型付きの言語は後者を取る傾向がある。なお、静的型付きの言語であるHaskellではどちらの方法でも実現できるが、あまり使われていない。

いずれにせよ、特にゲームプログラミングにおいて、動的に処理を選択したい場合は少なくない。オブジェクト指向がその便利な解決法であることは間違いなく、実際にゲームプログラミングで使われている言語のほとんどはオブジェクト指向をサポートしている。

モノイドと継続渡しの道具箱

関数型言語Haskellにおいて、普通は計算の結果は関数の戻り値として扱うが、「結果を受け取る関数」 に渡すという継続渡しというスタイルもある。これは単なる冗長なやり方ではなく、様々な興味深い性質を持つ。

基本形は、aという値を渡すところを

∀r. (a -> r) -> r

のような表現にする。たとえば、与えられた数の42倍を渡したいとき、そのまま\x -> x * 42ではなく、\x f -> f (x * 42)と書く。もちろんこれだけではありがたみが分からない。

さて、与えられた文字列の中のうち、大文字のアルファベットを取り出し、それがアルファベットの何番目か計算するプログラムを作りたい。普通はリストを使ってこのように書くかもしれない。

import Data.Char

uppers :: [Char] -> [Int]
uppers [] = []
uppers (x:xs)
   | isUpper x = fromEnum x - fromEnum 'A' : uppers xs
   | otherwise = uppers xs

継続渡しにすると([Int] -> r) -> rという形にもできるが、あえて(Int -> r) -> rのようにIntを渡したい場合はどうなるだろうか?すると、rのために新たな演算が必要になる。

uppers :: (Int -> r) -> [Char] -> r
uppers f [] = (空っぽ)
uppers f (x:xs)
   | isUpper x = (がっちゃんこ) (f (fromEnum x - fromEnum 'A')) (uppers f xs)
   | otherwise = uppers f xs

ここで(空っぽ)(がっちゃんこ)の型に着目しよう。

(空っぽ) :: r (がっちゃんこ) :: r -> r -> r

つまり、rは空の値と、結合する演算を持つような型であることがわかる。これはモノイドと呼ばれる代数的構造である。HaskellではMonoid型クラスとして提供されている。

class Monoid a where
    mempty :: a
    (<>) :: a -> a -> a -- 実際は(<>) = mappendとして定義されている

Monoid rの制約をつけ、空っぽとがっちゃんこはそれぞれmempty(<>)で置き換えてやれば望みのプログラムは作れる。

uppers :: Monoid r => (Int -> r) -> [Char] -> r
uppers f [] = mempty
uppers f (x:xs)
   | isUpper x = f (fromEnum x - fromEnum 'A') <> uppers f xs
   | otherwise = uppers f xs

大文字をカウントするには、要素を数えるような振る舞いを持つモノイドを作ればよい。

data Count = Count { getCount :: Int }

instance Monoid Count where
    mempty = Count 0
    Count m <> Count n = Count (m + n)

single :: a -> Count
single _ = Count 1

実際にはSumというモノイドが定義されており、Countと同様、足し算がなすモノイドとして働く。

upperssingle関数を渡すとCountが返ってくる。その中身は数え立てほやほやの大文字の個数だ。

getCount . uppers single :: [Char] -> Int

uppersは、リスト以外の構造に対しても考えられる一方、要素の数え上げを実現するCountは、uppersの扱う対象の構造には関与しない。その関心の分離に、このスタイルのパワーが表れている。

uppers :: Monoid r => (Char -> r) -> Map String Char -> r
uppers :: Monoid r => (Char -> r) -> Maybe Char -> r
uppers :: Monoid r => (Char -> r) -> Seq Char -> r

標準ライブラリでは、uppersのような操作を抽象化するFoldableというクラスが定義されている。 foldMapは、コンテナf aの要素をすべて与えられた関数に渡すことが期待されている(期待されているというのは、一部だけ渡しても、あるいはまったく渡さなくても正当なインスタンスたりうる)。

class Foldable f where
    foldMap :: Monoid r => (a -> r) -> f a -> r

なお、大文字のみをフィルターする機能は独立して定義することが可能だ。

filtering :: Monoid r => (a -> Bool) -> (a -> r) -> a -> r
filtering p f a
    | p a = f a
    | otherwise = mempty

また、要素のマッピングも独立した関数として定義できる。こちらは単なる関数合成だ。

maps :: (a -> b) -> (b -> r) -> a -> r
maps f g = g . f

foldMapfilteringmapsを組み合わせれば、uppersは以下のように書ける。上から下に処理の流れが表現されているのがわかるだろうか。

uppers :: (Foldable f, Monoid r) => (Int -> r) -> f Char -> r
uppers = foldMap
  . filtering isUpper
  . maps (subtract (fromEnum 'A') . fromEnum)

このような継続とモノイドを用いた畳み込みの仕組みは、高い柔軟性と美しい合成を提供する。 しかし、これでは不足する場合がある。というのも、foldMapは元の構造を忘れてしまうので、構造を保ったまま要素を書き換えたりする目的には使えない。たとえば、シーザー暗号を実装したい場合、今までのuppersでは元のリストを失ってしまうため実現できない。

元のuppersの定義に戻ってみよう。(空っぽ)(がっちゃんこ)に元の構造を取り戻すヒントを教えてやれば、どうにかうまくやれそうだ。

uppers' :: (Int -> (Intを保つ何か)) -> [Char] -> ([Char]を保つ何か)
uppers' f [] = (空っぽ) []
uppers' f (x:xs)
   | isUpper x = (がっちゃんこ) (:) x' (uppers' f xs)
   | otherwise = (がっちゃんこ) (:) ((空っぽ) x) (uppers' f xs)
   where
       x' = (ごにょ) (\n -> toEnum $ n + fromEnum 'A') (f (fromEnum x - fromEnum 'A'))

ここでの(空っぽ)、(ごにょ)、(がっちゃんこ)はそれぞれ以下のような型を持つはずだ。

(空っぽ) :: s -> (sを保つ何か)
(ごにょ) :: (a -> b) -> (aを保つ何か) -> (bを保つ何か)
(がっちゃんこ) :: (a -> s -> (sを保つ何か)) -> (aを保つ何か) -> (sを保つ何か) -> (sを保つ何か)

(xを保つ何か)というのは型パラメータxを持つ型で表せる。ここではfとしよう。

(空っぽ) :: s -> f s
(ごにょ) :: (a -> s) -> f a -> f s
(がっちゃんこ) :: (a -> s -> f s) -> f a -> f s -> f s

これらの操作ができるようなfにはApplicativeという名前がついている。

class Functor f where
    fmap :: (a -> b) -> f a -> f b

instance Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

liftA2 :: Applicative f => (a -> b -> f c) -> f a -> f b -> f c
liftA2 f a b = fmap f a <*> b

(ごにょ)fmap(空っぽ)(がっちゃんこ)がそれぞれpureliftA2である。すると、uppers'はこう書ける。

import Control.Applicative

uppers' :: Applicative f => (Int -> f Int) -> [Char] -> f [Char]
uppers' f [] = pure []
uppers' f (x:xs)
   | isUpper x = liftA2 (:) x' (uppers' f xs)
   | otherwise = fmap (x:) (uppers' f xs)
   where
       x' = fmap (\n -> toEnum $ n + fromEnum 'A') (f (fromEnum x - fromEnum 'A'))

Applicativeは「元の構造を保てる」モノイドになっている。もしシーザー暗号を実装する場合、結果として[Char]そのものが欲しい。 そんな時は、元の構造をそのまま包むIdentityが使える。

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)

instance Applicative Identity where
    pure = Identity
    Identity f <*> Identity a = Identity (f a)

シーザー暗号は以下のように実装できる。Identityは操作をそのまま中身に伝えるので、純粋な結果が得られる。

caesar :: Int -> [Char] -> [Char]
caesar k = runIdentity . uppers' (Identity . (`mod`26) . (+k))

いちいちIdentityrunIdentityを書くのは骨なので、以下のような関数で共通化すると便利だ。

purely :: ((a -> Identity a) -> s -> Identity s) -> (a -> a) -> s -> s
purely t f = runIdentity . t (Identity . f)

各要素に対してアクションを走らせたい場合は、それをそのまま渡すだけだ。一番簡単なパターンかもしれない。

printUppers :: [Char] -> IO [Char]
printUppers = uppers' (\x -> print x >> return x)

もし今までと同じように元の構造を捨て、モノイドにしたいときは、そのようなふるまいを持つApplicativeが使える。

newtype Const r a = Const { getConst :: r }

instance Functor (Const r) where
    fmap _ (Const r) = Const r

instance Monoid r => Applicative (Const r) where
    pure _ = Const mempty
    Const a <*> Const b = Const (a <> b)

uppers'ではfmappureに元の構造のための操作が渡されていたが、Constはそれらを捨てており、代わりにモノイドの演算をしていることがわかる。以下のsmashは、Constを用いて「格下げ」を行う関数で、uppers = smash uppers'の関係が成り立つ。

smash :: ((a -> Const r a) -> s -> Const r s) -> (a -> r) -> s -> r
smash t f = getConst . t (Const . f)

この強化されたuppers'だが、こちらも共通化のためのクラスが提供されており、こちらはTraversableと呼ばれている。traversefoldMapの上位版に位置する。

class (Functor t, Foldable t) => Traversable t where
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

フィルターは今までとほぼ同じような形で、独立して定義できる。

filtered :: Applicative f => (a -> Bool) -> (a -> f a) -> a -> f a
filtered p f a
    | p a = f a
    | otherwise = pure a

要素へのマッピングをするには、元の構造に戻すための関数が追加で必要となる。

isomorphic :: Functor f => (s -> a) -> (a -> s) -> (a -> f a) -> s -> f s
isomorphic f g c = fmap g . c . f

traversefilteredisomorphicを使うとuppers'はこう書ける。IntCharに戻す関数が必要になったのを除けば、Foldable版とほぼ変わらない。

uppers' :: (Applicative f, Traversable t) => (Int -> f Int) -> t Char -> f (t Char)
uppers' = traverse
    . filtered isUpper
    . isomorphic (subtract (fromEnum 'A') . fromEnum) (\n -> toEnum $ n + fromEnum 'A')

このように、foldMaptraverseに代表されるようなこの手の関数は、コンテナの処理に対して素晴らしい表現力を持つ。 ならばこれを最大限に活用しようと作られたのがlensパッケージだ。

uppers'のような関数はtraversalと呼ばれ、lensパッケージでは型シノニムが定義されている。

type Traversal' s a = forall f. Applicative f => (a -> f a) -> s -> f s

たとえば、コンテナの特定の要素を指すtraversalなどを提供している。

ix :: Ixed m => Index m -> Traversal' m (IxValue m)
-- ix :: k -> Traversal' (Map k a) a
-- ix :: Int -> Traversal' (Vector a) a

また、ここで紹介したpurelysmashisomorphicに相当するものだけでなく、traversalを構築および使用する手段が豊富に提供されている。

lensが扱っていない範囲でも、この考え方はプログラミングに役に立つ。計算結果をリストか何かで返そうと思ったとき、是非このスタイルも思い出してみてほしい。

出、出~~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

\displaystyle
\sum_{k=0}^{\infty} \frac{1}{a^k} (a \gt 1)
収束故、償却定数時間奴~~~~wwwwwwwww

取り出しも同様奴~wwwwwww

出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出~~~~wwwwwww

[63][20] → [41][40]

出出出出出出出出出出出出出出出出出出出出出出出出出出出出出~wwwwww

[40][12] → [26][26]

長ければ長いほど調整コスト相殺奴~~wwwwwwwwww

実装簡単、効率的データ構造奴~~~wwww

参考文献奴~wwwww

  • Chris Okasaki (1999). Purely Functional Data Structures