Logically pure/impure predicate implementations in the std lib

General
21

Improved determinism:

clumped2([], []).
clumped2([E|T], [E-Len|R]) :-
    (   integer(Len)
    ->  Len @>= 1
    ;   var(Len)
    ),
    clumped2_(T, R, E, 1, Len).

clumped2_(L, R, E, U, Len) :-
    % Possibilities:
    % U lt Len
    % U eq Len
    (   integer(Len),
        U @< Len
    % Improve determinism
    ->  C = lt
    ;   U == Len
    ->  C = eq
    ;   L == []
    ->  C = eq
    % Allow empty list
    ;   L = []
    ;   L = [H|_]
    ->  (   H \= E
        % U eq Len
        ->  C = eq
        ;   H == E
        % U lt Len
        ->  C = lt
        % Allow uncertain
        ;   true
        )
    % Allow uncertain
    ;   true
    ),
    clumped2_comp_(C, L, R, E, U, Len).

clumped2_comp_(eq, L, R, E, Len, Len) :-
    clumped2_after_eq_(L, E, R).
clumped2_comp_(lt, [E|T], R, E, U, Len) :-
    U1 is U + 1,
    clumped2_(T, R, E, U1, Len).

clumped2_after_eq_([], _, []).
clumped2_after_eq_([H|T], E, [RH|RT]) :-
    % Ensure next element is different
    dif(H, E),
    clumped2([H|T], [RH|RT]).

Results:

?- time(clumped2([a,X], C)).
% 33 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 790438 Lips)
C = [a-1, X-1],
dif(X, a) ;
% 7 inferences, 0.000 CPU in 0.000 seconds (78% CPU, 705787 Lips)
X = a,
C = [a-2].
% Is general

?- time(clumped2([a,b,b,c,c,c], C)).
% 30 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 2251407 Lips)
C = [a-1, b-2, c-3].
% No unwanted choicepoint

?- time(clumped2(L, [a-1, b-2, c-3])).
% 134 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 1638262 Lips)
L = [a, b, b, c, c, c].
% No unwanted choicepoint

… and after a bit more refinement:

clumped2([], []).
clumped2([E|T], [E-Len|R]) :-
    (   integer(Len)
    ->  Len @>= 1
    ;   var(Len)
    ),
    clumped2_(T, R, E, 1, Len).

clumped2_(L, R, E, U, Len) :-
    % Possibilities:
    % U lt Len
    % U eq Len
    (   U == Len
    ->  C = eq
    ;   clumped2_l_(L, E, C)
    ),
    clumped2_comp_(C, L, R, E, U, Len).

% Trying to determine C by looking ahead
clumped2_l_([], _, eq).
clumped2_l_([H|_], E, C) :-
    (   H \= E
    ->  C = eq
    ;   H == E
    ->  C = lt
    % Unsure
    ;   true
    ).

clumped2_comp_(eq, L, R, E, Len, Len) :-
    clumped2_after_eq_(L, E, R).
clumped2_comp_(lt, [E|T], R, E, U, Len) :-
    U1 is U + 1,
    clumped2_(T, R, E, U1, Len).

clumped2_after_eq_([], _, []).
clumped2_after_eq_([H|T], E, [RH|RT]) :-
    % Ensure next element is different
    dif(H, E), 
    clumped2([H|T], [RH|RT]).

Results:

?- time(clumped2([a,X], C)).
% 35 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 1582207 Lips)
C = [a-1, X-1],
dif(X, a) ;
% 8 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 779727 Lips)
X = a,
C = [a-2].

?- time(clumped2([a,b,b,c,c,c], C)).
% 36 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 1160616 Lips)
C = [a-1, b-2, c-3].

?- time(clumped2(L, [a-1, b-2, c-3])).
% 137 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 1483921 Lips)
L = [a, b, b, c, c, c].

Simplified further:

clumped2([], []).
clumped2([E|T], [E-Len|R]) :-
    (   integer(Len)
    ->  Len @>= 1
    ;   var(Len)
    ),
    clumped2_(T, R, E, 1, Len).

clumped2_(L, R, E, U, Len) :-
    % Improve determinism
    (   U == Len
    ->  !
    ;   U = Len
    ),
    (   L == []
    ->  !
    ;   L = [H|_],
        H \= E
    ->  !
    ;   true
    ),
    clumped2_after_eq_(L, E, R).
clumped2_([E|T], R, E, U, Len) :-
    U1 is U + 1,
    clumped2_(T, R, E, U1, Len).

clumped2_after_eq_([], _, []).
clumped2_after_eq_([H|T], E, [RH|RT]) :-
    % Ensure next element is different
    dif(H, E),
    clumped2([H|T], [RH|RT]).

Results:

?- time(clumped2([a,X], C)).
% 31 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 1510059 Lips)
C = [a-1, X-1],
dif(X, a) ;
% 6 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 711238 Lips)
X = a,
C = [a-2].

?- time(clumped2([a,b,b,c,c,c], C)).
% 33 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 1974629 Lips)
C = [a-1, b-2, c-3].

?- time(clumped2(L, [a-1, b-2, c-3])).
% 125 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 2545203 Lips)
L = [a, b, b, c, c, c].

Just noticed that the keys should be unique (depending on purpose, I suppose) - this version enforces that:

clumped2(L, C) :-
    clumped2_(L, [], C).

clumped2_([], _Ks, []).
clumped2_([E|T], Ks, [E-Len|R]) :-
    (   integer(Len)
    ->  Len @>= 1
    ;   var(Len)
    ),
    % Ensure keys are unique
    maplist(dif(E), Ks),
    clumped2_chk_(T, R, E, [E|Ks], 1, Len).

clumped2_chk_(L, R, E, Ks, U, Len) :-
    % Improve determinism
    (   U == Len
    ->  !
    ;   U = Len
    ),
    (   L == []
    ->  !
    ;   L = [H|_],
        H \= E
    ->  !
    ;   true
    ),
    clumped2_after_eq_(L, Ks, R).
clumped2_chk_([E|T], R, E, Ks, U, Len) :-
    U1 is U + 1,
    clumped2_chk_(T, R, E, Ks, U1, Len).

clumped2_after_eq_([], _Ks, []).
clumped2_after_eq_([H|T], Ks, [RH|RT]) :-
    clumped2_([H|T], Ks, [RH|RT]).

Results:

?- time(clumped2(L, [a-1, b-2, X-3])).
% 77 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 1790240 Lips)
L = [a, b, b, X, X, X],
dif(X, b),
dif(X, a).
1 Like