Tabling: Problem with answer subsumption?

Help!
1

I have a small grammar that turns a number sequence, say 1,2,3,4,9 into a range/integer list: 1-4,9

Here is the code:

% :- table intrange_list(min,_,_). % Send bug report?


:- table intrange_list//1.
% Consolidate N, followed by (N+1)-H
intrange_list([L-H]) -->
   integer(L),
   `,`,
   { L #= L1 - 1 },
   intrange_list([L1-H]).

% Basic N,N+1 sequence
intrange_list([L-H]) -->
   integer(L),
   `,`,
   integer(H),
   { H #= L + 1 }.

% Sequence followed by sequence or integer.
intrange_list([L-H|Ls]) -->
   intrange_list([L-H]),
   `,`,
   intrange_list(Ls).

% Integer followed by sequence or integer or by itself.
intrange_list([i(N)|Ls]) -->
   integer(N),
   ( `,`, ! | [] ),
   intrange_list(Ls).

% End of list.
intrange_list([]) --> [].

Producing the following output:

2 ?- phrase(intrange_list(L),`1,2,3,4,9`).
L = [i(1), i(2), i(3), i(4), i(9)] ;
L = [i(1), i(2), 3-4, i(9)] ;
L = [i(1), 2-3, i(4), i(9)] ;
L = [i(1), 2-4, i(9)] ;
L = [1-3, i(4), i(9)] ;
L = [1-2, i(3), i(4), i(9)] ;
L = [1-2, 3-4, i(9)] ;
L = [1-4, i(9)].

I want to keep only the shortest answer (taking advantage of term ordering), so instead of using regular tabling I switched to:

:- table intrange_list(min,_,_).

But now I get this error:

5 ?- phrase(intrange_list(L),`1,2,3,4,9`).
ERROR: Uninstantiated argument expected, found [2-_16240]
ERROR: In:
ERROR:   [21] throw(error(uninstantiation_error(...),_16290))
...

Answer subsumption is not accepting the partially uninitialized term [2-_], why not allow partially uninstantiated terms?

Perhaps I am missing something.

2

That is not the problem. The clue is in Un instantiated

The argument over which we do the answer subsumption must be unbound at call time. Anyway, it seems you want to minimize the list length. That is not going to work with standard order of term, which gives the list with the smallest first argument (and if equal the smallest second, etc.)

3

Thanks, I ended up using aggregate_all/3 with set(..) and took the shortest (last) solution.

4

Just out of curiosity, why not use an algorithm that gives you the shortest solution first instead of last? You might even just take the first and be done?

5

I just put together the DCG in a few minutes, but you’re right, do you have an idea for a better DCG?

6

It really depends what you are after. I thought this is just a minimal example that demonstrates a problem with tabling, and I don’t know about that so I assumed I am missing the big picture.

So is the problem "transform the string ‘1,2,3,4,9’ into the list [1-4,i(9)]"?

EDIT: and do you know that the original list of numbers is monotonically increasing? This makes it a bit easier I think.

7

This is not a DCG answer.

Have you looked at Run Length Encoding which is very similar. There is working Prolog code for RLE at RosettaCode.

1 Like
8

The problem is transform a sequence of integers into a string such that:

  1. Any consecutive set of integers is shortened to Low-High
  2. All the other integers are left in place

EDIT: I need it to work both ways.

This is very similar to what Eric pointed out: run length encoding.

1 Like
9

Too difficult for me, sorry. I never learned how to do that.

10

Thanks Boris, you encourage me to put little bit more work, here is a version that works both ways (for the first answer) and gives the shortest answer first.

intlist_intranges([L-H|Ls]) -->
   { N1 #= L + 1 },
   [L],
   lookahead(N1),
   intlist_intranges([N1-H|Ls]).

intlist_intranges([L-H|Ls]) -->
   { H #= L + 1 },
   [L],
   [H],
   intlist_intranges(Ls).

intlist_intranges([i(I)|Ls]) -->
   [I],
   intlist_intranges(Ls).


intlist_intranges([]) --> [].

lookahead(A), [A] --> [A].