Complete generativity over 2D lists

Help!
1

I’m using: SWI-Prolog version threaded, 64 bits, version 8.4.2

I’m attempting to implement matrices as 2D lists in pure prolog. I want the code to generate a complete set of solutions, in that all possible 2D matrix shapes should be generated/accepted.

But what I’m getting is that I’m able to backtrack on only one of 2 dimensions at a time.

I somewhat understand the trick using length/2, but I’m unable to extend it to 2 dimensions. I tried using mutually recursive predicates but failed, although it seemed a like a good idea?

My code looks like this, queried as matrix_2D(M). :

:- use_module(library(lists)).
% a vector is a flat list
vector([]).
vector([H|T]) :-
     var(H),!,
     vector(T).
vector([H|T]) :-
     atomic(H),dif(H,[]),
     vector(T).

% a matrix is a list of vectors
matrix_2D([H|T]) :-
     length([H|T],_), %change to length(H,_) for the other dimension
     matrix_2D(T,H).
matrix_2D([],V) :-
     vector(V).
matrix_2D([Th|Tt],H) :-
     same_length(Th,H),
     vector(H),
     matrix_2D(Tt,Th).
2

I don’t understand what length([H|T],_) should do… seems totally useless, so I’m waiting for someone to explain it better.
(edit: never mind, it occurred to me that it will work on backtracking…)
Meantime, if your problem is to access columns (not sure either…), an useful pattern could be the use of library(clpfd) transpose/2.

3

Yes, sorry I should have shown my code with length(H,_), because you are right that length([H|T],_) isn’t doing anything here, and is equivalent to commenting length(H,_) out.

Actually, I think I can manage with matrix_2D(M),transpose(M,T). which indeed generates what I want.

4

You might be interested this from Jan W. personal GitHub repositories

A prototype SWI-Prolog matrix library

or the SWI-Prolog packs for matrices

ffimatrix
matrix
matrix_utils

or even using one of the R interfaces in the SWI-Prolog packs.

1 Like