非決定性 with 例外

『On Lisp』の非決定性が面白い。

(define (two-numbers)
  (list (choose '(0 1 2 3 4 5))
        (choose '(0 1 2 3 4 5))))

(define (parlor-trick sum)
  (let ((nums (two-numbers)))
    (if (= (apply + nums) sum)
        `(the sum of ,@nums)
        (fail))))

> (parlor-trick 7)
(THE SUM OF 2 5)

On Lisp - 非決定性

　choose関数が正しい選択を行うと仮定したコードになっている。カラクリは単純。choose関数に指定された数値分の継続を順番に実行しているだけ。継続の実行をfail関数で行うことでfail関数が呼ばれないパスが求めるべき解になる。
　実は継続を使わなくても例外でできる。というわけで、D言語で実装してみる。

import std.stdio;

// やり直し例外
class FailException : Exception {
  this(string message, string file = __FILE__, int line = __LINE__) {
    super(message, file, line);
  }
}

// 試行錯誤
void choose_bind(T)(T[] choices, void delegate(T) fn) {
  foreach (int choice; choices) {
    try {
      fn(choice);
    }
    catch (FailException e) {
      continue;
    }
    return;  // 見つかった
  }
  fail();    // 見つからない
}

// やり直し
void fail() {
  throw new FailException("not found");
}

// firstsとsecondsのうち和がsumになる組み合わせを探す。
void parlor_trick(int sum, int[] firsts, int[] seconds) {
  choose_bind(firsts, (int first) {
    choose_bind(seconds, (int second) {
    
      // sumはfirstとsecondの和である。
      if (sum == first + second) {
        writeln(sum, " := ", first, " + ", second);
      }
      else {
        fail();
      }
    
    });
  });
}

void main() {
  writeln("<7>");
  parlor_trick(7, [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]);
  
  writeln("<23>");
  parlor_trick(23, 
               [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 
               [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
              );
  
  writeln("<70>");
  parlor_trick(70, [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]);
}

うまく動いた。

<7>
7 := 2 + 5
<23>
23 := 8 + 15
<70>
main2.FailException@nond.d(26): not found