At first, I didn't have the faintest idea how to do this in a logical programming language. I was again thinking way to procedural. The effect: my solutions didn't work, and I wasted about 3 hours figuring out why.
But I had a break-through! I finally looked at the problem in the correct way, the declarative way, and decided to write down what was true about a subsequence.
First of all, the basic case: a subsequence of an empty list. That's not hard, because it's empty too.
So: subsequence([],[]).
But then, what if the list wasn't empty?
Then the idea just popped into my mind, I can use one of the characteristics of a subsequence; it's order! I defined a subsequence of a list like this:
subsequence([H|T],[H|T2]) :- subsequence(T,T2).
subsequence([H|T],[H2|T2]) :- subsequence(T,[H2|T2]).
subsequence([],[]).
So this will try to match both lists' heads, and if so, then the subsequence of the tail of the first list, T, should be the tail of the second list T2.
If not, then the sublist of the tail of the first list, was still the same sublist as the one for the complete first list.
It turned out that my first try was very close to being perfect but I was missing some results.
The problem was in my last statement: subsequence([],[]).
This forced the last element of the subsequence of a list, to be the same as the last element of the original list. So I found out that it didn't matter how large the original list was, I already found a valid subsequence if I encountered an empty subsequence. Because an empty list is always a subsequence of any list.
So changing my last statement to: subsequence(_,[]). Fixed all my problems!
Great job. This helped me a lot. I was trying to do subsequence([H|T],L) :- subsequence(T,L). for the second clause and not realizing that it was also covering the first clause (the first elements could still be equal). Thus I was getting repeated solutions.
ReplyDeleteHi Colin, I'm glad you solved your problem using my post!
Delete