Edited at

RankNTypes と型レベルリストと extensible


モチベーション

こんな関数を定義したことありませんか?


今回の話の出発点

showArgs :: Int -> Bool -> Maybe Char -> [String]

showArgs a b c = [ show a, show b, show c ]

この showArgs 関数は正しく動作します。


showArgs関数の実行例

> showArgs 3 True (Just 'a')

["3","True","Just 'a'"]

さて、今回の話はこの showArgs をより一般化したい。

つまり、


  • 引数の型が全て異なっても動いて欲しい


  • show をリストの中に埋め込みたく無い

  • 1つの関数定義で任意長の引数を扱えるようにしたい

ということです。

この例を通して RankNTypes, 型レベルリスト, extensible package への道を作りたいと思います。


道のり1. タプル

まず、リストは同じ型の値しかリストに入れることができないので、複数の異なる型の値を1つの値として扱うことができるタプルを利用してみましょう。


タプルを使って再定義

showArgsTuple :: (Int, Bool, Maybe Char) -> (String, String, String)

showArgsTuple (a,b,c) = (show a, show b, show c)


showArgsTupleの実行例

> showArgsTuple (3, True, Just 'a')

("3","True","Just 'a'")

ここまでは順調です。あとはタプルの各要素に show 関数を適用する何かを定義するだけです。

すぐに思いつくのは Functor 型クラスの fmap ですが、これは上手くいきません。


インスタンス定義が無いと言われてエラーになる

> :set -XFlexibleContexts

> fmap show (1,True,Just 'a')
No instance for (Functor ((,,) Integer Bool))

インスタンス定義が無いなら自分で定義すれば良いですね。


3要素タプルのFunctor定義

instance Functor ((,,) a b) where

fmap :: (c -> d) -> (a,b,c) -> (a,b,d)
fmap f (a,b,c) = (a,b,f c)

しかし、定義してみるとわかりますが、最後の要素にしか f は適用できないのです・・・。fmap :: (a -> b) -> f a -> f b なので当然といえば当然です・・・。)


3要素のタプルにfmapしてみる例

> fmap show (1,True,Just 'a')

(1,True,"Just 'a'")

今欲しい結果は (a, b, f c) ではなく (f a, f b, f c) なので、これでは失敗です!

Functor の力を借りることができないので、自分で新しく関数を定義することにしましょう。


道のり2. mapTuple3 を自分で定義してみる

まずは1引数の関数に限定して考えることにします。


badMapTuple3(失敗)

badMapTuple3 :: (a -> r) -> (a,b,c) -> (r, r, r)

badMapTuple3 f (a,b,c) = (f a, f b, f c)

素朴に考えたらこんな感じの定義になるのではないでしょうか。

しかし、これはコンパイルに失敗します・・・。


コンパイルエラー

Couldn't match expected type a with actual type b

Couldn't match expected type a with actual type c

なぜコンパイルに失敗するかと言うと型 a は以下のように束縛されているからです。


明示的にforallを書いた(b,cは省略)

badMapTuple3 :: forall a . (a -> r) -> (a,b,c) -> (r, r, r)


もし aInt だったなら以下のようになります。


aがIntの場合

badMapTuple3 ::(Int -> r) -> (Int,b,c) -> (r, r, r)


これで f a は適用できるけども f b, f c が不可能だと言うことがわかりました。


道のり3. RankNTypes

badMapTuple3 の問題は forall の位置にあります。この問題を解決するためには、どんな型の引数でも動作するような総称的な関数を引数に取れば良いのです。(つまり、これは型クラスのメソッドです)

先に正しく動作する goodMapTuple3 を定義して比較してみましょう。定義するためには RankNTypes が必要です。


forallの位置の違い

badMapTuple3  :: forall a . (a -> r) -> (a,b,c) -> (r, r, r)

badMapTuple3 f (a,b,c) = (f a, f b, f c)

goodMapTuple3 :: (forall a. a -> r) -> (a,b,c) -> (r, r, r)
goodMapTuple3 f (a,b,c) = (f a, f b, f c)


実装は全く同じですが、goodMapTuple3 では forall が型の第一引数の関数の中にあります。

つまり、どんな型の値が来ても r の型の値を返す関数ということです。


gはどんな型が来てもr型の値を返す関数

g :: Int -> r

g :: Char -> r
g :: Maybe Int -> r
g :: [a] -> r
...

具体例をいくつか考えてみましょう。


goodMapTuple3に与える関数gの具体例

-- const 1 はどんな値が来ても常に1を返す関数

> goodMapTuple3 (const 1) (1,True,Just 'a')
(1,1,1)

いくつか考えようと思いましたが、意外と思いつきません。つまり、適用範囲が広い分、言えること (できること) が少ないんです。forallすべての と言う意味なので、すべての型の値について正しく動作する必要があるのです。


道のり4. 制約 (Constraint) を追加する

forall は扱える範囲は広いけど、具体的に何か処理を行おうとすると少し不便です。そのため、forall に制約を加えます。

ここでいう制約と言うのは、新しいものではなく、Haskell で必ず学習する型クラス制約のことです。具体的に言えば Eq, Show, Num, Monad などたくさんあります!

ようするに、forall (すべて) では対象が広すぎ、具体的な型では対象が狭すぎるため、型クラス制約を満たす型という感じで限定するんです。雰囲気こんな感じです。

typerange.png

今回は Show について考えていたので、Show 型クラス制約を用いて goodMapTuple3 を書き直してみましょう。


制約を追加したmapTuple3

mapTuple3 :: (Show a, Show b, Show c) => (forall x. Show x => x -> r) -> (a,b,c) -> (r, r, r)

mapTuple3 f (a,b,c) = (f a, f b, f c)

一番重要なのは forall x. Show x => の部分です、ここで関数が動作する型の範囲を限定しています。


mapTuple3の実行例

> mapTuple3 show (1,True,Just 'a')

("1","True","Just 'a'")

素晴らしいですね!これで


  • 引数の型が全て異なっても動いて欲しい


  • show をリストの中に埋め込みたく無い

  • 1つの関数定義で任意長の引数を扱えるようにしたい

の1つ目と2つ目を達成することができました!

鋭い方はお気づきかもしれませんが、mapTuple3 は関数の型に Show が埋め込まれているため任意の制約については扱うことができません。(extensible を使えば簡単に作ることができます)


ここまでのまとめ

-- オリジナル

showArgs :: Int -> Bool -> Maybe Char -> [String]
showArgs a b c = [ show a, show b, show c ]

-- タプルバージョン
mapTuple3 :: (Show a, Show b, Show c) => (forall x. Show x => x -> r) -> (a,b,c) -> (r, r, r)
mapTuple3 f (a,b,c) = (f a, f b, f c)

showArgs :: Int -> Bool -> Maybe Char -> [String]
showArgs a b c = mapTuple3 show (a,b,c)


少し良くなった感じがします。あとはこの関数を任意長の引数に拡張するだけです。


道のり5. 型レベルリスト (任意長引数への拡張)

タプルで全てが解決すると思うかもしれませんが、これは上手くいきません。なぜなら、タプルはリストとは違い固定長のデータ構造だからです。

タプルのようなリストが作れたら良いのに・・・。できます!それが、型レベルリストです。

まずは、extensible パッケージが提供している型レベルリストを使って値を作ってみましょう。(DataKindsTypeOperators が必要です)


extensibleパッケージの型レベルリストの定義

data HList (h :: k -> *) (xs :: [k]) where

HNil :: HList h '[]
HCons :: h x -> HList h xs -> HList h (x ': xs)


HListを使って実際に型レベルリストの値を作ってみる

{-# LANGUAGE DataKinds #-}

{-# LANGUAGE TypeOperators #-}
import Data.Extensible.HList

-- []
x0 :: HList Identity '[]
x0 = HNil

-- 'a' : []
x1 :: HList Identity (Maybe Char ': '[])
x1 = HCons (Identity (Just 'a')) x0

-- True : 'a' : []
x2 :: HList Identity (Bool ': Maybe Char ': '[])
x2 = HCons (Identity True) x1

-- 3 : True : 'a' : []
x3 :: HList Identity (Int ': Bool ': Maybe Char ': '[])
x3 = HCons (Identity 3) x2


こんな感じで型レベルリストを定義できます。(HList の H は Heterogeneous の H です。異なるのような意味があるそうです。)

次に定義した型レベルリストを使って何か適当な処理を行なってみたいですね。extensible が提供していてすぐに使えそうなのは hlengthhfoldrWithIndex でしょうか。


hlengthとhfoldrWithIndexの型

hlength :: HList h xs -> Int

hfoldrWithIndex :: forall h r xs. (forall x. Membership xs x -> h x -> r -> r) -> r -> HList h xs -> r

hlength は型レベルリストの長さを計算する関数です。これは直感的に使えますね。


hlengthの具体例

> hlength x3

3
> hlength x2
2
> hlength x1
1
> hlength x0
0

次に hfoldrWithIndex です。


hfoldrWithIndexを使った関数

example :: [Int]

example = hfoldrWithIndex go [] x3
where
go _m x xs = const 1 (runIdentity x) : xs

まず型を整理しておきます。


型の整理

go :: (forall x. Membership (Int ': Bool ': Maybe Char ': '[]) x -> Identity x -> r -> r)

_m :: Membership xs x -- 現在の要素の型とリストの何番目かの位置
x :: Identity x -- x は型レベルリストの要素の型によって変化
xs :: r -- foldr で畳み込まれた値

x :: Identity x なので runIdentity :: Identity a -> a を適用することで具体的な要素に触れることができます。(今回の例では意味無いです)

今回は hIdentity を選びましたが、仮に Maybe だった場合、 xx :: Maybe x 型の値になります。


exampleの実行結果

> example

[1,1,1]

全然面白く無い例ではありますが、これで型レベルリストに対して何かしらの処理を適用できるようになりました。つまり、これで任意長の引数を扱えるようになったということです!

ただ、残る問題は hfoldrWithIndex の第一引数の関数の型です。

-- hfoldrWithIndex

(forall x. Membership xs x -> h x -> r -> r)

-- 期待する形 (制約を追加したい)
(forall x. Show => Membership xs x -> h x -> r -> r)

hfoldrWithIndexShow => というように制約を追加することができません。

最後に extensible の力を借りてこの問題を解決してみましょう。


道のり6. extensible のすすめ

extensible 利用者は HList をそのまま使わずに積 (Product) の形に変換してから、処理を行うことが大半です。積はタプルの一般形であり、Haskell のレコード構文を拡張したものと考えることもできます。(詳しくは TAPL を読んでみてください)

HList から Product へ変換する関数は fromHList です。


fromHList

fromHList :: HList h xs -> h :* xs


実際に積に変換してみましょう。


型レベルリストから積への変換

p :: Identity :* (Int ': Bool ': Maybe Char ': '[])

p = fromHList x3

積は Show クラスのインスタンスになっているので普通に値を見ることができます。


積の形

> p

Identity 3 <: Identity True <: Identity (Just 'a') <: nil

-- (<:) = (:), nil = [] と見ればリストっぽいですね。


さて、最後の仕上げに先ほどの hfoldrWithIndex の制約バージョン hfoldrWithIndexFor を使うことにしましょう。(この例では TypeApplications が必要です)


hfoldrWithIndexForを使って再定義

example :: [String]

example = hfoldrWithIndexFor c go [] p
where
c = Proxy @Show
go _ x xs = show (runIdentity x) : xs

制約は Proxy :: Proxy Show のように型経由で渡します。ここでは c = Proxy @Show のようにしています。あとは、本当に型レベルリストを畳み込んでいるだけです。


exampleの実行結果

> example

["3","True","Just 'a'"]

できました!!!

おまけ


積を簡単に作る方法

-- helper

infixr 0 <::
(<::) :: Wrapper h => Repr h x -> h :* xs -> h :* (x ': xs)
(<::) = (<:) . review _Wrapper

p' :: Identity :* (Int ': Bool ': Maybe Char ': '[])
p' = 3 <:: True <:: Just 'a' <:: nil


(<::) 演算子は (=<:) として extensible に実装されました。


完成形

最後に任意の型レベルリストを処理できるように拡張してみます。(FlexibleContexts を追加する必要があります)


showArgsHListの定義

showArgsHList :: Forall Show xs => Identity :* xs -> [String]

showArgsHList = hfoldrWithIndexFor c go []
where
c = Proxy @Show
go _ x xs = show (runIdentity x) : xs

Forall Show xs => を制約に追加しました。これは型レベルリストの全て (Forall) の型が Show クラスのインスタンスであることを制約に追加しています。


showArgsHListの実行例

> showArgsHList (3 <:: True <:: Just 'a' <:: nil)

["3","True","Just 'a'"]

> showArgsHList (Right 5 <:: 3 <:: True <:: Just 'a' <:: nil)
["Right 5","3","True","Just 'a'"]

> showArgsHList (True <:: Just 'a' <:: nil)
["True","Just 'a'"]


どうですか!?これで当初の目標が全て達成できました!


  • 引数の型が全て異なっても動いて欲しい


  • show をリストの中に埋め込みたく無い

  • 1つの関数定義で任意長の引数を扱えるようにしたい


まとめ



  • RankNTypes, 型レベルリスト, extensible までの道のりを一歩一歩進んでみました。

  • この例を通して extensible パッケージやカインドに興味をもってもらえたら嬉しいです。

  • extensible パッケージはもっと凄い機能がたくさんあるんだよ!