Geek Answers Handbook

Erlang introduces the ambition operator.

Wikipedia says that with call / cc you can implement the amb statement for non-deterministic selection, and my question is how would you implement the amb statement in a language in which the only continuation support is to write in the continuation style, like in erlang ?

+4
source share
1 answer

If you can code restrictions for what is a successful solution or a choice as security guards, then you can use lists to create solutions. For example, understanding the list in a list shows an example of a Pythagorean triples solution that is often solved with amb(see, for example, exercise 4.35 SICP, 2nd edition ). Here's a more efficient solution, pyth1/1shown on the concepts list page:

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) 5-6x , pyth1(50)).

, 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.

+4

More articles:


All Articles