処理が遅延されないfold関数

 repaでは,畳み込みを行うfold関数も用意されています。並列処理版のfoldP関数と逐次処理版のfoldS関数があります。先に説明したように,foldP関数は値をモナドに包んで返します。

foldS   :: (Shape sh, Elt a, Unbox a, Repr r a)
        => (a -> a -> a)
        -> a
        -> Array r (sh :. Int) a
        -> Array U sh a
~ 略 ~

foldP   
        :: (Shape sh, Elt a, Unbox a, Repr r a, Monad m)
        => (a -> a -> a)
        -> a
        -> Array r (sh :. Int) a
        -> m (Array U sh a)
~ 略 ~

 foldS関数やfoldP関数では処理は遅延されません。

Prelude Data.Array.Repa> :t foldS
foldS
  :: (Shape sh, Repr r a, Data.Vector.Unboxed.Base.Unbox a,
      repa-3.1.4.2:Data.Array.Repa.Eval.Elt.Elt a) =>
     (a -> a -> a) -> a -> Array r (sh :. Int) a -> Array U sh a
Prelude Data.Array.Repa> :t foldP
foldP
  :: (Monad m, Shape sh, Repr r a, Data.Vector.Unboxed.Base.Unbox a,
      repa-3.1.4.2:Data.Array.Repa.Eval.Elt.Elt a) =>
     (a -> a -> a) -> a -> Array r (sh :. Int) a -> m (Array U sh a)

 foldS関数とfoldP関数は,「Array r (sh :. Int) a」型の値を引数として取り,内部の次元を畳み込んで次元を一つ減らした「Array U sh a」型の値を返します。

Prelude Data.Array.Repa> foldS (+) 0 $ fromListUnboxed (ix2 3 3) [1..9]
AUnboxed (Z :. 3) (fromList [6.0,15.0,24.0])
Prelude Data.Array.Repa> foldP (+) 0 $ fromListUnboxed (ix2 3 3) [1..9]
AUnboxed (Z :. 3) (fromList [6.0,15.0,24.0])
foldP (*) 1 $ fromListUnboxed (ix3 2 3 4) [1..24]
AUnboxed ((Z :. 2) :. 3) (fromList [24.0,1680.0,11880.0,43680.0,116280.0,255024.0]
Prelude Data.Array.Repa> foldP (*) 1 $ fromListUnboxed (ix3 2 3 4) [1..24]
AUnboxed ((Z :. 2) :. 3) (fromList [24.0,1680.0,11880.0,43680.0,116280.0,255024.0])

 返す値には,行列の次元以外にもう一つ注目すべき点があります。それは,引数として渡した配列と同じ型の配列ではなく,必ずU型の配列を結果として返すということです。

 先に説明したように,U型の配列の内部表現には,非ボックス化Vectorという実データが使われています。

-- | Unboxed arrays are represented as unboxed vectors.
--
--   The implementation uses @Data.Vector.Unboxed@ which is based on type
--   families and picks an efficient, specialised representation for every
--   element type. In particular, unboxed vectors of pairs are represented
--   as pairs of unboxed vectors.
--   This is the most efficient representation for numerical data.
--
data U
data instance U.Unbox e => Array U sh e
        = AUnboxed sh !(U.Vector e)

 非ボックス化Vectorは,第19回で説明した非ボックス化配列のVector版です。非ボックス化配列と同様に,非ボックス化Vectorでは,ボックス化されていない生のマシン表現を配列に格納します。したがって,foldS関数やfoldP関数で行う評価は遅延されず,必ず評価されてから格納されるのです。

 foldS関数とfoldP関数は内部の次元を畳み込む関数ですが,配列に格納された要素全体を畳み込んだスカラー値が欲しい場合もあります。しかし,foldS関数やfoldP関数を繰り返し適用して一つずつ次元を減らしたり,いったんリストやVectorなどに戻してから計算するのは,あまり筋が良い方法ではありません。これらの方法では,配列からスカラー値に変換するまでに必要な処理の間で何度か中間データ構造を作成することになるからです。中間データ構造の作成は,処理の性能を下げてしまうので,できる限り避けるべきです。

 そこでrepaでは,配列に格納された要素全体を畳み込んでスカラー値を返すfoldAllS関数やfodlAllP関数が提供されています。

Prelude Data.Array.Repa> :t foldAllS
foldAllS
  :: (Shape sh, Repr r a, Data.Vector.Unboxed.Base.Unbox a,
      repa-3.1.4.2:Data.Array.Repa.Eval.Elt.Elt a) =>
     (a -> a -> a) -> a -> Array r sh a -> a
Prelude Data.Array.Repa> :t foldAllP
foldAllP
  :: (Monad m, Shape sh, Repr r a, Data.Vector.Unboxed.Base.Unbox a,
      repa-3.1.4.2:Data.Array.Repa.Eval.Elt.Elt a) =>
     (a -> a -> a) -> a -> Array r sh a -> m a

Prelude Data.Array.Repa> foldAllS (+) 0 $ fromListUnboxed (ix2 3 3) [1..9]
45.0
Prelude Data.Array.Repa> foldAllP (+) 0 $ fromListUnboxed (ix2 3 3) [1..9]
45.0
Prelude Data.Array.Repa> foldAllS (*) 1 $ fromListUnboxed (ix2 3 3) [1..9]
362880.0
Prelude Data.Array.Repa> foldAllP (*) 1 $ fromListUnboxed (ix2 3 3) [1..9]
362880.0
Prelude Data.Array.Repa> foldAllS (+) 0 $ fromListUnboxed (ix3 2 3 4) [1..24]
300.0
Prelude Data.Array.Repa> foldAllP (+) 0 $ fromListUnboxed (ix3 2 3 4) [1..24]
300.0

 foldAllS関数とfoldAllP関数が返す値は配列ではありませんが,領域漏れ(スペース・リーク)の問題を防ぐために正格評価を内部的に利用しています(参考リンク1参考リンク2)。

 このように,repaが提供する畳み込み関数は,いずれも処理を遅延せずに即座に評価を行うよう定義されています。

 畳み込み関数の場合には,並列処理版の関数と逐次処理版の2種類の関数が用意されているのは,性能上の理由からだけではありません。もう一つ切実な理由があります。

 畳み込み関数を使った処理は,いつも並列化できるとは限りません。畳み込み関数で使う「a -> a -> a」型の関数が結合法則を満たすなら,配列内の各要素の対する処理をどの順番で行っても必ず同じ結果になります。この場合は「処理を複数に分割し,複数に分割されたそれぞれの処理を並列に行い,その結果をまとめる」というように定義された並列処理版の畳み込み関数を使っても問題はありません。

 ところが,「a -> a -> a」型の関数が結合法則を満たさない場合には,問題が起こります。結果が処理の順序に依存するため,並列処理版の畳み込み関数を使うと,予想外の結果になってしまうのです。例えば,並列化された畳み込み関数で引き算や割り算を使うと,処理をどのように分割して処理するかによって異なる結果になってしまいます。

import Data.Array.Repa

main = do
    let xs = fromListUnboxed (ix3 2 3 4) [(1::Double)..24]
    x <- foldAllP (-) 0 xs
    print x
    y <- foldAllP (/) 1 xs
    print y

$ ghc FoldP.hs -O2 -threaded
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking FoldP ...

$ ./FoldP
-12.0
0.16118025779724124

$ ./FoldP +RTS -N5
-44.0
2.812375282545737e-4

$ ./FoldP +RTS -N8
-100.0
1.4959919329038283e-8

 この例では,処理をすべて1個のCPUコア上で行った場合,5個のCPUコアに分割して並列処理した場合,8個のコアに分割して並列処理した場合で,それぞれ異なる結果になっているのがわかりますね。

 このように,「a -> a -> a」型の関数が結合法則を満たさない場合には,foldPやfoldAllPのような並列化した畳み込み関数を使った処理の結果は不定になります。並列化した畳み込み関数を安全に使うことができるのは,畳み込み関数に渡す「a -> a -> a」型の関数が結合法則を満たす場合だけです(参考リンク)。

 foldPやfoldAllPで利用する関数が常に結合法則を満たすよう型を使って制限できればよいのですが,現在のHaskellの型システムでは,そのような制限を適切な形で与えることはできません。

 一つの方法としては,FoldableクラスのfoldMapメソッドのように,foldP関数やfoldAllP関数の型にMonoidクラスのインスタンスという制約をつけ,常にmappend関数を使って処理を行うようにして,結合法則を満たさない計算を取り除くことが考えられます。しかし,これでは結合法則を満たす既存の「a -> a -> a」型の関数まで使えなくなります。また,repaは並列処理のためのライブラリなので,Monoidクラスのインスタンスを使うよう定義されたfoldPやfoldAllPとMonoidクラスのインスタンスを組み合わせると速度面の不安も残ります。少なくとも現時点では,Monoidクラスのインスタンスを利用するのは十分な解決策ではありません。

 今のところは,foldPやfoldP関数を使う場合には,結合法則を満たす処理を使っているかどうかをプログラマ自身が検証する必要があります。