In my experience, it is hard to avoid factoring in the resolution order. Cuts are still gross as hell though. Often you can follow Bird's advice for Haskell an

In my experience, it is hard to avoid factoring in the resolution order. Cuts are still gross as hell though. 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.