prolog Archives

Generate all permuted pairs in all positions

The question is how to generate all permutations of sequence of numbers. The caveat is to generate the numbers in all positions i.e. [X,Y] and [Y,X], but best to show how it works …

:- initialization(main).

%% for list of items
ppairs(Lst,[A,B]) :- 
   is_list(Lst), length(Lst,N), 
   between(1,N,X), between(1,N,Y), nth1(X,Lst,A), nth1(Y,Lst,B).
%% for numbers
ppairs(N,Pair) :- integer(N), ppairs(1,N,Pair).
ppairs(From, To, [X, Y]) :- between(From, To, X), between(From, To, Y).

main :- 
  %% all pairs of 1 .. 3
  findall(P,ppairs(3,P),L), write(L), write('\n'),
  %% all pairs of a,b,c
  findall(P2,ppairs([a,b,c],P2),L2), write(L2).


----

[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
[[a,a],[a,b],[a,c],[b,a],[b,b],[b,c],[c,a],[c,b],[c,c]]

2022-05-07 by myriad prolog 0

Java

Here is how you do it :

import java.lang.Thread;  

public class Main {
  public static void main(String[] args)  throws Exception {
        
    long startTime = System.nanoTime();
    Thread.sleep(3000);
    long endTime = System.nanoTime();
    //divide by 1000000 to get milliseconds.
    int duration = (int) ((endTime - startTime) / (1000000 * 1000));  

    System.out.println("it took: " + duration + " secs");
  }
}

-----

it took: 3 secs

Prolog

?- numlist(1, 100, L).
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...].

?- time(numlist(1, 100, L)).
% 105 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 1126344 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...].

Python

For Python look at this post : Timing code execution

2022-04-18 by myriad java prolog python 0

Arrays in Prolog

Prolog variables are immutable. for this reason there is no builtin array type.

For Arrays implemented using Prolog OOP check here

Think about it to support backtracking Prolog have keep the state at every point. First arrays can be big and vector operations can involve elements all over the place. So keeping track is not just inefficient, but also very complex.

For this and other reasons Prolog does not support standard type of arrays.

That is all good and stuff, but what if you still need simple small array !?
The obvious way to implement it is to use Lists, but because the access to elements is sequential the implementation will be slow.

Instead we will do it in a more hacky, no-no method, by using Terms instead of Lists. We do that by employing arg and setarg. The difference is that they allow direct access ergo implementation will be fast.

Below you have simple API that support 1D and 2D arrays.

:- initialization(main).

say(X) :- write(X), write('\n').
say(D,X) :- write(D), write(X), write('\n').

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).

ary2d_new(Rows,Cols,Sym,Ary) :- 
	functor(Ary,a2,Rows), 
	ary1d_new(Cols,Sym,Row),
	forall(arg(X,Ary,_), nb_setarg(X,Ary,Row)).
ary2d_get(X,Y,Ary,Val) :- arg(X,Ary,Row), arg(Y,Row,Val).
ary2d_set(X,Y,Ary,Val) :- arg(X,Ary,Row), nb_setarg(Y,Row,Val).

main :-
say('1D example : '),
ary1d_new(5,0,A1D),say('new(5) : ', A1D),
ary1d_set(2,A1D,1),say('set(2,1) : ', A1D),
ary1d_get(2,A1D,Val),say('get(2) : ', Val),
say('2D example : '),
ary2d_new(3,3,0,A2D),say('new(3,3) : ', A2D),
ary2d_set(2,2,A2D,1),say('set(2,2,1) : ', A2D),
ary2d_get(2,2,A2D,Val),say('get(2,2) : ', Val),
ary2d_get(X,Y,A2D,1),say('find coord of 1 : ', [X,Y]).

-----

1D example : 
new(5) : a1(0,0,0,0,0)
set(2,1) : a1(0,1,0,0,0)
get(2) : 1
2D example : 
new(3,3) : a2(a1(0,0,0),a1(0,0,0),a1(0,0,0))
set(2,2,1) : a2(a1(0,0,0),a1(0,1,0),a1(0,0,0))
get(2,2) : 1
find coord of 1 : [2,2]
true.

The implementation of 2D array above uses as storage mechanism 1D array for every row.

But there is also possible to use single 1D array for this purpose. In this case to access a cell we would need to transform the 2D coordinate to 1D.

One problem with this is there is no way to guess the dimensions of the 2D array if we use 1D array to represent it. For this reason we will use the first 2 elements of the storage to store those dimensions.

Here is how an implementation will look like :

%% 2D array using 1D storage
a2d_new(Rows,Cols,Sym,Ary) :- 
	Size is Rows * Cols + 2, 
	ary1d_new(Size,Sym,Ary), 
	nb_setarg(1,Ary,Rows), nb_setarg(2,Ary,Cols).
a2d_get(X,Y,Ary,Val) :- 
	arg(2,Ary,Cols), Pos is (X-1) * Cols + Y + 2,
	arg(Pos,Ary,Val).
a2d_set(X,Y,Ary,Val) :- 
	arg(2,Ary,Cols), Pos is (X-1) * Cols + Y + 2,
	nb_setarg(Pos,Ary,Val).
a2d2lst(Ary,Lst) :- Ary =.. [ _,_,_ | Lst].

For Arrays implemented using Prolog OOP check here

2022-04-12 by myriad prolog 0

Prolog: Saving the fact+rules to file

Sometimes you may wish you can save your current state to file. Here is how you do it

save(Heads,File) :- tell(File), listing(Heads), told.

you can use the same idea to save the result of other predicates to file.

2022-01-10 by myriad prolog 0

HashList for key:value pairs

In Prolog if you need to use hashes you can use Dicts, but for small number of kv-pairs it is overkill.

In such cases use the HashList that I invented ;). It is very easy and you can use it as a Two way hash too. Very handy.

% HashList utils : [ key1:val1, key2:val2, ... ], also can be used as TwoWaysHash
keys(HL,Res) :- maplist(\I^K^(I = K:_),HL,Res).
vals(HL,Res) :- maplist(\I^V^(I = _:V),HL,Res).
val(Key,HL,Res) :- member(Key:Res,HL).
key(Val,HL,Res) :- member(Res:Val,HL).

-----

?- use_module(library(lambda)).

?- H = [first:john, last:doe, city:huston, state:tx],
keys(H,Keys),vals(H,Vals),
val(city,H,Val),key(huston,H,Key).

H = [first:john, last:doe, city:huston, state:tx],
Keys = [first, last, city, state],
Vals = [john, doe, huston, tx],
Val = huston,
Key = city .

2021-11-30 by myriad prolog 0

List-in-List membership

Prolog has a predicate member, which checks if an item is in a list, but what if you want to know if multiple elements are part of a list.

%is elems from Lst1 also elems of Lst2
members(Lst1,Lst2) :- maplist( \X^(member(X,Lst2)), Lst1).

example use, but as you see it needs the lambda module :

?- use_module(library(lambda)).
?- members([3,4],[1,2,3,4]).
true .

?- members([3,4,5],[1,2,3,4]).
false.

Just found out you can get similar results with subset, but

The library(lists) contains a number of old predicates for manipulating sets represented as unordered lists, notably intersection/3, union/3, subset/2 and subtract/3. These predicates all use memberchk/2 to find equivalent elements. As a result these are not logical while unification can easily lead to dubious results.
…..
deprecated: New code should use library(ordsets) instead.

2021-11-07 by myriad prolog 0

Easier print in Prolog

say(Lst) :- is_list(Lst), writeln(Lst).
say(S)   :- say(S,[]).
say(S,P) :- string_concat(S, '~n', S1), format(S1,P).

?- say('hello').
hello
true.

?- say('hello ~w',[world]).
hello world
true.

?- say('hello ~w ~w',[new,world]).
hello new world
true.

2021-11-05 by myriad prolog 0

Meaning of {curly brakets} in Prolog

Since Prolog is a homo-iconic language, everything is a term. Therefore, we are sure that {a,b,c} is also a term.

Let’s check SWI-Prolog REPL:

?- functor({a,b,c},F,N).
F = {},
N = 1.

so, {a,b,c} it’s just a compound, and a,b,c its argument:

?- {a,b,c} =.. Syntax.
Syntax = [{}, (a, b, c)].

also write_canonical helps when exploring syntax details :

?- write_canonical({a,b,c}).
{','(a,','(b,c))}

SWI-Prolog extension, dicts, uses {} to build object representation…

2021-10-27 by myriad programming prolog 0

zip function in Prolog

:- use_module(library(lambda)). 
zip1(L1,L2,Z) :- scanl(\X^Y^_^[X,Y]^[X,Y],L1,L2,_,[_|Z]). 
zip2(L1,L2,Z) :- maplist(\X^Y^[X,Y]^[X,Y],L1,L2,Z).

or better this one :

pair(X,Y,[X,Y]).
zip(L1,L2,Z) :- maplist(pair,L1,L2,Z).

?- zip([1,2,3],[4,5,6],Z).
Z = [[1, 4], [2, 5], [3, 6]].

2021-10-27 by myriad programming prolog 0

prolog

Java

Prolog

Python

Categories

Tags

For gifts and updates