読者です 読者をやめる 読者になる 読者になる

きくらげ観察日記

好きなことを、適当に。

Data.Dataのgfoldlの型を読み解く

Data.Data.Data型クラスを使うと、Typeableと同様に非常に一般的な関数を書くことができるようになります。

前回のTypeableは値の型情報を取得するだけでしたが、Dataのメソッドを用いると代数的データ型の任意のフィールドにアクセスするといったようなことができるようになります。

また、DataもDeriveDataTypeable拡張を利用することにより、任意の型に対してderiveすることができるようになります。

まずはData型クラスの定義を見てみましょう。

>>> :i Data
class Typeable a => Data a where
  gfoldl ::
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a
  gunfold ::
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a
  toConstr :: a -> Constr
  dataTypeOf :: a -> DataType
  dataCast1 ::
    Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)
  dataCast2 ::
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)
  gmapT :: (forall b. Data b => b -> b) -> a -> a
  gmapQl ::
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r
  gmapQr ::
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r
  gmapQ :: (forall d. Data d => d -> u) -> a -> [u]
  gmapQi :: Int -> (forall d. Data d => d -> u) -> a -> u
  gmapM :: Monad m => (forall d. Data d => d -> m d) -> a -> m a
  gmapMp ::
    Control.Monad.MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a
  gmapMo ::
    Control.Monad.MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a
  	-- Defined in ‘Data.Data’

大量のメソッドが並んでいますが、キモはgfoldlとgunfoldの2つです。この2つさえ理解してしまえば残りは大したことありません。

foldlはリスト

[a0, a1, a2, ..., an]

に対し、次のような操作を提供するものです

zero `op` a0 `op` a1 `op` a2 `op` ... `op` an

この関数の一般化を考えてみます。一般の代数的データ型Aが以下のような値コンストラクタで定義されているとします

C x0 x1 x2 ... xn

これに対して、gfoldlでは、このA型の値に

(zero C) `op` x0 `op` x1 `op` x2 `op` ... `op` xn

という処理を行います。


gfoldlの型を見てみましょう

gfoldl
  :: Data a =>
     (forall d b. Data d => c (d -> b) -> d -> c b)
     -> (forall g. g -> c g) -> a -> c a

Rank2の多相型になっているため見た目は少々複雑ですが、先ほど説明した動作と照らしあわせて考えてみましょう。

まずは第二引数の型について考えてみましょう。

zero :: forall g. g -> c g

これは簡単です。値コンストラクタをApplicative的なものに包むだけの関数です。

次に、第一引数の型について考えてみます。

op :: forall d b. Data d => c (d -> b) -> d -> c b

第一引数は上での説明に出てきたopの部分に相当します。

C x0 x1 x2 ... xn

の各xiの型がバラバラである可能性がある以上、opは十分一般的な関数でなければなりません。引数の型についての制限は、dがDataのインスタンスであることだけです。しかし、Dataのインスタンスである型は、その型のすべてのフィールドの型がDataのインスタンスであることが要求されるため、これは問題ありません。

実際にopを適用させていった時、型がどのように変化していくか見てみましょう

(zero C)                 :: c (T0 -> T1 -> T2 -> ... -> Tn -> A)
(zero C) `op` x0         :: c (T1 -> T2 -> ... -> Tn -> A)
(zero C) `op` x0 `op` x1 :: C (T2 -> ... -> Tn -> A)
...
(zero C) `op` x0 `op` x1 `op` ... `op` x(n-1)         :: C (Tn -> A)
(zero C) `op` x0 `op` x1 `op` ... `op` x(n-1) `op` xn :: C A

この操作を続けていく中で、opは型

c (Ti -> T(i+1) -> ... -> Tn -> A)

にフィールドの値を適用し、

c (T(i+1) -> ... -> Tn -> A)

にしていることがわかります。
この

Ti

の部分がdに相当し、

T(i+1) -> ... -> Tn -> A

の部分がbに相当するのがお分かりでしょうか。

ここまで分かれば使うのは簡単です。実際に使ってみましょう。

data Person = Person {
    name :: String
  , age :: Int
  , isMale :: Bool
  } deriving (Eq, Show, Data, Typeable)

自前で定義したPerson型に対して、gfoldlを使ってみます。
一番簡単なのは、値コンストラクタに各フィールドの値を適用させていって元の値に戻すことです。

>>> gfoldl (\(Just con) field -> Just (con field)) Just $ Person "Tanaka" 18 False
Just (Person {name = "Tanaka", age = 18, isMale = False})

他にも、例えばn番目のフィールドの値を取得するといったこともgfoldlならできてしまいます。

get :: forall a t. Data t => Int -> t -> a
get n x = result
  where
    (result, _, _) = gfoldl step (\con -> (undefined, 0, con)) x
    step :: forall a d b. Data d => (a, Int, d -> b) -> d -> (a, Int, b)
    step (res, i, con) field
      | i == n = (unsafeCoerce field, i + 1, con field)
      | otherwise =  (res, i + 1, con field)

実行例:

>>> let yamada = Person { name = "Yamada", age = 18, isMale = False }
>>> get 0 yamada :: String
"Yamada"
>>> get 1 yamada :: Int
18
>>> get 2 yamada :: Bool
False

ただし、戻り地の型が不定である以上、この関数の扱いには注意が必要です。
間違った型を指定してしまった場合はエラーになるばかりか、最悪の場合コアダンプして死にます。

>>> get 0 yamada :: Int
1729382804966730138
>>> get 0 yamada :: IO ()
<interactive>: internal error: stg_ap_v_ret
    (GHC version 7.8.4 for x86_64_unknown_linux)
    Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug
中止 (コアダンプ)

この他にも、例えばフィールドの全型情報を取得するといったこともできます。

getTypes :: forall t. Data t => t -> [TypeRep]
getTypes x = types
  where
    (types, _) = gfoldl step (\con -> ([], con)) x
    step :: forall d b. Data d => ([TypeRep], d -> b) -> d -> ([TypeRep], b)
    step (ts, con) field = (ts ++ [typeOf field], con field)

実行例:

>>> getTypes yamada
[[Char],Int,Bool]

実は、これと同じようなことをするためのgmapQ関数というものが用意されています。

gmapQ :: Data a => (forall d. Data d => d -> u) -> a -> [u]
>>> gmapQ typeOf yamada
[[Char],Int,Bool]

この他にも用途毎にgmapT, gmapM, gmapMp等、様々なgfoldlの亜種が用意されています。このへんは適当に調べてみてください。

長くなったので続きはまた今度。次はgunfoldの型を読み解いていこうと思います。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!