VBAHaskellの紹介 その18（reverseをfoldで実装）

「reverseをfoldlで実装する」、というネタを仕入れたのでやってみる。
これは簡単だ。

printM iota(1,10)
  1  2  3  4  5  6  7  8  9  10
printM foldl1(p_cons(ph_2, ph_1), iota(1,10))
  10  9  8  7  6  5  4  3  2  1

cons関数は Haskellの : 演算子と同じで配列の先頭に要素を追加するもので、プレースホルダph_1とph_2を逆順にしてfoldl1すれば配列が逆順になる。
ただしこれは効率が悪く、ちょっと配列が大きくなると使いものにならない。土台がVBAなので、配列のサイズを動的に変えるcons関数の効率を大きく改善するのは無理だ。
そこでこういう作戦とする。
・　最初に対象配列と同じ大きさの配列を作って、それに繰り返し操作をする。サイズは変えない。
・　fold関数内での返り値の取り回しを効率的にする（配列をコピーしない）。

最初に対象配列aと同じものを作り、逆順に N, N-1, N-2, ... , 2, 1, 0 の位置に書き込んでいくのだが、書き込み位置を保持する変数が必要になる。その変数とaを一緒につめ込んだジャグ配列をfoldlの初期値に与えることにした。
foldlに与える関数reverse_impleおよびreverse2関数の実装はこうなる。

Function reverse_imple(ByRef a As Variant, ByRef b As Variant) As Variant
    ' a(0) : 書き込み位置
    ' a(1) : 書き込み対象配列
    a(1)(a(0)) = b      ' 値を書き込む
    a(0) = a(0) - 1     ' 書き込み位置を動かす
    swapVariant reverse_imple, a      ' コピーしないswapで返す
End Function
    Function p_reverse_imple(略...

'reverse関数
Function reverse2(ByRef a As Variant) As Variant
    Dim ret As Variant
    ' 書き込み位置と対象をつめ込んだ配列　VBA.Array(UBound(a), a) が初期値
    ret = foldl(p_reverse_imple, VBA.Array(UBound(a), a), a)
    swapVariant reverse2, ret(1)
End Function

これを使ってみる。

a = iota(1,1000000)
m = reverse2(a)
printM m, 5
  1000000  999999  999998  999997  999996
printM m, -5
  5  4  3  2  1

期待通りの結果となった。
パフォーマンスについては、VBAHaskellにはもともと普通のループによるreverse関数がユーティリティとして存在しており、それとの比較だとだいたい4.5倍程度の時間がかかった。配列長100万では手元のマシンで140ms対640msくらいだ。

---

VBAHaskellの紹介 その17（大きな関数オブジェクト）
VBAHaskellの紹介 その1（最初はmapF）
ソース https://github.com/mYmd/VBA
dllバイナリ：
https://github.com/mYmd/VBA/blob/master/bin/mapM (32bit-Office用)
https://github.com/mYmd/VBA/blob/master/bin/mapM64 (64bit-Officey用)
VBAコード添付済みExcelブック
VBAHaskellほぼ全部入り.xlsm