CODEWITHSUNDEEP
listprolog
Świstak35
Świstak35

Reputation: 350

Prolog avoid generating same lists twice

I have following code:

internal_generator(List):-
  select(foo, List, MList),
  select(bar, MList, M2List),
  select(baz, M2List, _).

internal_generator2(List):-
  select(sth1, List, MList),
  select(sth2, MList, M2List),
  select(sth3, M2List, _).

external_generator([List1, List2]):-
  internal_generator(List1),
  internal_generator2(List2).

Prolog, after generating some List1 by internal_generator, is starting to generate List2 by internal_generator2 and display results. However, when internal_generator2 will throw all his results, prolog will go back to internal_generator, get some other result with foo,bar,baz and will start generating all possible values at internal_generator2 again.

How can I refactor my code to in some way store the results from internal_generator2?

Moreover, I don't want to use findall to generate all of the possible results at the beginning of exernal_generator (my real example is too large, and I get global stack overflow).

Upvotes: 1

Views: 332

Answers (1)

Will Ness
Will Ness

Reputation: 71070

So you need a zip. In general terms, you need reentrable coroutines for that. The built-in Prolog mechanism works in nested fashion.

So if you could re-write your generator predicates to produce their results in linear, incremental fashion, instead of by backtracking, you'd just call each a given number of times to fill your lists. Such predicates would have to represent their state somehow, and proceed by using that state to produce a new value and an augmented state. You'd chain these calculations by using the updated state from a previous call as an input to the next call.

Upvotes: 1

Related Questions