Subsequences in Prolog

Today, I was again programming in Prolog. And I found some really nice way of generating all subsequences of a given list.

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!

Prolog, logic programming

Today, I'm programming in Prolog. Prolog is a logic programming language designed to be very declarative instead of procedural. Basically it's programming in First Order Logic.
So today I've just finished building a predicate (function) which will display the sum of a list of numbers.
It works like this:
The predicate is defined as sumOf(List, Sum). The parameter Sum is for output only. Seeing this is a declarative language, let's start by defining a simple case: the sum of an empty list. You can see this will always turn out to be zero.
Let's integrate this in Prolog: sumOf([],0). Easy right?
Now let's define all the other cases. We've got to find some definition for expressing the sum of a given list.
In my case, I ended up like this:
sumOf([Head|Tail],Sum) :- sumOf(Tail,S2), Sum is Head + S2.
So, in english, this translates to: the Sum of a list, with a Head and a Tail, implies that we must have the sum, S2, of the Tail, and then the Sum must be the Head plus S2.
If you've ever done any functional or logical programming you'll probably see these 2 lines of code combined will recursively take the first element of the list until an empty list is encountered, then the sum will be zero. This will give the algorithm a starting point for the total sum, as now the algorithm will add all the list heads to this zero, eventually giving you the sum of the list.
The idea behind this declarative programming style is quite nice, and it's awesome that you can solve such a problem with just 2 lines of code. The problem is that I worked on those 2 lines for about 3 hours. I could easily solve this program using Java in about 5 minutes, writing 10-20 lines of code.
And that's the problem when programming in a functional or logical language; it takes loads of time.