Tay Ray Chuan home archive

start small, simple

Thu, 14 Nov 2013 16:30:58 +0800 | Filed under clp, programming, zen, prolog

I'm learning Prolog as part of CS2104. Consider a predicate in Prolog that checks if the Nth-indexed element of a list is Y:

nth([],_,_) :- fail.
nth([_|T],N,Y) :- N #> 0, N1 #= N-1, nth(T,N1,Y).

This is fine for individual N's, but what if we want all such N's for a given Y?

?- nth([2,1,3,1],N,1).
N = 1 ;
N = 4 ;


?- findall(N, nth([2,1,3,1],N,1), Ns).
Ns = [1, 4].

Wow, we didn't even have to provide this functionality explicitly. Go Prolog and CLPFD!

But aside from the Prolog fun, notice how we were concentrating on getting the individual N's part right. By not going for all N's upfront, we didn't have to muck up the code with miscellaneous bookkeeping like memory management for arrays, keeping a counter for indexing, etc. Our code was simple and easy to verify.

Come to think of it, Prolog and backtracking aside, this is similar to how one would use map of functional languages. For those who hold objections based on performance: a good compiler should be able to generate code that would drop the call and inline the function down to just branches, just like a plain-old loop. (citation needed)

blog comments powered by Disqus