前回は、行列演算を定義する方法を説明しました。行列演算は、traverse関数やfromFunction関数を使って、「行列を変換する処理」と「個々の要素を求める処理」を組み合わせることで定義できます。同様に、「ステンシルを使って配列の中の隣接要素を取り出す処理」と「取り出した各要素を畳み込む処理」を組み合わせると、信号処理のフィルタなどを記述できます(参考リンク)。この処理を、ステンシル畳み込み(Stencil Convolution)といいます。ステンシルとは「型板」という意味です。

transpose関数で隣接要素を参照

 前回説明したtranspose関数では、traverse関数を使って「行列の形状を変更し、変更された行列の形状に応じて参照先を変換する」という処理を行っていました。同様に、traverse関数を使って参照先を変換すれば、元の参照先とは別の場所にある要素を参照できます。

 traverse関数の基本的な使い方を振り返っておきましょう。traverse関数が第3引数として取るのは、「(sh -> a) -> sh' -> b」という型の「新しい行列の形状sh'に合わせて参照先を書き換える関数」です。

-- | Unstructured traversal.
traverse
        :: forall r sh sh' a b
           ( Source r a
           , Shape sh, Shape sh')
        => Array r sh a                 -- ^ Source array.
        -> (sh  -> sh')                 -- ^ Function to produce the extent of the result.
        -> ((sh -> a) -> sh' -> b)      -- ^ Function to produce elements of the result.
                                        --   It is passed a lookup function to get elements of the source.
        -> Array D sh' b

traverse arr transExtent newElem
 = fromFunction (transExtent (extent arr)) (newElem (index arr))

 「(sh -> a) -> sh' -> b」という型で説明すると複雑になるので、traverse関数の第2引数としてid関数を渡すと仮定します。この場合、第3引数の関数の型は「(sh -> a) -> sh -> b」になります。

 「(sh -> a) -> sh -> b」型の関数は、第1引数として「行列の形状shの型の値を取って参照先のa型の値を返す関数」、第2引数として「配列の要素の参照に利用する行列の形状sh型の値」を取ります。このうち、第1引数である「行列の形状shの型の値を取って参照先のa型の値を返す関数」は、traverse関数によって渡された「index arr」です。第2引数は、traverse関数を使って作成するD型の配列の要素を、index関数などを使って実際に参照する際に渡される値です。ここでは行列の形状を変換しないので、「(sh -> a) -> sh -> b」型の関数を「\get sh -> get sh」と記述すれば、この関数の第1引数のgetを使ってこの関数の第2引数のshの要素を参照できます。

 このとき、参照先を書き換えれば、現在の参照先の要素ではなく別の場所にある要素を参照できます。例えば、「(sh -> a) -> sh -> b」型の関数を「\get (Z :. i :. j) -> get (Z :. (i-1) :. (j-1))」と記述すれば、この関数の第2引数として与えられる「Z :. i :. j」の指す「i行j列目」ではなく「i-1行j-1列目」の要素を参照できます。

 また、複数の個所の要素を参照する処理を、「(sh -> a) -> sh -> b」型の関数としてtraverse関数の第3引数として渡すこともできます。例えば、ライフゲームで死を0、生を1としたときに、隣接する要素の合計、すなわち隣接する生きたセルの数を求める処理は、以下のような形になります(参考リンク)。

sumAround arr = traverse arr id sumAround'

sumAround' get (Z :. i :. j)
    = get (Z :. (i-1) :. (j-1))
    + get (Z :. (i-1) :. j)
    + get (Z :. (i-1) :. (j+1))
    + get (Z :. i     :. (j-1))
    + get (Z :. i     :. (j+1))
    + get (Z :. (i+1) :. (j-1))
    + get (Z :. (i+1) :. j)
    + get (Z :. (i+1) :. (j+1))

 sumAround'関数では、index関数などによってsumAround'関数の第2引数として渡される「Z :. i :. j」に隣接する各要素の合計を求めています。

 ただし、このsumAround'関数の定義には大きな問題があります。sumAround'関数の第2引数として渡された「Z :. i :. j」の値によっては、「Z :. (i-1) :. (j-1)」から「Z :. (i+1) :. (j+1)」までの「隣接要素の参照」の中に、配列の範囲外への参照が含まれる可能性があるのです。そこで、配列の範囲外を参照しないようにする処理を組み込むことにしましょう。

sumAround arr = traverse arr id sumAround'
  where
    _ :. height :. width = extent arr

    sumAround' get (Z :. i :. j)
        = outIsZero get (Z :. (i-1) :. (j-1))
        + outIsZero get (Z :. (i-1) :. j)
        + outIsZero get (Z :. (i-1) :. (j+1))
        + outIsZero get (Z :. i     :. (j-1))
        + outIsZero get (Z :. i     :. (j+1))
        + outIsZero get (Z :. (i+1) :. (j-1))
        + outIsZero get (Z :. (i+1) :. j)
        + outIsZero get (Z :. (i+1) :. (j+1))

    outIsZero get ix@(Z :. i :. j)
      = if isInternal i j
          then 0
          else get ix

    isInternal i j
        =  (i <= 0) || (i >= height - 1)
        || (j <= 0) || (j >= width  - 1)

 範囲外に対する参照かどうかを検査するisInternal関数と、範囲外に対する参照の場合に定数0を返すoutIsZero関数を定義しました。場合によっては、定数0を返すのではなく、「参照しようとした範囲外の領域の近くにある要素」、例えば「Z :. i :. j」の参照先などを返すほうが適切なこともあります。