山分け関数を Perl と OCaml と awk で比べる

Higher Order Perl の最初のほうに出てくる find_share 関数は、ある重み/価値を持ったアイテムのリストからいくつかを取り出して、その重みの合計が指定の値になるようにするものだ。つまり山分け関数である。

sub find_share {
  my ($target, $treasures) = @_;
  return [] if $target == 0;
  return    if $target < 0 || @$treasures == 0;
  my ($first, @rest) = @$treasures;
  my $solution = find_share($target-$first, \@rest);
  return [$first, @$solution] if $solution;
  return         find_share($target       , \@rest);
}

このコードは何をしているかすぐに分かるほど平明ではないかもしれない。パターンマッチを持った言語だと以下のようにすっきりと書ける。

exception No_share

let rec find_share = function
| (0, _) -> []
| (_, []) -> raise No_share
| (target, _) when target < 0 -> raise No_share
| (target, x::xs) ->
  try
    x::find_share (target - x, xs)
  with No_share ->
    find_share (target, xs)

OCaml にパターンマッチがあってよかったと思える瞬間だ。この関数は以下のように使う。

# let treasure = [1; 2; 3; 4; 5];;
val treasure : int list = [1; 2; 3; 4; 5]
# find_share (8, treasure);;
- : int list = [1; 2; 5]
# find_share (6, treasure);;
- : int list = [1; 2; 3]
# find_share (9, treasure);;
- : int list = [1; 3; 5]
# find_share (7, treasure);;
- : int list = [1; 2; 4]
# find_share (12, treasure);;
- : int list = [1; 2; 4; 5]

ところでパターンマッチといえば awk である。というわけで awk を使って書いてみた。

$1 == 0 { exit 0 }
$1 < 0  { exit 1 }
NF <= 1  { exit 1 }
{
  target = $1; $1 = ""
  head = $2; $2 = ""
  rest = $0
  result = find_share(target - head, rest)
  if (result) {
    result = find_share(target, rest)
    if (result) { exit 1 }
  } else {
    print head
  }
  exit 0
}

function find_share(target, list)
{
  return system(sprintf("echo %s %s | awk -f find_share.awk", target, list))
}

これはこうやって使う。第1フィールドが目標となる分け前で、第2フィールド以降がアイテムのリストである。

$ echo 12  1 2 3 4 5 | awk -f find_share.awk
5
4
2
1

再帰的にプロセスを生むことの馬鹿馬鹿しい不経済はともかくとしてパターンマッチを使った3行目まではいい感じである。不味いのは例外処理を if に置き換えないといけなかった点で、ここはどうにも汚い。OCaml には例外もあって良かった。