In general, declarative programming tends to rely on having a sufficiently smart implementation. Maybe Prolog is simply more efficient than I would've guessed
In general, declarative programming tends to rely on having a sufficiently smart implementation. Maybe Prolog is simply more efficient than I would've guessed
Often you can follow Bird's advice for Haskell and make an inefficient program that is obviously right as a base. Prolog programs often have a generate-and-test flavor; once you have a good base, you can start refining inefficiencies in one side or the other. Maybe it's easier to make your generator produce better-qualified candidates, maybe it's easier to make your test faster.
Prolog also sometimes has surprising abilities owing to the unification process itself. For example, difference lists give you singly-linked lists with O(1) append to the tail. Data structures with "holes" are a generalization of that idea.
There's also a whole book devoted to making Prolog programs efficient: The Craft of Prolog by Richard O'Keefe.
In practice, Prolog requires the programmer to have some understanding of how it's going to be executed. This is in contrast to SQL, which is intentionally high-level to allow the database to figure out the best strategy and does require a lot more in the backend. Mercury also finds this abhorrent, but Mercury is another sufficiently-smart situation and a bit more obtuse.