Proposal for an alternative transpose/2 definition

General
1

Paulo brought in a predicate definition group/2, answering a question on stackoverflow, that I think should replace transpose/2 in library(clpfd).

Some dummy raw performance test:

?- N=1000,length(M,N),maplist({N}/[R]>>length(R,N),M),time(transpose(M,T)).
% 3,007,008 inferences, 1.170 CPU in 1.170 seconds (100% CPU, 2571118 Lips)

?- N=1000,length(M,N),maplist({N}/[R]>>length(R,N),M),time(group(M,T)).
% 1,003,002 inferences, 0.341 CPU in 0.341 seconds (100% CPU, 2938693 Lips)

And it’s almost reversible

?- group(X,[[1,2,3],[4,5,6]]).
X = [[1, 4], [2, 5|_2262], [3, 6|_2274]].

Would be nice to get rid of the last unbound element… but not essential, since currently transpose/2 needs a list of lists as first argument anyway.

If someone else thinks it could be useful, I’ll attempt to issue a proper PR for library(clpfd).

2

A little exploration hints that transpose/2 suffers from calling same_length/2 which doesn’t add to the computation. It verifies a condition, but should IMO raise an exception if this is not satisfied, It might even not be necessary to check. Second is whether library(apply_macros) is loaded to inline the maplists. Then foldl is not inlined by library(apply_macros). Removing the same_length/2 and using library(apply_macros) gets the the timing fairly close.

Almost reversible isn’t that useful :slight_smile:

Sure though, pull requests that make existing code better (cleaner, faster, shorter, using less memory) are always welcome. Often you will win on one dimension and loose on another, making the outcome less clear :frowning:

3

Seems it’s loaded, by the directive at line 143 of library(clpfd)

:- use_module(library(apply_macros)).

Indeed debugging brings up the hidden expansion

clpfd:'__aux_maplist/4_list_first_rest+0'([A|D], [B|E], [C|F]) :-
    list_first_rest(A, B, C),
    '__aux_maplist/4_list_first_rest+0'(D, E, F).

Indeed, it’s only a check, eating most of time. Maybe could be optionally disabled at load time for more performance sensitive customers.

Final digression: has been a lot of time ago, I compared my own (very old and naive) transpose_col_row/2 and transpose/2 and found they was nearly identical in performance, but readability and elegance is another matter, specially after having seen Paulo’ code.

transpose_col_row([], []).
transpose_col_row([U], B) :- gen(U, B).
transpose_col_row([H|T], R) :- transpose_col_row(T, TC), splash(H, TC, R).

gen([H|T], [[H]|RT]) :- gen(T,RT).
gen([], []).

splash([], [], []).
splash([H|T], [R|K], [[H|R]|U]) :-
splash(T,K,U).

Thanks for your comments, in the end doesn’t seem the gain is worth a PR effort.

4

Its a minor thing. I think it makes more sense to look at Fabrizio’s or some other matrix library and turn that into a standard library… If there is a transpose there we can delete it from clp(fd). It doesn’t really belong there IMO.