erlang - Erlang实现了amb运算符。

在Wikipedia上，它说可以使用call / cc来实现amb运算符以进行不确定的选择，而我的问题是，如何以唯一支持延续性的语言实现延续性amb运算符，例如二郎？

最佳答案

如果您可以对构成成功解决方案或选择作为约束的约束进行编码，则列表推导可用于生成解决方案。例如，list comprehension documentation显示了解决Pythagorean triples的示例，这是使用amb经常解决的问题（例如，参见exercise 4.35 of SICP, 2nd edition）。这是更有效的解决方案pyth1/1，显示在列表理解页面上：

pyth1(N) ->
    [ {A,B,C} ||
        A <- lists:seq(1,N-2),
        B <- lists:seq(A+1,N-1),
        C <- lists:seq(B+1,N),
        A+B+C =< N,
        A*A+B*B == C*C
    ].

amb的一个重要方面是有效地搜索解空间，这是通过使用A生成B，C和lists:seq/2的可能值，然后使用防护约束和测试这些值来完成的。请注意，该页面还显示了效率较低的解决方案，名称为pyth/1，其中A，B和C都是使用lists:seq(1,N)相同生成的；这种方法会生成所有排列，但比pyth1/1慢（例如，在我的机器上，pyth(50)比pyth1(50)慢5-6倍）。

如果您的约束不能表示为守卫，则可以使用模式匹配和try / catch来处理失败的解决方案。例如，这是pyth/1中与改写为常规函数triples/1和递归triples/5相同的算法：

-module(pyth).
-export([triples/1]).

triples(N) ->
    triples(1,1,1,N,[]).
triples(N,N,N,N,Acc) ->
    lists:reverse(Acc);
triples(N,N,C,N,Acc) ->
    triples(1,1,C+1,N,Acc);
triples(N,B,C,N,Acc) ->
    triples(1,B+1,C,N,Acc);
triples(A,B,C,N,Acc) ->
    NewAcc = try
                 true = A+B+C =< N,
                 true = A*A+B*B == C*C,
                 [{A,B,C}|Acc]
             catch
                 error:{badmatch,false} ->
                     Acc
             end,
    triples(A+1,B,C,N,NewAcc).

我们将模式匹配用于两个目的：


在函数头中，相对于A控制B，C和N的值并了解何时完成
在triples/5的最后一个子句的主体中，断言条件A+B+C =< N和A*A+B*B == C*C匹配true


如果两个条件都匹配true的最后一个子句中的triples/5，则将解决方案插入到累加器列表中，但是如果两个条件都不匹配，则会捕获badmatch错误并保留原始累加器值。

调用triples/1会产生与pyth/1和pyth1/1中使用的列表理解方法相同的结果，但它的速度也是pyth/1的一半。即使这样，使用这种方法，任何约束都可以编码为正常函数，并在try / catch表达式中测试其是否成功。