PR

2個以上のリストを使う際の融合変換

 fold/buildには,1個のリストを使う場合しか考慮されていないという制限があります。先に見たように,build関数は「(a -> b -> b) -> b -> b」型の関数gだけを引数として取るように定義されています。つまり,buildはあくまで1個のリストを作成するためだけのものであり,「++」を使って2個のリストをつなぎ合わせる場合は考慮されていません(参考リンク1参考リンク2)。

build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
~ 略 ~
build g = g (:) []

 「xs ++ ys」のような式でリストを作成した場合,fold/buildによる融合変換はxsだけが対象になってしまいます。

 この問題を解決するためにGHC.Extsが提供しているのが「foldr/augment」です。この手法では,三つのリスト,すなわちxs,ys,「式『xs ++ ys』の結果として作成されるリスト」のすべてを融合変換の対象として扱えるように,augment関数と"foldr/augment"規則を使います。

augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
{-# INLINE [1] augment #-}
augment g xs = g (:) xs
{-# RULES
~ 略 ~
"foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) . 
                foldr k z (augment g xs) = g k (foldr k z xs)
~ 略 ~
"augment/build" forall (g::forall b. (a->b->b) -> b -> b)
                       (h::forall b. (a->b->b) -> b -> b) .
                       augment g (build h) = build (\c n -> g c (h c n))
"augment/nil"   forall (g::forall b. (a->b->b) -> b -> b) .
                        augment g [] = build g
 #-}

 ++演算子は,書き換え規則によってaugmentを使った形に変換されます。

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys
{-# RULES
"++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
  #-}

 次に,augmentを使った式に"foldr/augment"規則を適用することで,xsを融合変換すると同時に,"fold/build"規則を適用できる状態にysを変換します。ysの生成にbuildが使われているため,最終的に"fold/build"規則が適用されてxs,ys,「xs ++ ys」の結果として作成されるリストのすべてに対して融合変換が行われるのです。

 なお,「xs ++ ys」のysが空リストである場合には,"augment/nil"規則を使ってaugmentをbuildに変換します。

destroy/unfoldrを使った融合変換

 Data.Listモジュールは,foldrと双対の関係にある関数としてunfoldrを提供しています。unfoldrは,foldrとは逆にリストを作成するための関数です(参考リンク)。

-- A simple use of unfoldr:
--
-- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
-- >  [10,9,8,7,6,5,4,3,2,1]
--
unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b  =
  case f b of
   Just (a,new_b) -> a : unfoldr f new_b
   Nothing        -> []

 foldrで使用する関数fとunfoldrで使用する関数f'の間に以下の条件が成り立つ場合には,unfoldrはfoldrによる処理を取り消すことができます。

f' (f x y) = Just (x,y)
  f' z       = Nothing

unfoldr f' (foldr f z xs) == xs

 さて,foldrで定義された「リストを使用する関数」では,fold/buildという融合変換の手法が利用できました。同様に,unfoldrで定義された「リストを作成する関数」では,「destroy/unfoldr」という融合変換の手法が利用できます。

 destroy/unfoldrでは,リストを使用する関数を定義するためにdestory関数を利用します。

destroy :: (forall b. (b -> Maybe (a,b)) -> b -> c) -> [a] -> c
destroy g = g psi
  where psi :: [a] -> Maybe (a,[a])
        psi []     = Nothing
        psi (x:xs) = Just (x,xs)

 「unfoldrを使ってリストを作成し,destroyを使ってリストを使用する処理」を書き換えて中間データ構造を除去するには,以下の"destroy/unfoldr"規則を使います。

{-# RULES
"destroy/unfoldr"    forall psi e (g::forall b. (b -> Maybe (a,b)) -> b -> c) . 
                     destroy g (unfoldr psi e) = g psi e
 #-}

 "destroy/unfoldr"規則では,"fold/build"規則と同様に,destroyとunfoldrを使わない処理への書き換えが行われます。この結果,リストの様々な処理に対する中間データ構造が除去されるのです。

 "destroy/unfoldr"規則の利点は,zipやzipWithのように複数のリストを使う関数を融合変換できることです。一方で,この規則には,規則を適用する前と適用した後でプログラムの意味が変わったり,規則の適用後に値を共有できなくなったりするといった欠点があります(参考リンク1参考リンク2)。このため,destroy/unfoldrはGHCのライブラリ実装には使われていません。

 今のところは「destroy/unfoldrという手法もある」という程度の理解で十分でしょう。


著者紹介 shelarcy

 2009年12月14日にGHC 6.12.1がリリースされました。日本語を使ったテキストの入出力に対応しているなど,魅力的な点がいろいろあるのですが,残念ながら今回からGHCはユーザー向けのリリースという位置付けではなくなりました。一般のユーザーは,近々リリースされる予定のHaskell Platformを使ってほしいとのことです。

 Haskell Platformには,cabalコマンド(パッケージ名からcabal-installともいう)などのツールが標準で付属しています。Haskell Platformの新しいバージョンが出たら,cabalコマンドについても説明したいと思っています。