Prolog 中的多个构造函数

Question

我试图在 Hailstone 序列上实现各种形式的查询。

冰雹序列是具有以下属性的正整数序列：

1 被认为是序列的终止值。
对于任何偶数正整数i，序列中i之后的值是i/2。
对于任意奇数正整数j > 1，序列中j之后的值为3j+1

查询可以

hailSequence(Seed,Sequence)：其中Sequence是从给定的Seed生成的冰雹序列。
hailStone(M,N)：其中 N 是冰雹序列中 M 之后的数字。例如。如果 M 是 5 那么 N 应该是 16，如果 M 是 20 那么 N 应该是 10，等等
hailStorm(Seed,Depth,HailTree)：其中 HailTree 是可以在指定深度序列中位于 Seed 之前的值树。

示例：

| ?- hailStorm(1,4,H).  
H = hs(1,hs(2,hs(4,hs(8)))) ?  
yes 

| ?- hailStorm(5,3,H).  
H = hs(5,hs(10,hs(3),hs(20))) ?  
yes

Pictorial Representation

现在我已经实现了前两个谓词：

hailSequence(1,[1]) :- !.  
hailSequence(N,[N|S]) :- 0 is N mod 2, N1 is round(N / 2), hailSequence(N1,S).  
hailSequence(N,[N|S]) :- 1 is N mod 2, N1 is (3 * N) + 1, hailSequence(N1, S).  

hailStone(X,Y) :- nonvar(X), 0 is X mod 2, Y is round(X / 2).  
hailStone(X,Y) :- nonvar(X), 1 is X mod 2, Y is (3 * X) + 1.  
hailStone(X,Y) :- nonvar(Y), 1 is Y mod 3, T is round( (Y - 1) / 3), 1 is T mod 2, X is T.

对于 hailStorm/2 谓词，我编写了以下代码，但它没有按预期工作：

make_hs1(S,hs(S)).  
make_hs2(S,R,hs(S,make_hs1(R,_))).  
make_hs3(S,L,R,hs(S,make_hs1(L,_),make_hs1(R,_))).  

hailStorm(S,1,hs(S)) :- !.  
hailStorm(S,D,H) :- nonvar(S), nonvar(D), 4 is S mod 6, S=\= 4, make_hs3(S,hailStorm(round((S-1)/3),D-1,_X),hailStorm(2*S,D-1,_Y),H).  

hailStorm(S,D,H) :- nonvar(S), nonvar(D), make_hs2(S,hailStorm(2*S,D-1,_X),H).

输出：

| ?- hailStorm(5,2,H).  
H = hs(5,make_hs1(hailStorm(2*5,2-1,_),_))  
yes

这不是想要的输出，即

H = hs(5,hs(10)) ?

Answer 1

问题陈述中表达了几个问题：

在序言中，有谓词和项但没有函数.将它们视为函数会让人相信您可以编写诸如 foo(bar(3), X*2)) 之类的术语，并期望 Prolog 将调用 bar(3) 并评估 X*2 和然后将这些结果作为两个参数传递给 foo。但是 Prolog 所做的是像您看到的那样传递这些项（实际上，X*2 在内部就是项，*(X,2)）。如果 bar(3) 被调用，它不会 return 一个值，而是成功或失败。
is/2 不是变量赋值运算符，而是算术表达式求值器。它计算第二个参数中的表达式，并统一它与左边的变量或原子。能统一就成功，否则就失败。
虽然 0 is N mod 2, N1 is round(N / 2) 等表达式可以工作，但您可以在 Prolog 中更多地利用整数运算并将其更恰当地写为 0 =:= N mod 2, N1 is N // 2 其中 =:=是算术比较运算符。也可以使用位运算：N /\ 1 =:= 0, N1 is N // 2.
你还没有为冰雹风暴树的样子定义一个一致的定义。例如，有时您的 hs 项有一个参数，有时有三个。如果您没有在谓词 hailStorm.

所以你的 hailSequence 在其他方面是正确的，但你不需要删减。我会将其重构为：

hail_sequence(1, [1]).
hail_sequence(Seed, [Seed|Seq]) :-
    Seed > 1,
    Seed /\ 1 =:= 0,
    S is Seed // 2,
    hail_sequence(S, Seq).
hail_sequence(Seed, [Seed|Seq]) :-
    Seed > 1,
    Seed /\ 1 =:= 1,
    S is Seed * 3 + 1,
    hail_sequence(S, Seq).

或者更简洁，使用 Prolog if-else 模式：

hail_sequence(1, [1]).
hail_sequence(Seed, [Seed|Seq]) :-
    Seed > 1,
    (   Seed /\ 1 =:= 0
    ->  S is Seed // 2
    ;   S is Seed * 3 + 1
    ),
    hail_sequence(S, Seq).

你对 hailStone 的描述并没有说它必须是 "bidirectional"，但你的实现暗示这就是你想要的。因此，它看起来不完整，因为它缺少大小写：

hailStone(X, Y) :- nonvar(Y), Y is X * 2.

我会使用一点 CLPFD 重构它，因为它将给出 "bidirectionality" 而无需检查 var 和 nonvar。我还将区分 hail_stone1 和 hail_stone2，原因您稍后会看到。这些代表冰雹石可以产生的两种方式。

hail_stone(S, P) :-
    hail_stone1(S, P) ; hail_stone2(S, P).
hail_stone1(S, P) :-
    S #> 1,
    0 #= S rem 2,
    P #= S // 2.
hail_stone2(S, P) :-
    S #> 1,
    1 #= S rem 2,
    P #= S * 3 + 1.

注意S必须限制为> 1，因为1之后没有冰雹石。如果你想使用 var 和 nonvar，我会把它留作转换回来的练习。 :)

现在进入序列。首先，我要清楚地定义树的外观。由于它是一棵二叉树，因此常见的表示形式是：

hs(N, Left, Right)

其中 Left 和 Right 是分支（子树），其值可能为 nul、n、nil 或其他任何值你希望代表一棵空树的原子。现在我们有一个一致的 3 参数项来表示树。

然后可以更容易地定义谓词以产生冰雹风暴：

hail_storm(S, 1, hs(S, nil, nil)).  % Depth of 1

hail_storm(S, N, hs(S, HSL, HSR)) :-
    N > 1,
    N1 is N - 1,

    % Left branch will be the first hail stone sequence method
    (   hail_stone1(S1, S)       % there may not be a sequence match
    ->  hail_storm(S1, N1, HSL)
    ;   HSL = nil
    ),

    % Right branch will be the second hail stone sequence method
    (   hail_stone2(S2, S)       % there may not be a sequence match
    ->  hail_storm(S2, N1, HSR)
    ;   HSR = nil
    ).

从中我们得到，例如：

| ?- hail_storm(10, 4, Storm).

Storm = hs(10,hs(20,hs(40,hs(80,nil,nil),hs(13,nil,nil)),nil),hs(3,hs(6,hs(12,nil,nil),nil),nil)) ? ;

(1 ms) no

如果您想使用二叉树的不太对称且可以说不太规范的定义：

hs(N)        % leaf node
hs(N, S)     % one sub tree
hs(N, L, R)  % two sub trees

然后 hail_storm/3 谓词变得稍微复杂但易于管理：

hail_storm(S, 1, hs(S)).
hail_storm(S, N, HS) :-
    N > 1,
    N1 is N - 1,
    (   hail_stone1(S1, S)
    ->  hail_storm(S1, N1, HSL),
        (   hail_stone2(S2, S)
        ->  hail_storm(S2, N1, HSR),
            HS = hs(S, HSL, HSR)
        ;   HS = hs(S, HSL)
        )
    ;   (   hail_stone2(S2, S)
        ->  hail_storm(S2, N1, HSR),
            HS = hs(S, HSR)
        ;   HS = hs(S)
        )
    ).

从中我们得到：

| ?- hail_storm1(10, 4, Storm).

Storm = hs(10,hs(20,hs(40,hs(80),hs(13))),hs(3,hs(6,hs(12)))) ? ;

no

Prolog 中的多个构造函数

Multiple Constructors in Prolog

constructor

prolog

collatz