KenN%MIT-OZ%MIT-MC@sri-unix.UUCP (05/15/84)
Everyone knows how to write concatenate in Prolog. I thought of a variant with interesting properties. It is intended to be run with mode(+,+,-). concatenate([A,B,C,D|X],Y,[A,B,C,D|Z]) :- ! concatenate([X,Y,Z]). concatenate([A|X],Y,[A|Z]) :- concatenate([X,Y,Z]). concatenate([],Y,Y). In LM-Prolog the above runs about 25% faster than without the first clause. It also means that the result is cdr-coded in chunks four long. The first clause could be automatically derived from the other two. If this trick was used often, then it would be worth getting Prolog compilers to generate code that was clever enough to avoid the first clause on recursive calls if a goal fails to unify with it. After a quick check it seems that currently for LM-Prolog that doing four steps of concatenate at once is optimal. It would be interesting to know if the first clause helps in other Prolog implementations and what the optimal number of steps it should incorporate. Comments?