第52回　データ構造を走査するためのTraversableクラス

2012.02.08

sheやDeriveXでTraversableクラスのインスタンスを楽に定義

　TraversableクラスはFunctorクラスやFoldableクラスのサブクラスであるため，Traversableクラスのインスタンスを定義する場合にはFunctorクラスやFoldableクラスのインスタンスも定義しなければなりません。

module Tree where
import Control.Applicative (pure, (<$>), (<*>))
import Data.Foldable (Foldable(..))
import Data.Traversable

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
            deriving Show

instance Traversable Tree where
    traverse f Empty = pure Empty
    traverse f (Leaf x) = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

instance Functor Tree where
    fmap = fmapDefault

instance Foldable Tree where
    foldMap = foldMapDefault

　fmapDefault関数やfoldMapDefault関数があるとはいえ，このようにいちいちインスタンスを書くのは面倒です。

　そこで利用できるのが，前回のコラムで説明した「スーパークラスに対してインスタンスを定義する機能」を提供する「she」です。sheでは組み込みの定義として「スーパークラスに対してインスタンスを定義する機能」を使ったFunctorクラスやFoldableクラスのインスタンスが提供されています。sheをプリプロセサとして利用すれば，FunctorクラスやFoldableクラスのインスタンスの定義を省略できます。

　sheを利用するプログラムは以下のように記述します。

{-# OPTIONS_GHC -F -pgmF she #-}
module Tree where
import Control.Applicative (pure, (<$>), (<*>))
import Data.Foldable (Foldable(..))
import Data.Traversable

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
            deriving Show

instance Traversable Tree where
    traverse f Empty = pure Empty
    traverse f (Leaf x) = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

　OPTIONS_GHC指示文で与えている-Fオプションは，プリプロセサを使用することを示します。-pgmFオプションでは，-Fオプションのもとで実際に利用するプリプロセサを指定します。つまり「-F -pgmF she」と指定することで，sheを使った前処理が行われます（参考リンク）。では，このコードにTree.hsというファイル名を付け，GHCiに渡してみましょう。

$ ghci Tree.hs
GHCi, version 7.0.4: http://www.haskell.org/ghc/  :? for help
～ 略 ～
Tree.hs
Tree.hs
/var/folders/zs/bsr11y_x3d76ssg4bl_kx7nm0000gn/T/ghc15318_0/ghc15318_0.hspp
[1 of 1] Compiling Tree             ( Tree.hs, interpreted )
Ok, modules loaded: Tree.
*Tree>

　表示されている「Tree.hs」「Tree.hs」「*.hspp」は，それぞれ，プログラムのソースコードとして読み込んだオリジナルのファイル名，プリプロセサで処理されるファイル名，プリプロセサで処理した結果として一時的に生成される中間ファイル名です（参考リンク1，参考リンク2，参考リンク3）。Tree.hsではsheで前処理を行う前には特別な処理を行っていないので，オリジナルのファイル名である「Tree.hs」が2回出力されています。なお，これらのファイル名の表示はsheが行っているものです。別のプリプロセサでは，このようなファイル名の表示が行われないこともあります。

　では，sheを使って生成されたFunctorクラスやFoldableクラスを使ってみましょう。

*Tree> fmap (+1) Empty
Empty
*Tree> fmap (+1) (Leaf 22)
Leaf 23
*Tree> fmap (+1) (Node (Leaf 23) 11 (Empty))
Node (Leaf 24) 12 Empty
*Tree> Data.Foldable.foldl (+) 1 Empty
1
*Tree> Data.Foldable.foldl (+) 1 (Leaf 22)
23
*Tree> Data.Foldable.foldl (+) 1 (Node (Leaf 23) 11 (Empty))
35

　FunctorクラスのfmapメソッドやFoldableクラスのfoldlメソッドが問題なく利用できているのがわかります。このように，sheを使うことでTraversableクラスのインスタンスからFunctorクラスやFoldableクラスのインスタンスの定義を生成できます。

　sheでは，FunctorクラスやFoldableクラスのインスタンスを定義するには，Traversableクラスのインスタンスの定義が必要です。しかし，Traversableクラスのインスタンスが定型的に定義できる場合には，Traversableクラスのインスタンスの定義自体を省略したくなります。このような場合には，sheではなくGHCの言語拡張である「DeriveX」（Xは型クラス名）を利用します。

　FunctorクラスやFoldableクラス，Traversableクラスのインスタンスで与えられるメソッドの定義は，一般には「データ型を表現する木を走査し，関数を適用していく」という定型になります。GHCでは，DeriveXを利用してFunctorクラスやFoldableクラス，Traversableクラスを導出インスタンス宣言の対象にすることで，定型のインスタンス定義を自動導出できます（参考リンク）。

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
module Tree where
import Data.Foldable (Foldable(..))
import Data.Traversable (Traversable(..))

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
            deriving (Show, Functor, Foldable, Traversable)

　sheの「スーパークラスに対してインスタンスを定義する機能」とは異なり，DeriveXはTraversableクラスのインスタンスに依存しない独立した機能として定義されています。このため，Traversableクラスのインスタンスを定義しなくても，FunctorクラスやFoldlabeクラスのインスタンスを定義できるのです。逆にいえば，Traversableクラスのインスタンスを定義しても，このインスタンスの定義を使ってFunctorクラスやFoldableクラスの定義が生成されるわけではありません。

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
module Tree where
import Data.Foldable (Foldable(..))

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
            deriving (Show, Functor, Foldable)

　ただし，導出インスタンス宣言の対象にできるのは，モジュールのスコープ内のクラスに限られます。対象になるクラスがインポートされていない場合にはエラーになるので注意してください。

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
module Tree where
import Data.Foldable (Foldable(..))

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
            deriving (Show, Functor, Foldable, Traversable)

$ ghci Tree.hs
GHCi, version 7.0.4: http://www.haskell.org/ghc/  :? for help
～ 略 ～
[1 of 1] Compiling Tree             ( Tree.hs, interpreted )

Tree.hs:6:48: Not in scope: type constructor or class `Traversable'
Failed, modules loaded: none.
Prelude>

　DeriveXを使えばTraversableクラスのインスタンスの定義さえも省略できます。ですが，DeriveXがあればsheは要らないというわけではありません。

　FunctorクラスやFoldableクラス，Traversableクラス，それぞれのインスタンスのメソッドに対して，「配列のように組み込みのデータ構造として定義する必要がある」「効率的に扱うために特別な処理が必要である」「Applicativeやモナドとしても利用するので特別な意味が必要である」といった特別な理由があれば，DeriveXが自動導出する定型のインスタンスに頼ることはできません。必要に応じて特別なインスタンスの定義を用意する必要があります。

　このとき，FunctorクラスとFoldableクラス，Traversableクラスすべてに対して，fmapDefaultやfoldMapDefaultも使わない特別なインスタンスが必要であれば，DeriveXだけでなくsheも利用できません。しかし，Traversableを含む一部のクラスに特別なインスタンスを定義すれば，残りのインスタンスはfmapDefaultやfoldMapDefaultを使った定義でも十分な場合もあります。このような場合には，fmapDefaultやfoldMapDefaultを使ったインスタンスの定義をsheで生成できます。

　このようなsheとDeriveXの特性を理解して，必要に応じて使い分けてください。

著者紹介 shelarcy

　2011年12月にインターネット上で開催された「Haskell Advent Calendar 2011」というイベントの企画記事の一つとして「GHC 7.4.1 時代の日本語文字列の扱い」という記事を書きました。「Haskell Advent Calendar 2011」で書かれた記事は，私の記事を含め，まとめて技術評論社の電子出版サービス「Gihyo Digital Publishing」で無料の電子書籍として出版される予定です（参考リンク）。ぜひ読んでみてください。