(PowerShell)ダイナミックスコープなReduce
$1. 関数内再帰関数で Join-Paths
最初にちょっと寄り道。
前回エントリでは、引数を配列にして3つ以上のパス要素連結関数を書きました。
Join-Path 同様に可変長の引数にすることは出来ないでしょうか? できました。
function Join-Paths{ function rec ([string[]] $paths){ $parent, $rest = $paths if(-not $rest){ $parent }else{ Join-Path $parent (rec $rest) } } rec $args }
PS C:\> Join-Paths C: xxx yyy zzz C:\xxx\yyy\zzz
仮引数を省略するとすべての引数は暗黙変数 $argsに配列で渡されます。可変長の再帰関数は書けませんが $argsで受けてしまえば配列を要求する関数へ渡すことが可能です。
ここでは関数内のローカル関数として再帰関数を定義しています。
$2. パイプラインで実装
PowerShellといえばパイプライン指向ですので、パイプラインによる実装も書いてみましょう。
function Join-Paths { $acc, $rest = $args $rest | % {}{$acc=Join-Path $acc $_}{$acc} }
% の後ろの3つのブロックが、begin(初期化), process(繰り返し), end(最終処理)となっています。初期化処理は特に必要なかったので空っぽです。
名前付引数を使えば beginブロック自体を省略できます。
function Join-Paths{ $acc, $rest = $args $rest | % -Process {$acc=Join-Path $acc $_} -End {$acc} }
この場合、-Processも省略できるようです。
function Join-Paths{ $acc, $rest = $args $rest | % {$acc=Join-Path $acc $_} -End {$acc} }
PowerShellの再帰呼び出しはとても遅いので、通常はこのようにパイプラインやループで書くほうがよさそうです。
$3. ダイナミックスコープなReduce
本題。
% (ForEach-Objectコマンドレット)で畳み込み処理ができましたが、Endブロックを書いたり、Beginブロックに気を遣ったりするのは少し煩わしいですね。そこで関数型言語によくある高階関数的な畳み込み関数 Reduceを書いてみました。
function Get-ReduceObject ([ScriptBlock] $Script, [object] $Init){ if($null -ne $Init){ $acc = $Init }elseif($input.MoveNext()){ $acc = $input.Current }else{ return } $input | % {$acc = & $Script} -End {$acc} } Set-Alias reduce Get-ReduceObject
$Init は畳み込みの初期値です。省略可能です。省略した場合、$Inputの初項で代用されます。
$Input は 暗黙の変数で、パイプラインから流れ込むデータを表します。IEnumerator を実装しているので。MoveNextメソッドで参照先を移動し、Currentプロパティで現在の値を取得できます。(ここでは初項を取り出すために MoveNext,Currentを使っています)。また$Inputはforeachで回したりパイプラインへ流すこともできます。
ScriptBlockは無名関数のようなものです。& 演算子で実行します。
ScriptBlockはダイナミックスコープです。クロージャではないので ScriptBlock内の自由変数は実行時の環境で値が決まります。
使ってみます。
PS C:\> 1..10 | reduce {$_ * $acc} 3628800 PS C:\> 1..5 | reduce { "(cons $_ $acc)" } -Init "NIL" (cons 5 (cons 4 (cons 3 (cons 2 (cons 1 NIL)))))
$_ と $acc は Get-ReduceObject内で $Script が実行される環境で見えている $_ と $acc の値となります。...でも、Get-ReduceObject 内に $_ は見当たりませんね。
ForEach-Objectコマンドレット (%) の Processブロック内ではパイプラインからの値が一つ一つ 暗黙変数 $_ でわたってきます。この暗黙変数がそのまま $Scriptから見えているのです。
この reduce を使ってパス連結関数を書くと。
function Join-Paths { $args | reduce {Join-Path $acc $_} }
ForEach-Object を生で使った場合と比べるとだいぶスッキリしました。
$4. Emacs Lispでも書いてみる。
Emacs Lispはダイナミックスコープな処理系ということで有名です。ならば同じことができるはず。
;; ダイナミックスコープを利用した reduce (defun reduce-dy (fun ls &optional init) (let (($acc (if init init (car ls))) (ls (if init ls (cdr ls)))) (dolist ($_ ls $acc) (setq $acc (funcall fun)))))
(reduce-dy '(lambda () (* $acc $_)) '(1 2 3 4 5 6 7 8 9 10)) ;;=> 3628800
(reduce-dy '(lambda () (format "(cons %s %s)" $_ $acc)) '(1 2 3 4 5) 'NIL) ;;=> "(cons 5 (cons 4 (cons 3 (cons 2 (cons 1 NIL)))))"
なるほどね。