Несколько конструкторов в Prolog

В постановке задачи выражено несколько вопросов:

• В Прологе есть предикаты и термы, но нет функций. Думая о них как о функциях, можно подумать, что вы можете написать такие термины, как foo(bar(3), X*2)), и ожидать, что Пролог вызовет bar(3) и оценит X*2, а затем передаст эти результаты в качестве двух аргументов foo. Но что делает Пролог, так это передает их так же, как термы, как вы их видите (на самом деле, X*2 внутри является термом, *(X,2)). И если была вызвана bar(3), она не возвращает значение, а либо завершается успешно, либо терпит неудачу.

• is/2 — это не оператор присваивания переменной, а скорее оценщик арифметического выражения. Он оценивает выражение во втором аргументе и объединяет его с переменной или атомом слева. Он преуспевает, если может объединиться, и терпит неудачу в противном случае.

• Хотя такие выражения, как 0 is N mod 2, N1 is round(N / 2), будут работать, вы можете получить больше преимуществ от целочисленной арифметики в Прологе и записать ее более подходящим образом, как 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).

Или, более компактно, используя шаблон Пролога 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 не говорится, что он должен быть "двунаправленным", но ваша реализация подразумевает, что вы этого и хотели. Таким образом, он кажется неполным, поскольку отсутствует корпус:

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

Я бы реорганизовал это, используя немного CLPFD, так как это даст «двунаправленность» без проверки 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 или любой другой атом, который вы хотите представить пустым деревом. Теперь у нас есть согласованный терм с тремя аргументами для представления дерева.

Тогда предикат может быть более легко определен для получения града:

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