読者です 読者をやめる 読者になる 読者になる

ジャグ配列をフラットな配列に展開

コーへーさんのブログからネタを拝借させていただく。

callmekohei.hatenablog.com

すでにthomさんもこのネタで記事を書いているので、VBAHaskellを使って少し違う方向性でやってみたい。

目標

ジャグ配列、たとえば Array(1, Array(2, Array(3, Array(4, Array(5), 6))), 7) をフラットな配列Array(1, 2, 3, 4, 5, 6, 7) に展開する。

方針

次のような関数curiouslyRecursive を作る。

  1. 出力用の配列を受け取り、その末尾に対象配列の各要素を順に追記していく。要素自身が配列である時は再帰的に処理する。
  2. 上記の繰り返し処理は畳み込み関数foldlで表現する。
  3. 配列の末尾に追記するときはサイズを拡張しなければならないので、処理効率が気になる。(配列結合関数catVを繰り返し呼び出すのは得策ではない。)この問題をなるべく汎用的に扱えるよう、イテレータ *1 にその機能を持たせることにし、そのための新しい関数iterator_push_exを追加する。
  4. この関数自体をfoldlの引数に渡す!

コード

' 少しだけ奇妙な再帰
Function curiouslyRecursive(ByRef it As Variant, ByRef x As Variant) As Variant
    If IsArray(x) Then  ' 配列の場合
        curiouslyRecursive = foldl(p_curiouslyRecursive, it, x)  ' ← ここ
    Else  ' 単一変数の場合
        curiouslyRecursive = iterator_push_ex(it, x)     ' 単純に末尾に追加
    End If
End Function
    ' この関数を関数ポインタ化したもの
    Function p_curiouslyRecursive(Optional ByRef firstParam As Variant, Optional ByRef secondParam As Variant) As Variant
        p_curiouslyRecursive = make_funPointer(AddressOf curiouslyRecursive, firstParam, secondParam)
    End Function

' テスト関数
Sub curiouslyRecursiveTest()
    Dim arr As Variant
    arr = Array(1, Array(2, Array(3, Array(4, Array(5), 6))), 7) ' ジャグ配列
    Dim ret As Variant: ret = Array()    ' 結果出力用配列
    Dim it As Variant:  it = make_iterator(ret)
    it = curiouslyRecursive(it, arr)
    ret = release_iterator(it)
    ReDim Preserve ret(0 To iterator_pos(it))
    printS ret  ' サイズ表示
    printM ret  ' 配列の内容表示
End Sub

「ここ」とコメントした箇所で、自分自身をfoldlの引数に渡している。配列ではない単一の変数に到達するまで再帰的に呼び出され、単一変数になったらそれを末尾に追加することになる。

イテレータに新規に導入した関数

イテレータが指し示す位置に要素を追加するが、位置が配列の UBound を超えていたらサイズを2倍にしてから追加する。

' 範囲拡張しながらiterator_push
Function iterator_push_ex(ByRef it As Variant, ByRef x As Variant) As Variant
    Dim m As Long: m = max_fun(it(1), 2 * UBound(it(0)) - LBound(it(0)) + 1)
    If UBound(it(0)) < it(1) Then
        Dim tmp As Variant
        swapVariant tmp, it(0)
        ReDim Preserve tmp(LBound(tmp) To m)
        swapVariant tmp, it(0)
    End If
    iterator_push_ex = iterator_push(it, x)
End Function

モジュール

イテレータ
https://github.com/mYmd/VBA/blob/master/Haskell_6_iterator.bas
テスト関数
VBA/test_module.bas at master · mYmd/VBA · GitHub