VBAHaskellの紹介 その11 （木構造）
やっと「すごいHaskellたのしく学ぼう！」の７章まで進んだところ、139ページから始まる二分木の解説の中で、「リストを1要素ずつ辿って値を返す操作はたいがい畳み込みで実装できる」という表現に感銘を受けた。
let nums = [8,6,4,1,7,3,5]
let numsTree = foldr treeInsert EmptyTree nums
これをVABHaskellでもやってみる。VBAで木構造といえばCreateObject("Scripting.Dictionary")として連想配列が使える *1 ようだが、キーの順序はVBAデフォルトの大小関係しか対応できない。ここは任意の比較関数を与えて連想配列を実装してみたいところだ。
ただし、きちんとした平衡二分探索木構築のアルゴリズムを実装する能力がないことと、要素を挿入した新しい木を返す関数がVBAで効率よく実装できないという問題があるが、あくまでサンプルということで前者は無視、後者はハッキング *2 で誤魔化すことにする。
結果的に、テストモジュールの treeTest() に書いた通り、バラバラな型のキーで木構造を作ることができた。大小比較は、「型が異なるときは変数のVarTypeで比較、配列どうしだったら次元と要素数で比較、そうでなければ数値もしくは文字列のデフォルトの大小関係」と指定したが、厳密で弱い順序関係なら何でも指定できるはずだ。ノードの集合を定義した後で、木構造自体は foldr 一発で構築している。
'型がバラバラで配列も含む木構造のテスト
Sub treeTest()
Dim nodes As Variant, tree As Variant
Debug.Print "型がバラバラで配列も含むキーによる木構造のテスト"
'===============ノードの集合===============
nodes = Array(makeNode(75676786, "A", p_comp000) _
, makeNode("abc", "B", p_comp000) _
, makeNode(iota(1, 8), "C", p_comp000) _
, makeNode("鳥小屋", "D", p_comp000) _
, makeNode(6, "E", p_comp000) _
, makeNode(makeM(2, 2, iota(1, 4)), "F", p_comp000) _
, makeNode(300, "G", p_comp000) _
, makeNode(iota(1, 15), "H", p_comp000) _
, makeNode("犬小屋", "I", p_comp000) _
, makeNode(makeM(2, 3, iota(1, 6)), "J", p_comp000) _
)
'===============畳み込みによる木の構築===============
tree = foldr(p_insertNode, Empty, nodes)
'===============キーの選択===============
Debug.Print """abc"" => ";
printM getNode("abc", tree)
Debug.Print """犬小屋"" => ";
printM getNode("犬小屋", tree)
Debug.Print "iota(1, 8) => ";
printM getNode(iota(1, 8), tree)
End Sub
