Simple code snippet: fast all_equal/1 predicate

[hurufu]

Hi, haven't been active for a long time.

Recently I wrote very fast all_equal/1 it outperforms naive maplist(=(Element), List) two times and reaches theoretical minimum number of inferences for such task. It uses cyclic terms – which you might strongly dislike, but they are good for performance.

% Describes a list that contains all the same elements
all_equal([]).
all_equal([H|T]) :-
    U = [H|U],
    finite_circular(T, U).

% All finite prefixes L that match cyclic list U
finite_circular(L, U) :- open_list(L, U-U).

% Describes list difference an it's prefix (regular list)
open_list([], X-X).
open_list([H|D], [H|T]-X) :- open_list(D, T-X).

Here are some numbers:

?- length(L, 1_000_000), time(maplist(=(hello), L)).
   % CPU time: 0.251s, 2_000_001 inferences
   L = [hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello|...].
?- length(L, 1_000_000), time(all_equal([hello|L])).
   % CPU time: 0.177s, 1_000_004 inferences
   L = [hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello|...].

Maybe someone can find it useful if you happen to need a lot of same elements :)

[UWN]

Shorter, faster, purer (NSTO):

?- length(L,1_000_000), time(append(L,_,[hello|L])).
   % CPU time: 0.095s, 1_000_057 inferences
   L = [hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello|...].
?- length(L,1_000_000), time(all_equal([hello|L])).
   % CPU time: 0.138s, 1_000_060 inferences
   L = [hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello,hello|...].

[hurufu]

Cool, append/3 is such a versatile predicate, in other languages you would need to have a whole library of functions to do what a simple append can. Actually specifying that all elements are all the same is very common in constraint satisfaction problems, so every programmer should learn quite a few idioms like this one.

[UWN]

And now such that for each element, every other element is equal. Thus:

?- everyotherequal(L).
   L = []
;  L = [_A]
;  L = [_A,_B]
;  L = [_A,_B,_A]
;  L = [_A,_B,_A,_B]
;  ... .

[hurufu]

Easy:

?- append(L,_,[_,_|L]).
   L = []
;  L = [_A]
;  L = [_A,_B]
;  L = [_A,_B,_A]
;  L = [_A,_B,_A,_B]
;  L = [_A,_B,_A,_B,_A]
;  L = [_A,_B,_A,_B,_A,_B]
;  ... .

[hurufu]

I think it would be nice to create an online collection of Prolog idioms and small code snippets. Rosetta code isn't helpful, because all tasks there are biased towards imperative languages.

[UWN]

Consider also the Prolog prologue.