Pack multiple predicates into one list without enumerating predicate insertion order?

[light-and-salt]

Goal: I'm trying to get the shortest path tree from a graph:

% get the shortest path from root to each node
#minimize { Ti@5, X : node(X, Ti), is_step(Ti) }.

Problem: The nodes in this graph are generated at runtime, and modeled as multiple predicates (instead of one simple predicate):

% Ti = 0
dashboard("db1", 0).
chart("ch1", 0).
field("ch1", x, "Displacement", 0).
chart("ch2", 0).
...
...

So I try to pack all dashboard information into one node(X, Ti) (Ti = 0, 1, 2...) -- the dashboard, the charts it may contain, the multifarious properties of each chart that can be generated at runtime... I was able to collect all relevant predicates into one list[] using an external function that sorts predicates and inserts them into a Python list (see code below). BUT the performance is poor because the external function is called at grounding time. The way I'm calling the insert() function right now, all combinations are computed insert(ch1), insert(ch2) & insert(ch2), insert(ch1) (the combinatorial effect gets worse when I pack more predicates into each node). But since I'm sorting predicates inside the insert() function, all these computation result in the same node(X). Is there a definitive way to insert all predicates into one list[] just once, without enumerating predicate insertion order?

Here's my code:

#script (python)

from clingo.symbol import Number, String, Function

class Context:

  # insert predicate into spec
  def insert(self, spec, predicate):
    print("*** insert()", spec, predicate)
    list = spec.arguments
    if predicate in list:
      return spec

    index = len(list)
    # search for the position
    for i in range(len(list)):
      if str(list[i]) > str(predicate):
        index = i
        break

    # insert the predicate into the list
    if index == len(list):
      list = list[:index] + [predicate]
    else:
      list = list[:index] + [predicate] + list[index:]
    return Function('', list)

  # count the number of predicates in spec
  def count(self, spec):
    return Number(len(spec.arguments))

def main(prg):
  prg.ground([("base", [])], context=Context())
  prg.solve()

#end.

list((ascending(), dashboard(D)), Ti) :-
  is_step(Ti),
  dashboard(D, alive, _, Ti).

list(@insert(X, chart(CH)), Ti) :-
  list(X, Ti),
  chart(CH, alive, _, Ti).

list(X, @count(X), Ti) :- list(X, Ti).

list_len(Nmax, Ti) :- is_step(Ti), #max { N: list(_, N, Ti) } = Nmax.

node(X, Ti) :- list(X, N, Ti), list_len(N, Ti), is_step(Ti).
#show node/2.

[rkaminsk]

In clingo (and other ASP systems) it generally does not work well to represent lists using function symbols. Also sorting is more expensive than in other programming languages. Maybe you can avoid sorting altogether to solve your problem? If you just need a static sort order, it might also be possible to compute it in a preprocessing step? If you need to sort using rules, you could use:

% set(S).
% member(S,I).

next(S,I,J) :- member(S,I), J = #min{ J: member(S,J), J>I }.
% (for the largest element l in a set s you get next(s,l,#sup))

[light-and-salt]

Thanks, @rkaminsk!!!

next(S,I,J) :- member(S,I), J = #min{ J: member(S,J), J>I }.

Worked: This is super helpful! I can avoid sorting in the external function and pre-sort my facts in ASP now!

In clingo (and other ASP systems) it generally does not work well to represent lists using function symbols.

To compute the shortest paths, I do need to pack variable-length facts into 1 variable though...

Didn't Work: With the external function approach, even though I got the correct next(ch1, ch2) order, inside my external function I still saw "append(ch1), append(ch2) and append(ch2), append(ch1)" kind of (unnecessary) variation. I didn't understand why it happened:

%  append facts one by one
list(@append(X, B), B, Ti) :-
  next(A, B, Ti),
  list(X, A, Ti).

Worked: So I got rid of my external function and nested the facts in ASP instead. This is working for me now:

% log facts
fact(chart(CH), Ti) :- chart(CH, alive, _, Ti).
fact(channel(CH, C), Ti) :- channel(CH, C, alive, _, Ti).
% fact(field(CH, C, F), Ti) :- field(CH, C, F, alive, _, Ti).

% sort facts ascendingly, for the smallest fact F we get next(#inf, F, Ti)
next(A, B, Ti) :- fact(B, Ti), A = #max{ F: fact(F, Ti), F<B }.
% #show next/3.

% start nesting facts into the first variable
% count the number of nested facts in the second variable
% the third variable is the last fact in the nest; #inf here because the smallest fact is next(#inf, F, Ti)
nest(dashboard(D), 1, #inf, Ti) :-
  is_step(Ti),
  dashboard(D, alive, _, Ti).
% #show nest/4.

% nest facts one by one
nest((X, B), N+1, B, Ti) :-
  next(A, B, Ti),
  nest(X, N, A, Ti).

nest_size(Nmax, Ti) :- is_step(Ti), Nmax = #max { N: nest(_, N, _, Ti) }.
% #show nest_size/2.

node(X, Ti) :- nest(X, N, _, Ti), nest_size(N, Ti), is_step(Ti).
#show node/2.