I have written the following program, which calculates the longest non-decreasing sub-sequence of input array.
The sub-program to find the longest list from the list of lists is taken from stackoverflow (How do I find the longest list in a list of lists) itself.
:- dynamic lns/2.
:- retractall(lns(_, _)).
lns([], []).
lns([X|_], [X]).
lns([X|Xs], [X, Y|Ls]) :-
lns(Xs, [Y|Ls]),
X < Y,
asserta(lns([X|Xs], [X, Y|Ls])).
lns([_|Xs], [Y|Ls]) :-
lns(Xs, [Y|Ls]).
% Find the longest list from the list of lists.
lengths([], []).
lengths([H|T], [LH|LengthsT]) :-
length(H, LH),
lengths(T, LengthsT).
lengthLongest(ListOfLists, Max) :-
lengths(ListOfLists, Lengths),
max_list(Lengths, Max).
longestList(ListOfLists, Longest) :-
lengthLongest(ListOfLists, Len),
member(Longest, ListOfLists),
length(Longest, Len).
optimum_solution(List, Ans) :-
setof(A, lns(List, A), P),
longestList(P, Ans),
!.
I have used the Prolog dynamic database for memoization purpose. Though the program with database runs slower than the program without database. Below are the comparative times between two runs.
?- time(optimum_solution([0, 8, 4, 12, 2, 10, 6, 14, 1, 9], Ans)).
% 53,397 inferences, 0.088 CPU in 0.088 seconds (100% CPU, 609577 Lips)
Ans = [0, 2, 6, 9]. %% With database
?- time(optimum_solution([0, 8, 4, 12, 2, 10, 6, 14, 1, 9], Ans)).
% 4,097 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 2322004 Lips)
Ans = [0, 2, 6, 9]. %% Without database. commented out the database usage.
I would like to know if I am using the dynamic database correctly. Thanks!
The issue is that as you are traversing the list building subsequences, you need to consider only prior subsequences whose last value is less than the value you have in-hand. The problem is that Prolog's first-argument indexing is doing an equality check, not a less-than check. So Prolog will have to traverse the entire store of lns/2, unifying the first parameter with a value so you can check to see if it's less and then backtracking to get the next.