比較関数の自然な例
ソートで使用する比較関数のうまい例がみつからない。
列 { Xn } をソートするのに、関数 f でマップした f(Xn) の大小関係で比較することは良くあり、そのときの比較関数は [ ] ( auto a, auto b) { return f(a) < f(b); } という内容のものになるだろう。
VBAHaskellで実装している関数は配列を直接ソートするのではなくて、ソートインデックスを出力するものだ。それならば列 { f(Xn) } を作って、デフォルトの大小関係でソートすればいいことになるし、関数 f の呼び出し回数を考慮するとその方が速度は上かもしれない。このままでは比較関数を受け取る sortIndex_pred 関数の存在意義が説得力のないものになってしまう。
あらかじめ { f(Xn) } を作っておくのが難しい（またはすごく面倒な）例はないだろうか？あれば比較関数をとる sortIndex_pred の意義をより有効に表現できるのだ。
VBAHaskellの紹介 その8 （ソート関連） - mmYYmmdd’s blog
VBAHaskellの紹介 その8 （ソート関連）
ソート関連は別にHaskellぽくない。特徴と言えるのは任意の比較関数が使えることくらいだ。
sortIndex 昇順ソート後のインデックス配列
sortIndex_pred 任意の比較関数によるソート後のインデックス配列permutate (Sub) 配列をソートインデックスを使って実際にソートする
lower_bound ソート済み配列からのキーの検索
lower_bound_pred ソート済み配列からのキーの検索
upper_bound ソート済み配列からのキーの検索
upper_bound_pred ソート済み配列からのキーの検索
equal_range ソート済み配列からのキーの検索
equal_range_pred ソート済み配列からのキーの検索
個々の機能は分かると思うので、多少注意を要する点だけあげる。
1. sortIndexとsortIndex_predは対象配列を直接ソートするわけではなく、下図の赤文字部分にあたるソート後のインデックスを出力する。*1 sortIndexは昇順ソートであり、降順指定はない。*2
対象配列 ： 3 , 1, 5 , 2 -> 1 , 2 , 3 , 5
インデックス ： [0 1 2 3] -> [ 1 3 0 2 ]
2. ソートした結果の配列を得たいときには、subM関数 *3 を使う。
' 配列を m をソートしたい
index = sortIndex(m) ' または index = sortIndex_pred(m, comp)result = subM(m, index) ' 昇順
result = subM(m, reverse(index)) ' 降順
3. 対象配列は1次元か2次元のみであり、自動的に判別される。2次元の場合は行をレコードと見たソートであり、列方向のソートはできない。ソートキーはsortIndex関数の第2引数に指定することが可能で、優先したい順に列番号を並べる。省略した場合には全列がキーとなる（左にあるほうの列が優先）。
' 2次元配列 m の0列目, 2列目, 4列目 をソートキーにする
sortIndex(m, Array(0, 2, 4))
4. sortIndex_pred では2引数の比較関数を与えることによって自由な順序でソートできる。この比較は「第1引数が第2引数より小さい」とき1を、そうでないとき０を返すものとする。比較関数さえ書ければいいので、型がバラバラでもジャグ配列でもソートできる。test_module にそのようなテスト関数を追加した。（Function comp000とSub sortTest）
「比較関数を書けばその通りにソートできて当然ではないか」というのが通常の感覚だと思うが、VBAではなかなかできなかった。
2次元配列を対象とする場合は1行を一つの配列とみて比較関数を書く。
5. upper_bound と upper_bound_pred の返り値、そしてequal_range と equal_range_pred の返り値の2番目の要素は検索範囲の最後の要素の「次の」インデックスである。C++の<algorithm>にあるのと同じだ。
6. 残念ながらAPIのC++プログラムにコンパイル時処理はない。
VBAHaskellの紹介 その7 （bind1stとbind2nd）
http://mmyymmdd.hatenablog.com/entry/2015/04/16/224313
VBAHaskellの紹介 その7 （bind1stとbind2nd）
VBAHaskellにbind1stとbind2ndを追加した。C++の<functional>にあるのとだいたい同じだが、VBAHaskellにおいては関数は初めから何らかの形で束縛されているので、あまり使う場面はないと思う。意味的には引数の"再"束縛なので rebind と名付けるべきなのかもしれない。プレースホルダになっている場所をある値で束縛するわけだが、何が1stで何が2ndかが自分でも少々わかりにくいのだ。
これを説明するために、VBAHaskellの紹介その5（関数のシグネチャ）で少し紹介した「関数ポインタ的なもの」についてもっとはっきり示したい。
VBA関数 "func" に対応する p_func *1 の実体は次の配列だ。
p_func = Array ( AddressOf func, _
placeholder, _ ' 第1引数のプレースホルダ
placeholder, _ ' 第2引数のプレースホルダ
placeholder) ' 関数であるフラグ
AddressOf funcはLong値として扱っている。*2 placeholderは API で作っている特殊な値で、一種のマジックナンバーと考えてよい。「関数であるフラグ」としてもplaceholder を流用しているが、これは手抜きに過ぎない。別に何でもよかったのだ。
想像できるように、第1引数もしくは第2引数を束縛したものは以下のものになっている。
p_func(3) = Array ( AddressOf func, _
3, _ ' 第1引数は3に束縛
placeholder, _ ' 第2引数のプレースホルダ
placeholder) ' 関数であるフラグ
p_func (, 3) = Array ( AddressOf func, _
placeholder, _ ' 第1引数のプレースホルダ
3, _ ' 第2引数は3に束縛
placeholder) ' 関数であるフラグ
bind1stとbind2ndは次のものになる。*3
bind1st(p_func(3), 100) = Array ( AddressOf func, _
3 , _ ' 第1引数は変更なし
placeholder, _ ' 第2引数のプレースホルダ
placeholder) ' 関数であるフラグ
bind2nd(p_func(3), 100) = Array ( AddressOf func, _
3, _ ' 第1引数は変更なし
100, _ ' 第2引数は100に束縛
placeholder) ' 関数であるフラグ
ややこしいのは関数がネストされた合成関数の場合だ。
p_func(p_func, p_func(, 2)) =
Array ( AddressOf func, _
Array ( AddressOf func, placeholder, placeholder, placeholder), _
Array ( AddressOf func, placeholder, 2, placeholder), _
placeholder )
これに対して、bind1st や bind2nd を作ったらこういう状態になっている。
bind1st(p_func(p_func, p_func(, 2)) , 3 ) =
p_func(p_func(3, 3), p_func(, 2)) =
Array ( AddressOf func, _
Array ( AddressOf func, 3, 3, placeholder), _
Array ( AddressOf func, placeholder, 2, placeholder), _
placeholder
)
bind2nd(p_func(p_func, p_func(, 2)) , 3 ) =
p_func(p_func, p_func(3, 2)) =
Array ( AddressOf func, _
Array ( AddressOf func, placeholder, placeholder, placeholder), _
Array ( AddressOf func, 3, 2, placeholder), _
placeholder
)
product_set関数 *4 のパフォーマンスをあげるのにこれらを使った。
# 2015/5/17 : 関数の内容を文字列化するユーティリティ関数 dumpFun を Haskell_3_printMモジュール に追加した。
VBAHaskellの紹介 その6 （foldl） - mmYYmmdd’s blog
VBAHaskellの紹介 その6 （foldl）
VBAHaskellで実装しているfoldlは本物のHaskellと同様に、「2引数関数」、「初期値」、「対象リスト」の3つの引数を取る左畳み込み関数だ。VBAでラップはしておらず、Haskell_0_declareモジュールに宣言しているC++ API *1 をそのまま使う。
Declare Function foldl Lib "mapM.dll" ( _
ByRef pCallback As Variant, _
ByRef init As Variant, _
ByRef matrix As Variant, _
Optional ByVal axis As Long = 1) As Variant
「2引数関数」である pCallbackには前回 VBAHaskellの紹介 その5（関数のシグネチャ）で解説したmake_funPointerで関数ポインタ化した構造を渡す。このとき引数は束縛しない。
例えば1から10までの整数の和を取る場合は次のように書けばよい。
' 1から10 までの整数の和を求める
foldl(p_plus, 0, iota(1, 10)) ' = 55 *2
これも含め同様の関数を列挙すると以下の８つある。
foldl 特定の軸に沿った左畳み込み（初期値指定あり）
foldr 特定の軸に沿った右畳み込み（初期値指定あり）
foldl1 特定の軸に沿った左畳み込み（初期値=先頭要素）
foldr1 特定の軸に沿った右畳み込み（初期値=先頭要素）
scanl 特定の軸に沿った左scan（初期値指定あり）
scanr 特定の軸に沿った右scan（初期値指定あり）
scanl1 特定の軸に沿った左scan（初期値=先頭要素）
scanr1 特定の軸に沿った右scan（初期値=先頭要素）
個々の 機能の説明は省略するが、「特定の軸に沿った」とは何か？これはVBAの配列には2次元以上のものがあることが関係している。2次元の場合は縦方向と横方向では別の処理になるのだが、例をあげた方が早いと思う。
m = makeM(3,5,repeat(1,15)) : printM m *3 ' [3 * 5] の配列
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
printM foldl(p_plus, 0, m, 1) ' 1は省略可
3 3 3 3 3
printM foldl(p_plus, 0, m, 2)
5 5 5
4番目の引数を1にすると 縦に加算、2にすると横に加算された1次元配列が出力値となる。３次元の場合も同様だが出力は2次元配列になる。 4次元以上には対応していない。*4
この引数となる関数は算術的な演算だけではない。applyFun*5 という「関数適用関数」を引数にすれば、任意個の関数の合成ができるのだ。
' 関数適用関数 これは要するに func(param) を呼び出している
Function applyFun(ByRef param As Variant, ByRef func As Variant) As Variant
これを関数ポインタ化した p_applyFun を使って次のようにすると、初期値 init に配列形式で与えた1変数関数を左から順次適用して結果を出力する。
foldl(p_applyFun, init, 関数配列 )
そしてこの foldlとp_applyFunの組み合わせをひとつのパターンとして関数にしてしまうこともできるのだ。*6
サンプル*7 にあるロジスティック漸化式、フィボナッチ数列、Newton法による多項式の求根などはこれを使っている。 これらの場合は関数配列と言っても同一関数のリピートである。 VBAでこんなことができるなんて、けっこう胸アツなんじゃないかと思う。
VBAHaskellの紹介 その5 （関数のシグネチャ）
http://mmyymmdd.hatenablog.com/entry/2015/04/12/205359
VBAHaskellの紹介 その5 （関数のシグネチャ）
VBAHaskellはVBAの関数を合成して独立したオブジェクトにしたり、Haskell的なリスト処理をするライブラリだが、それが可能なVBA関数のシグネチャは実質的に1種類しかない。
Function myFunction(ByRef a As Variant, ByRef b As Variant) As Variant
または
Function myFunction(ByRef a As Variant, Optional ByRef b As Variant) As Variant
この関数をそのまま使うのではなく、一種の関数ポインタ的なものにして渡す必要があって、それをやるヘルパ関数が
make_funPointer と make_funPointer_with_2nd_Default だ。
たとえば Haskell_2_stdFunモジュールで最初に定義されている firstArg 関数はこうなっている。
Function firstArg(ByRef a As Variant, ByRef b As Variant) As Variant
firstArg = a
End Function
Function p_firstArg(Optional ByRef firstParam As Variant, _Optional ByRef secondParam As Variant) As Variant
p_firstArg = make_funPointer(AddressOf firstArg, firstParam, secondParam)
End Function
firstArg 関数に付属する p_firstArg が関数ポインタを作っており、その中でmake_funPointerを呼んでいる。関数名は何でもよいが、p_関数名 にだいたい統一している。新たに関数を定義したら、この p_firstArg のコードをコピペして赤文字のところだけ対象関数に合わせて修正すれば使えるようになる。*1
make_funPointer は4要素の配列を作っているだけで、その配列は（関数ポインタ、引数1、引数2、xxx）という構成になっている。2つある引数には他の関数をネストすることもできて、これによって関数合成が実現される。
C++API側ではこのネストした配列を受け取って頻繁に呼び出すことになるが、VBAのsafearray構造体の中身に毎回アクセスするのは効率が悪いと思われるので、再帰的なリンク構造を再構成してから呼び出すようにしている。具体的には VBA_NestFunc.hpp と VBA_NestFunc.cpp にある funcExpr_i::eval() の再帰的な呼び出しがそれにあたる。
残念ながらここにはコンパイル時処理はない。
VBAHaskellの紹介 その4 （Find）
http://mmyymmdd.hatenablog.com/entry/2015/04/12/113746
VBAHaskellの紹介 その3 （FizzBuzz）
http://mmyymmdd.hatenablog.com/entry/2015/04/11/130016
VBAHaskellの紹介 その2 （合成関数）
http://mmyymmdd.hatenablog.com/entry/2015/04/11/112139
VBAHaskellの紹介 その1 （最初はmapF）
http://mmyymmdd.hatenablog.com/entry/2015/04/11/095044
ソースコード：
dllのバイナリ：
VBAHaskellの紹介 その4 （Find）
きょう、いわゆる検索関数 "find_pred" を追加した。Haskell_1_Coreモジュールに入れている。
Function find_pred(ByRef pred As Variant, ByRef vec As Variant) As Variant
対象配列の中から条件に合致する値を探す関数で、第1引数のpredは検索における条件指定の述語で、第2引数のvecは対象配列だ。
自由度の高いpredを簡単に生成できるかどうかが検索の使い勝手を決めると思う。「指定した範囲に含まれる」とか「素数である」等の条件を述語オブジェクトとして生成するときに、いちいちヘルパ関数を定義したりするのは面倒なのでやりたくない。*1
find_predは単にループを回しているだけだが、合成関数の作成と呼び出しが簡単なので、シンプルに実装できた。
これを使って乱数列の中からある範囲内の数値を探すコードはこうなる*2 。
Points = mapF(p_rnd(0), repeat(100, 10000))
pred = p_mult(p_greater( , 29.9), p_less( , 29.99))
m = find_pred(z, Points)
こう書くと pred は 29.9 < x かつ x < 29.99 を満たす x に1を、そうでない x に0を返す関数になる。ラムダ式のような自由と柔軟さはないが、C++03でbind1stやbind2ndを組み合わせて生成するよりはマシかもしれない。
find_pred の全体は以下の通り。
Function find_pred(ByRef pred As Variant, ByRef vec As Variant) As Variant
Dim z As Variant
Dim i As Long: i = LBound(vec)
For Each z In vec
If applyFun(z, pred) Then
find_pred = i
Exit Function
End If
i = i + 1
Next z
find_pred = Null
End FunctionFunction find_pred(ByRef pred As Variant, ByRef vec As Variant) As Variant
If Dimension(vec) = 1 Then
find_pred = find_imple(pred, vec, UBound(vec) + 1)
If find_pred = UBound(vec) + 1 Then find_pred = Null
Else
find_pred = Null
End If
End Function
個々の配列要素に対してapplyFun(z, pred) で pred を呼び出すだけである。
(2015/4/14)
効率上の理由からVBA側でループするのではなくAPIに find_imple 関数を追加してそれを呼び出す形に変更した。C++側でイテレーションのたびにpred の構築と破棄を繰り返すのは無駄だから。
ところで引数の順序が find_pred(pred, vec) とするか find_pred(vec, pred) とするか決め難かった。とりあえず述語を前にしたが、ソート関連の関数*3では比較関数が後になっている。
VBAHaskellの紹介 その3 （FizzBuzz）
http://mmyymmdd.hatenablog.com/entry/2015/04/11/130016
VBAHaskellの紹介 その2 （合成関数）
http://mmyymmdd.hatenablog.com/entry/2015/04/11/112139
VBAHaskellの紹介 その1 （最初はmapF）
http://mmyymmdd.hatenablog.com/entry/2015/04/11/095044
VBAHaskellの紹介 その3 （FizzBuzz）
2015-07-10
前のよりずっとわかりやすいFizzBuzzができたので書く。
というより下の記事を書いたときは寝ぼけていたとしか思えない。
' 分かりやすいFizzBuzz
fun3 = p_if_else(, Array(p_mod(, 3), placeholder, "Fizz"))
fun5 = p_if_else(, Array(p_mod(, 5), fun3, "Buzz"))
fun15 = p_if_else(, Array(p_mod(, 15), fun5, "FizzBuzz"))
printM mapF(fun15, iota(1, 100))
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz
前より短くなったわけではないが、product_setとかreplaceNullといった関数を使う必要は全然なかったのだ。シンプルなif_elseのネストに対してmapFするだけになった。
2015-04-11
基本的なパーツの紹介の前にFizzBuzzを紹介する。
' 書きたくないコード
If x Mod 15 = 0 Then Debug.print "FizzBuzz"
ElseIf x Mod 5 = 0 Then Debug.print "Buzz"
ElseIf x Mod 3 = 0 Then Debug.print "Fizz"
Else Debug.print x (改行は省略)
１から100までの整数にこのロジックを当てはめるだけだが、もちろんこんなコードを書かずに基本的なパーツの組み合わせでシンプルに表現したい。
これはなかなか短くできなかった。現状のコードは以下の通り。
m = Array(Array(p_mod(, 15), Null, "FizzBuzz"), _
Array(p_mod(, 5), Null, "Buzz"), _
Array(p_mod(, 3), placeholder, "Fizz"))printM foldl1(p_replaceNull, product_set(p_if_else, iota(1, 100), m), 2)
使っているパーツは、剰余関数"p_mod"、条件分岐関数"p_if_else"、mapの直積版"product_set"、上書き関数”p_replaceNull”、そして foldl1*1 である。
product_setは与えられた2つのリストの直積に対して関数を適用するので、イメージとしては表のようになる。対象となる関数はif_elseで、1つ目のリストの要素は1~100の整数、2つ目のリストの要素は [条件、真の場合の値、偽の場合の値] だ。
15と5については、割り切れない場合にNull値、割り切れる場合にそれぞれFizzBuzzとBuzzを設定し、3についてだけは割り切れないとき元の整数引数を設定している。それぞれのp_modで第2引数を束縛していることに注意。
これを左から見ていって、「Nullは新しい値に置き換えるがNullでなかったらそのまま」という関数を繰り返し適用すればよい。その関数は"replaceNull"で、この配列に対して foldl1 すれば結果が得られる。foldl1 の最後の引数である 2 は、2次元配列に対する畳み込みを横方向に行えという指定である。
このコードはリンクしたgithubテストモジュール(test_module.bas）の中のデモ関数 vbaUnitに書かれている。
VBAHaskellの紹介 その2 （合成関数） - mmYYmmdd’s blog
VBAHaskellの紹介 その1 （最初はmapF） - mmYYmmdd’s blog
