You can also change the search strategy used in Prolog, ie using library(search), supporting BFS and iterative deepening. Tabling is also supported.

Another useful tool for homoiconicity is clause/2:

?- assertz((foo(X) :- append(X, _, [1,2,3]))).

true.

?- clause(foo(X), Body).

Body = append(X, _, [1, 2, 3]).

If you really like Haskell and OCaml's pattern matching, you'll probably really love Prolog. Prolog's pattern matching is much more powerful.