# Logically pure/impure predicate implementations in the std lib

**URL:** <https://swi-prolog.discourse.group/t/logically-pure-impure-predicate-implementations-in-the-std-lib/6317>\
**Category:** General\
**Created:** [February 28, 2023, 6:39am UTC](https://swi-prolog.discourse.group/t/logically-pure-impure-predicate-implementations-in-the-std-lib/6317 "2023-02-28T06:39:02Z")\
**Posts on this page:** 1\
**Showing post:** 21

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [May 19, 2023, 7:48pm UTC](https://swi-prolog.discourse.group/t/logically-pure-impure-predicate-implementations-in-the-std-lib/6317/21 "2023-05-19T19:48:10Z")

</div>

Improved determinism:

```prolog
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:

```prolog
?- 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:

```prolog
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:

```prolog
?- 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:

```prolog
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:

```prolog
?- 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:

```prolog
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:

```prolog
?- 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).

```

---

_[View the full topic](https://swi-prolog.discourse.group/t/logically-pure-impure-predicate-implementations-in-the-std-lib/6317)._
