2015-06-01

■

VBA

前回記事 VBAHaskellの紹介その15（引数の部分文字列のリストを取り出す）で、問題を解くためのアドホックな関数を定義して使ったことを不満点としてあげた。

VBAHaskellで実装している関数合成はスコープがフラットで、すべてのプレースホルダに実引数を渡して一斉に評価することしかできないのが問題で、このままでは本物のラムダ式からはほど遠い。

一応これを解決する関数lambdaExprを作ったのでその内容を書く。
（Haskell_1_Core モジュールに追加）

問題にしたのは以下のコードだ。

'consMap 関数の定義は cons 関数を map しているだけ
Function consMap(ByRef a As Variant, ByRef v As Variant) As Variant
    consMap = mapF(p_cons(a), v)
End Function

'consMap関数を組み込む
f = p_cons(p_makeSole, p_consMap(ph_1, ph_2))  '[a] : map (a:) b
m = foldr(p_catV, Array(), scanr(f, Array(), a))

ここで p_mapF(p_cons(ph_1), ph_2) というような形に書ければ、consMap関数は不要になる。しかし「すべてのプレースホルダに実引数を渡して一斉に評価することしかできない」と書いたとおり、これに引数 a, v を渡すと mapF(cons(a, a), v) もしくは mapF(cons(a, v), v) などと代入され、先にcons関数が評価されてしまう。本来は mapF(p_cons(a, _), v) というように、引数を代入した後もプレースホルダを残したファンクタのままでいてほしいのだ。
これは要するに引数の代入に対する関数呼び出しを遅延させればいいので、Haskell_1_CoreモジュールにlambdaExprという関数を追加してそれができるようにした。

lambdaExprを使うコードはこうなる。*1

'                         p_consを第1引数によって遅延 bind1st する
f = p_cons(p_makeSole, p_mapF(lambdaExpr(p_cons, 1, ph_1), ph_2))
m = foldr(p_catV, Array(), scanr(f, Array(), a))

lambdaExprの実質は単なる遅延 bind1st(またはbind2nd) である。
上の p_mapF(lambdaExpr(p_cons, 1, ph_1), ph_2) に引数 a, v を与えると、
mapF(bind1st(p_cons, a), v)
と評価され、最終的に
mapF(p_cons(a, _), v)
という、プレースホルダを残したままの形になっている。
これをラムダ式と呼ぶのは苦しいが lambdaExpr と名付けた。

VBAHaskellの紹介その15（引数の部分文字列のリストを取り出す）
VBAHaskellの紹介その1（最初はmapF）

*1:テストモジュールにテスト関数segmentsTest2として追加した。

2015-06-01

VBAHaskellの紹介その15（引数の部分文字列のリストを取り出す）

VBA

「関数プログラミング実践入門」に記載されている問題についての解説記事を別のところで見かけた。解説が面白かったし、VBAHaskellで実装を試みるのに手頃だったのでやってみたが、あまりいい結果にはならず課題が残った。

segments という関数で、引数に文字列を渡すと部分文字列のリストが取り出せる。例えば "ABC" に対して、["A","AB","ABC","B","BC","C"] を出力するものだ。
本に載っている実装は以下のものらしい。

segments :: [a] -> [[a]]
segments = foldr (++) [] . scanr (\a b -> [a] : map (a:) b) []

構成要素をまとめるとこうなる。

言語要素	VBAHaskell	今回の実装
foldr, scanr	foldr, scanr*1	-
リスト結合 (++)	catV 関数*2	-
リスト生成演算(:)	なし	新規作成
関数合成 .	不十分	処理を分ける
ラムダ式 \	不十分	独立した関数にする

これを実装するためにやったことは以下の通りだが、VBAHaskellの合成関数の仕組みでは今回の問題に対応するには不十分だということがわかった。

Haskellでconsと呼ばれているリスト生成演算を用意していなかったので、標準関数としてHaskell_4_vector.basモジュールに cons 関数を追加した。これは別に問題ではない。
Haskellの文字列は文字のリストだが、VBAはそうではないため、結果表示のとき配列を文字列に変換する必要がある。foldlを使ってやればできるが、効率面も考えて StdFunモジュールに配列要素を連結する関数 joinFun を実装した（VBA組み込み関数 Join 相当）。これも問題ない。
ラムダ式　\a b -> [a] : map (a:) b 　の内部にあるmap (a:) b が問題になった。インラインでは書けず、以下の関数を実装することになった。

' \a b -> [a] : map (a:) b のうち、
' map (a:) b の部分
Function consMap(ByRef a As Variant, ByRef v As Variant) As Variant
    consMap = mapF(p_cons(a), v)
End Function
    Function p_consMap(略

これらを準備して、以下のようなプログラムを書いた。*3

a = Array("A", "B", "C", "D", "E")
'   [a] : map (a:) b  の部分
f = p_cons(p_makeSole, p_consMap(ph_1, ph_2))         ' ポイント1
'   foldr (++) []  と  scanr f []  の実行
m = foldr(p_catV, Array(), scanr(f, Array(), a))      ' ポイント2
'   文字列として表示
printM mapF(p_join(, ""), m)
'A  AB  ABC  ABCD  ABCDE  B  BC  BCD  BCDE  C  CD  CDE  D  DE  E

「ポイント1」のところで、特化した関数consMapを組み込んでいる。「ポイント2」のところでは、foldrとscanrに実引数を与えて実際に評価してしまっていて、事前にひとまとまりの関数として定義できていない。
VBAHaskellで実装している関数合成はスコープがフラットで、すべてのプレースホルダに実引数を渡して一斉に評価することしかできないのが問題で、このままでは本物のラムダ式からはほど遠い。

VBAHaskellの紹介その14（変数のムーブ）
VBAHaskellの紹介その13（プレースホルダの追加：_1と_2）
VBAHaskellの紹介その1（最初はmapF）

*1:Haskell_0_declareモジュールに宣言

*2:Haskell_4_vectorモジュールで実装

*3:テストモジュールにサンプルsegmentsTest として追加

2015-05-20

VBAHaskellの紹介その14（変数のムーブ）

VBA

Haskellと全く関係ない話題だが、VBAHaskellでは効率上の理由からVariant変数のムーブ・セマンティクスを実装して利用している。APIにある moveVariant 関数だ。*1
効率とは、関数で配列を返す時に発生するローカル変数のコピーなどのことである。

' 0 から n までの自然数配列を返す関数（簡略化版）
Function iota_(ByVal n As Long) As Variant
    Dim ret As Variant, i As Long

    ReDim ret(0 To n - 1)       ' ローカル変数をReDimする
    For i = 0 To n - 1: ret(i) = i: Next i
    iota_ = ret                 ' 普通に返すか
    iota_ = moveVariant(ret)    ' ムーブして返すか
End Function

VBAには return 文がなく、関数名 = 値とすることによって値を返す。しかし関数名を直接 ReDim することはできない。上記の例だと、ReDim iota_(0 to n - 1) とはできないので、配列を返すためにはローカル変数をReDimし、関数名 = ローカル変数とする。
ここで iota_ = ret とするとVariant変数のコピーが発生するため、大きな配列の場合や頻繁に呼び出される場合にはコストが無視できない。
どうせローカル変数は捨てられるのだから、ムーブしてしまえばよい。

//sourceのVARIANT変数をtargetのVARIANTへmoveする
VARIANT __stdcall  moveVariant(VARIANT* source)
{
    VARIANT target;
    ::VariantInit(&target);
    std::swap(target, *source);
    return target;
}

実装はこれだけで、std::swap の VARIANT への特殊化はもちろんしていない。
（その後、moveVariantはswapVariant関数を使って実装する形に変更した。変数のスワップの方が汎用性が高いのだ。）

これは実測してかなり効果があることが分かった。元の変数はきれいさっぱり消えてしまうので注意が必要だが、「配列を受け取って何かして返す」というとき、Sub プロシージャでなく Function プロシージャにできるというメリットがある。

' 単に配列の最初の要素をインクリメントするだけ
Function moveIt(ByRef x As Variant) As Variant
    x(0) = x(0) + 1
    moveIt = variantMove(x)
End Function

'aは大きな配列
a = moveIt(a)
b = moveIt(a)    ' こうすると a は消えるが一瞬で処理できる

こうすれば、引数を渡すのも返すのもコストを気にせずに済む。API内でも functionExpr::eval で使用している。

VBAHaskellの紹介その13 （プレースホルダの追加： _1 と _2 ）
VBAHaskellの紹介　その1　（最初はmapF）

*1:後述のように、API側はswapVariantという関数に変更し、moveVariantはVBA側に移動した

2015-05-17

ネストした関数を可視化するユーティリティ

VBA

2015/4/16の記事 VBAHaskellの紹介その7（bind1stとbind2nd）で記述に誤りがあった。bind1stとbind2ndの中身がどうなっているかの説明で、bind1stで上書きされない変数を上書きされると間違えていたのだ。
VBAHaskellの関数は配列なので直接見えないし、ネストされているものがあるから、bind1stやbind2ndでどう変更されるのかが非常にわかりにくい。そこでそれを可視化するユーティリティを作って Haskell_3_printMモジュールに入れた。

'ネストした関数を文字列化
Function dumpFun(ByRef x As Variant) As Variant

これによって、関数の入れ子状態や変数の束縛状況、プレースホルダの配置などがある程度分かる。束縛された値は数値や文字列の場合はそのまま出力し、配列などそのまま出力できないものは * 表示する。プレースホルダについては、暗黙のプレースホルダは _ 、ph_1 と ph_2は _1 と _2 で表した。
表示例は以下の通り。

f = p_plus(p_minus(ph_1, 5), p_mult(, ph_2))
? dumpFun(f)
F6828(F8556(_1, 5), F6644(_, _2))

? dumpFun(bind1st(f, 111))
F6828(F8556(111, 5), F6644(_, _2))

? dumpFun(bind2nd(f, 222))
F6828(F8556(_1, 5), F6644(222, 222))

2015-05-16

VBAHaskellの紹介その13 （プレースホルダの追加： _1 と _2 ）

VBA

VBAHaskellで2変数関数を合成するときの自由度を高めるために新しいプレースホルダ ph_1 と ph_2 を導入した。これの直接のきっかけは以下の問題 *1 を解くことだった。

問題4
正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。

これには下のような比較関数を使ってソートする必要がある。(())

'比較関数（aとbは数字だけからなる文字列とする）
Function Question4Comp(ByRef a As Variant, ByRef b As Variant) As Variant
    'a,bの順に結合した文字列を数値化  <  b,aの順に結合した文字列を数値化
    Question4Comp = IIf(Val(a & b) < Val(b & a), 1, 0)
End Function

もちろんこれでいいのだが、こういう単純な比較関数はいちいちモジュールに書くのではなく、関数合成で作り出したい。しかし今までの実装では難しかったので、C++側を改造しVBA側で新しく2種類のプレースホルダを追加した。
これまでの実装では比較関数 f(x, y) の中で何か計算をしようとして関数を合成しても、f(g(x), h(y)) という形にしかならなかった *2 が正しい。))。 f(x, y) の x には第1引数のみ、y には第2引数のみを渡していたのである。実引数(a, b)を代入すると f(g(a), h(b)) となるので、a と b は分離され結合文字列を作ることができない。ab を逆順の ba にすることも難しい。
単純に f(g(a, b), h(a, b)) を評価するように変えればいいが、合成されていないただの f(x, y) に適用したときには f(a, b) となるべきで、 f(a, a) とか f(b, b) になってはいけない。もちろんVBAのユーザーコードは修正不要にしたい。
そこで、C++標準ライブラリのstd::placeholdersにある _1 や _2 のような明示的なプレースホルダを導入することにした。これまでプレースホルダは関数の中で置かれている位置によって第1引数を受け取るか第2引数を受け取るかが決まっていたが、これらは場所に依存せずに受け取る引数を決め打ちできる。もちろん _1 は第1引数を受け取り、_2 は第2引数を受け取るプレースホルダだ。
VBAではアンダースコア '_' で始まる変数や関数がエラーになってしまうので、_1、_2 ではなく ph_1 と ph_2 と名付けている *3。

具体的にはこうなる。

' f(x, y) = CLng(x & y) < CLng(y & x)    と同じ
comp4 = p_less(p_getCLng(p_plus(ph_1, ph_2)), p_getCLng(p_plus(ph_2, ph_1)))

' dumpFunで中身を見てみる
?dumpFun(comp4)
F8652(F1868(F6828(_1, _2), _), F1868(F6828(_2, _1), _))

これを使って対象の配列に対するソートインデックスを作ればいい。ただし問題が「最大数」を求めるものなので逆順にしてから適用する。

' 上の方のcomp4を使う
s = sortIndex_pred(arr, comp4)     ' ソートインデックスを出力
result = subM(arr, reverse(s))     ' 逆順に並べ替える

このサンプルをテストモジュールに追加した。(Sub sortTest2)

VBAHaskellの紹介その12（1時間以内に解けなければプログラマ失格がなんたら）
VBAHaskellの紹介その1（最初はmapF）

*1:1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題にの問題4

*2:正確には g と h は2変数関数のうち1変数を束縛したものなので、f(g(x, x), h(y, y

*3:Haskell_1_Core.basモジュールに追加。

2015-05-13

比較関数の自然な例(2)

VBA

昨日の VBAHaskellの紹介その12 では、5つある問題のうち5番目だけを対象にした。今考えると、元記事「1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に」にある問題4

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。

が、2015年4月20日のブログ比較関数の自然な例で探していたものだということに気付いた。

VBAHaskellで実装しているソート関数 sortIndex_pred は、比較関数を第2引数に与えることで任意の大小関係でソートを実行できるのだが、たいていの場合はそんなもの使わなくても、何らかの変換写像でマップした値に通常の大小関係を適用すればできてしまう。

しかしこの問題4はそういうやり方では難しく、以下のような比較関数が必要になる。

Function Question4Comp(ByRef a As Variant, ByRef b As Variant) As Variant
    Question4Comp = IIf(val(a & b) < val(b & a), 1, 0)
End Function

例えば "5" と "53" では、文字列としての通常の大小関係は "5" < "53" だが、この順に連結した時と逆順に連結した時の比較をしてみると "553" > "535" なので、"53" < "5" というわけである。この問題を解くには、この大小関係で数字を大きい順に並べる必要がある。

この比較関数があればイミディエイト・ウィンドウ上で片付けられる。

' 1～99 の整数乱数を10個作る
a = mapF(p_getCLng(p_rnd(,99)), repeat(0,10))
' 文字列化する
b = mapF(p_cStr, a)
' 件の比較関数でソート（逆順）
c = subM(b, reverse(sortIndex_pred(b,p_Question4Comp)))
' もとの数列を出力
printM a
  11  99  67  2  57  10  10  79  28  5
' ソート後の列を出力
printM c
  99  79  67  57  5  28  2  11  10  10
' 文字列を結合して表示
? foldl1(p_plus, c)
997967575282111010

ただし文字列化関数 p_str は今日必要性に気付いて Haskell_2_stdFun.bas に追加したものだ。

2015-05-12

constexprカウンタ

C++

きのうtwitter上で紹介されていた、いわゆるconstexprカウンタのコード。

&lt;a href="http://melpon.org/wandbox/permlink/Ddng0P1vvVkBTUlt" data-mce-href="http://melpon.org/wandbox/permlink/Ddng0P1vvVkBTUlt"&gt;[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ&lt;/a&gt;melpon.org

昨夜は考えても分からなかったけれど、今やっと理解できた気がする。

なんというか、貯金を貯めていってる感じ？