How can make array in prolog?

Question

I want to make an array in Prolog. How can do it? How can access the elements?

tnx, i know this link. and something about Lists in prolog but i want to learn something like array in c++ (or c) with a simple example. if you have it please share. tnx again — BeginnerProgrammer, Jan 29 '12 at 08:07
AFAIK, it is impossible to make an array in prolog, but you can simulate it with a simple predicate "returning" i-th element of your list if you really need it. — Alexander Putilin, Jan 29 '12 at 08:16

score 8 · Answer 1 · answered Feb 23 '12 at 20:41

8

The stadard Prolog way of having (possibly limited in length, non-mutable) arrays is with arg/3 predicate:

11 ?- length(X,4), A =.. [g|X], arg(1,A,a).

X = [a, _G590, _G593, _G596]
A = g(a, _G590, _G593, _G596) 

Yes

12 ?- length(X,4), A =.. [g|X], arg(1,A,a), arg(3,A,c), arg(2,A,b), arg(1,A,d).

No
13 ?- length(X,4), A =.. [g|X], arg(1,A,a), arg(3,A,c), arg(2,A,b), arg(4,A,d).

X = [a, b, c, d]
A = g(a, b, c, d) 

Yes

Bratko ("Prolog programming for artificial intelligence") has the code to solve the classic 8 queens problem using this feature.

Another way to emulate arrays in Prolog is to encode your list as a binary tree, for O(log(n)) access time.

answered Feb 23 '12 at 20:41

Will Ness

70,110
9
98
181

Some timing seems to show that arguments of a functor are still represented and accessed as a linked list internally. :(... is there a way around this? I am implementing a language and this algorithmic inefficiency is unacceptable. – protist Sep 21 '13 at 15:55
Sorry, I was looking at the wrong number. I was reading the result as the inference count. Programming while drunk haha. 1 inference no matter the argument requested, beautiful. – protist Sep 21 '13 at 15:59
I left them because I thought someone might benefit from knowing that the access time on arguments of a functor using `arg/3` is O(1). Knowing there is a good abstraction is one thing, knowing the abstraction has the expected algorithmic efficiency is another. :) – protist Sep 22 '13 at 10:49
Of interest: [Does SWI-Prolog have N+K-trees?](https://swi-prolog.discourse.group/t/does-swi-prolog-have-n-k-trees/1310) – Guy Coder Sep 25 '19 at 18:49
@GuyCoder that's a different problem though, a *resizable* array. btw cf. this [related data structure](https://en.wikipedia.org/wiki/Hashed_array_tree). – Will Ness Sep 25 '19 at 19:51

score 6 · Answer 2 · edited Mar 10 '22 at 11:30

6

If you are using a Prolog that has unlimited arity on terms, like SWI-Prolog, you can use setarg/3 to emulate a vector.

Please read the notes that the project leader wrote on the argument.

I've never used arrays in Prolog, but answering this question, I tested for efficiency of the functionality. Actually works fairly well.

edited Mar 10 '22 at 11:30

Erik Kaplun

37,128
15
99
111

answered Jan 29 '12 at 08:27

CapelliC

59,646
5
47
90

2

I think this is a much closer equivalent to arrays in Prolog than the accepted answer of linked lists. – danr Jan 29 '12 at 13:13
1

not even `setarg` but a simple and standard **`arg`** will do - is much better actually - for an "8-puzzle problem". The key is that it's **not** updatable. (seen it in Bratko) – Will Ness Feb 23 '12 at 20:21

score 5 · Accepted Answer · answered Jan 29 '12 at 08:14

5

There's no 'array' in prolog. I mean, you cannot get an indexed list. All you have to do is access the list as somewhat like a linked list. You'll have to do it in a recursive way.

answered Jan 29 '12 at 08:14

Sufian Latif

13,086
3
33
70

List can use for 8-puzzle problem?? – BeginnerProgrammer Jan 29 '12 at 08:18
1

-1. The standard Prolog way to have (possibly length-limited, possibly un-updatable) arrays is with `arg/3` predicate, which allows direct indexing. Bratko gives amazing code for the "8-puzzle" (which I take to mean 8-queens puzzle) using this technique, and the key there is that the value at a given index can **not** be changed after it was first set. – Will Ness Feb 23 '12 at 20:24

Pierre · Answer 4 · 2017-05-30T01:35:05.247

You can simulate an array using a binary heap. Accessing and changing an element is in Theta(log(i)) where i is the index of the element, instead of Theta(1) for an array in say C.

:- module(arraysim, [insertAS/4,getAS/3]).
%------------------------------------------------------------------------    
%
% AUTHOR: Pierre
%
% USE OF A BINARY TREE TO STORE AND ACCESS ELEMENTS INDEXED FROM THE
% SET OF POSITIVE INTEGERS, I.E. SIMULATION OF SPARSE ARRAYS.
%
% Provide predicates:
% = =================
%
% insertAS(+Value,+Index,+Tree,-NewTree) to insert/rewrite Value at node
% of index Index in Tree to produce NewTree.
%
% getAS(-Value,+Index,+Tree): to get the Value stored in node of index
% Index in Tree. Value is nil if nothing has been stored in the node
% (including the case when the node was never created).
%
% User note:
% =========
%
% assume indexation starts at 1.
% The empty Tree is [].
%
% Data Structure:
% ==============
%
% The nodes of the binary tree are indexed using the indexing scheme
% employed to implement binary heaps using arrays. Thus, the indexes of
% elements in the tree are defined as follows:
%
% The index of the root of the tree is 1
% The index of a left child is twice the index of the parent node
% The index of a right child is twice the index of the parent node plus
% one.
%
% A tree is recursively represented as a triple:
% [Value,LeftTree,RightTree] where Value is the value associated with
% the root of the tree. if one of LeftTree or RightTree is empty this
% tree is represented as an empty list.
%
% However, if both left and right tree are empty the tree (a leaf node)
% is represented by the singleton list: [Value].
%
% Nodes that correspond to an index position whose associated value has
% not been set, but are used to access other nodes, are given the
% default value nil.
%
% Complexity:
% ==========
%
% Insertion (insertAS) and extraction (getAS) of the element at index i
% runs in Theta(log_2(i)) operations.
%
% The tree enables to store sparse arrays with at most a logarithmic (in
% index of element) storage cost per element.
%
% Example of execution:
% ====================
%
% 10 ?- insertAS(-5,5,[],T), insertAS(-2,2,T,T1),
% | insertAS(-21,21,T1,T2), getAS(V5,5,T2),
% | getAS(V2,2,T2),getAS(V10,10,T2),getAS(V21,21,T2).
% T = [nil, [nil, [], [-5]], []],
% T1 = [nil, [-2, [], [-5]], []],
% T2 = [nil, [-2, [], [-5, [nil, [], [-21]], []]], []],
% V5 = -5,
% V2 = -2,
% V10 = nil,
% V21 = -21.
%
%------------------------------------------------------------------------


%------------------------------------------------------------------------
%
% find_path(+Index,-Path)
%
% Given an index find the sequence (list), Path, of left/right moves
% from the root of the tree to reach the node of index Index.
%
%------------------------------------------------------------------------

find_path(Index,Path):-
    integer(Index),
    Index > 0,
    find_path2(Index,[],Path).

%-----------------------------------------------------------------
%
% find_path2(+Index,+Acc,-Path)
%
% Use of an accumulator pair to ensure that the sequence is in the
% correct order (i.e. starting from root of tree).
%
%-----------------------------------------------------------------


find_path2(1,Path,Path):-!.
find_path2(Index,Path,ReturnedPath):-
    Parity is Index mod 2,
    ParentIndex is Index div 2,
(   Parity =:= 0
->  find_path2(ParentIndex,[left|Path],ReturnedPath)
;   find_path2(ParentIndex,[right|Path],ReturnedPath)
).

%-----------------------------------------------------------------
%
% insertAS(+Value,+Index,+Tree,-NewTree)
%
% Insert Value at node of index Index in Tree to produce NewTree.
%
%-----------------------------------------------------------------

insertAS(Value,Index,Tree,NewTree):-
    find_path(Index,Path),
    insert(Value,Path,Tree,NewTree),!.

%-----------------------------------------------------------------
%
% insert(+Value,+Path,+Tree,-NewTree)
%
% Insert Value at position given by Path in Tree to produce
% NewTree.
%
%-----------------------------------------------------------------

% insertion in empty tree
%
insert(Value,[],[],[Value]).
insert(Value,[left|P],[],[nil,Left,[]]):-
    insert(Value,P,[],Left).
insert(Value,[right|P],[],[nil,[],Right]):-
    insert(Value,P,[],Right).

% insertion at leaf node
%
insert(Value,[],[_],[Value]).
insert(Value,[left|P],[X],[X,Left,[]]):-
    insert(Value,P,[],Left).
insert(Value,[right|P],[X],[X,[],Right]):-
    insert(Value,P,[],Right).

% insertion in non-empty non-leaf tree
%
insert(Value,[],[_,Left,Right],[Value,Left,Right]).
insert(Value,[left|P],[X,Left,Right],[X,NewLeft,Right]):-
    insert(Value,P,Left,NewLeft).
insert(Value,[right|P],[X,Left,Right],[X,Left,NewRight]):-
    insert(Value,P,Right,NewRight).

%-----------------------------------------------------------------
%
% getAS(-Value,+Index,+Tree)
%
% get the Value stored in node of index Index in Tree.
% Value is nil if nothing has been stored in the node
% (including the case when the node was never created).
%
%-----------------------------------------------------------------

getAS(Value,Index,Tree):-
    find_path(Index,Path),
    get(Value,Path,Tree),!.

%-----------------------------------------------------------------
%
% get(-Value,Path,+Tree)
%
% get the Value stored in node with access path Path in Tree.
% Value is nil if nothing has been stored in the node
% (including the case when the node was never created).
%
%-----------------------------------------------------------------

get(nil,_,[]).
get(nil,[_|_],[_]).
get(Value,[],[Value]).
get(Value,[],[Value,_,_]).
get(Value,[left|P],[_,Left,_]):-
    get(Value,P,Left).
get(Value,[right|P],[_,_,Right]):-
    get(Value,P,Right).

score 1 · Answer 5 · answered May 07 '22 at 19:46

I have two articles on how to do it :

Arrays in Prolog

Arrays using OOP

but the shortest answer :

ary1d_new(Size,Sym,Ary) :- 
  functor(Ary,a1,Size), 
  forall(arg(X,Ary,_), nb_setarg(X,Ary,Sym)).
ary1d_get(Pos,Ary,Val) :- arg(Pos,Ary,Val).
ary1d_set(Pos,Ary,Val) :- nb_setarg(Pos,Ary,Val).

How can make array in prolog?

5 Answers5