PowerShell 3.0からはじめるunfoldr and take

Powershell Haskell

最近 Haskell とかの関数型言語のリスト操作を PowerShell 2.0 で使うのにハマっている。
1つの例を挙げると、Haskell のリスト操作関数に Data.List#unfoldr というのがあって、これは　unfoldr に与えた関数とシード値を使い、先頭から末尾の向きにリストを生成してくれる。ここで、unfoldr に与える関数は現在のシード値を受け取り、リストの要素とする値と次のシード値のtupleを返す。

The unfoldr function is a `dual' to foldr: while foldr reduces a list to a summary value, unfoldr builds a list from a seed value. The function takes the element and returns Nothing if it is done producing the list or returns Just (a,b), in which case, a is a prepended to the list and b is used as the next element in a recursive call.

Data.List

これが割と便利で、例えば配列を任意の位置で2分割する関数(HaskellではsplitAtとして提供されている)と組み合わせて、配列を任意の要素数ごとに分割したリストを生成したり、要素値が或る式に従う無限リストを得たりすることが出来る。

PowerShell に unfoldr 相当の組み込みコマンドレットはないので、自分で実装する必要がある。PowerShell には末尾再帰最適化がないので、ここでは繰り返し構造に変更している。

function unfoldr([scriptblock] $f, $b) {
    while($true) {
        $it = &$f($b)
        if ($it -eq $null) {
            # f b == Nothing
            break
        } else {
            # f b == Just (a,b)
            ,$a, $b = $it
            ,$a
        }
    }
}

1から10までの整数値のリストを生成するワンライナーは次のようになる。

PS> unfoldr {param($x) if ($x -eq 11) { $null } else { ,$x,($x+1) }} 1
1
(snip)
10

有限リストならこれで良いけど、無限リストの場合は途中で評価を打ち切らねば制御が戻ってこない。かと言って unfoldr に与える関数に打ち切り条件を込めるのも格好悪い。

そこで登場するのが take 関数。リストから指定した数の要素だけを取り出し、そこで評価を打ち切ってくれる。
これも PowerShell に存在しないので実装する必要があるのだけど、PowerShell 2.0 では unfoldr のループを、unfoldr に与えた関数以外で正しく止めることは出来ない。

filter take([int]$n) {
  if ($n -gt 0) {
    # これは書けるけど
    $n--
    $_
  } else {
    # 止めるコードが書けない
  }
}

Web 上では昔から break や PipelineStoppedException 例外を使ったコードが散見されるけど、絶対にやってはいけない。

filter take_using_break([int]$n) {
  if ($n -gt 0) {
    $n--
    $_
  } else {
    # ダメ
    break
  }
}

filter take_using_exception([int]$n) {
  if ($n -gt 0) {
    $n--
    $_
  } else {
    # これもダメ
    throw (New-Object System.Management.Automation.PipelineStoppedException)
  }
}

前者はそこでスクリプトが終了してしまうし（trapしてると変なコードフローになった上に終了する）、後者はパイプラインの評価値が真っ白になる。

PS> $x = unfoldr {param($x) ,$x,$x } 1 | take_using_break 10; $x
(何も返らない)
PS> trap {continue}; $y = unfoldr {param($x) ,$x,$x } 1 | take_using_exception 10; $y
(何も返らない)

条件を関数として与えることが出来る takeWhile 関数と言うのもあるけど、実装しても同じ目に遭うことだろう。

それではどうすれば打ち切りを実現出来るのか。答えは簡単で、PowerShell 2.0 を 3.0 にバージョンアップするだけでいい。驚くべきことに、これだけで take_using_break がそのまま使える。

PS> $x = unfoldr {param($x) ,$x,$x } 1 | take_using_break 10; $x
1
(snip)
1
PS>

カラクリは PowerShellのパイプライン後段にある break の取り扱い方。2.0 では挙動不審に陥るけど、3.0 では、後段にある break が、直近の上流の繰り返し構造への break と見なされ、大域脱出することが出来るようになっている（らしい）。
# どこにもそのようなことを扱っている記事が見当たらないので、正式な意味論は不明

何はともあれ take が使えるようになって、私の PowerShell ライフはますます充実しそうだ。