CODEWITHSUNDEEP
matrixprologrowbacktracking
Shabu
Shabu

Reputation: 645

Prolog - Getting element from a list of lists

I am having trouble figuring out how to access a single character from a list of strings without using recursion, but instead backtracking.

For example I have this list of Strings and I want to be able to return a single character from one of these strings ('.' 'o', '*'). The program I am working on is treating it as rows and columns. It is a fact in my database that looks like this:

matrix(["...o....",
        ".******.",
        "...o....",
        ".*...*..",
        "..o..*..",
        ".....*..",
        ".o...*..",
        "....o..o"].

I have the predicate:

get(Row,Col,TheChar) :-

that takes a row and column number (with index starting at 1) and returns the entry (TheEntry) at that specific row and column.

I have a feeling my predicate head might not be build correctly but I'm really more focused on just how to go through each String in the list character by character without recursion and returning that.

I am new to prolog and am having major difficulty with this.

Any help at all would be greatly appreciated!

Thank you!

Upvotes: 3

Views: 4071

Answers (2)

Nicholas Carey
Nicholas Carey

Reputation: 74345

using your matrix representation, you could do something like this:

cell(X,Y,Cell) :- matrix(Rows) , Matrix =.. [matrix|Rows] , arg(X,Matrix,Cols) , Row =.. [row|Cols] , arg(Y,Row,Cell) .

The use of =.. to construct terms on the fly might be a hint that your matrix representation isn't the best. You might consider different representations for your matrix.

Assuming a "standard" matrix with fixed-length rows, you could represent the matrix

A B C D
E F G H
I J K L

in a couple of different ways:

  • A single string, if the cell values can be represented as a single character and your prolog supports real strings (rather than string-as-list-of-char-atoms):

    "ABCDEFGHIJKL"

    Lookup is simple and zero-relative (e.g., the first row and the first column are both numbered 0):

    ( RowLength * RowOffset ) + ColOffset

    gives you the index to the appropriate character in the atom. Retrieval consists of a simple substring operation. This has the advantages of speed and simplicity.

  • a compound term is another option:

    matrix( rows( row('A','B','C','D') ,
              row('E','F','G','H') ,
              row('I','J','K','L')
            )
      ).

    Lookup is still simple:

    cell(X,Y,Matrix,Value) :- arg(X,Matrix,Row) , arg(Y,Matrix,Cell) .

  • A third option might be to use the database to represent your matrix more directly using the database predicates asserta, assertz, retract , retractall , recorda, recordz, recorded, erase. You could build a structure of facts, for instance in the database along the lines of:

    matrix( Matrix_Name ).

matrix_cell( Matrix_Name , RowNumber , ColumnNumber , Value ).

    This has the advantage of allowing both sparse (empty cells don't need to be represented) and jagged (rows can vary in length) representations.

  • Another option (last resort,you might say) would be to jump out into a procedural language, if your prolog allows that, and represent the matrix in a more...matrix-like manner. I had to do that once: we ran into huge performance problems with both memory and CPU once the data model got past a certain size. Our solution was to represent the needed relation as a ginormous array of bits, which was trivial to do in C (and not so much in Prolog).

I'm sure you can come up with other methods of representing matrices as well.

TMTOWTDI (Tim-Toady or "There's More Than One Way To Do It") as they say in the Perl community.

Upvotes: 1

cth
cth

Reputation: 422

An implementation of get/3 might look like this:

get(Row,Col,TheChar) :-    
   matrix(M),
   nth(Row,M,RowList),
   nth(Col,RowList,TheChar).

Note that TheChar is unified to a character code e.g. 

| ?- get(1,4,X).
X = 111

If you want to get see the character you can for instance use atom codes, e.g.

| ?- get(4,2,X), atom_codes(CharAtom,[X]).
X = 42
CharAtom = *

Hope this helps.

Upvotes: 3

Related Questions