3 ms·
>> What turned me off to Prolog is that there's no way to reason about the computational complexity of the algorithm. That's easy to figure out once you realis
by YeGoblynQueenne 10y ago
>> What turned me off to Prolog is that there's no way to reason about the computational complexity of the algorithm.
That's easy to figure out once you realise your code also has an imperative reading. So for instance it's obvious that reversing a list:
reverse(A, B) :-
reverse(A, [], B, B).
reverse([], A, A, []).
reverse([B|A], C, D, [_|E]) :-
reverse(A, [B|C], D, E).
takes time proportional to the lists' length, since you're walking through the list an element at a time. And it's easy to figure out that consing, as in [B|C], is a constant-time operation.
Or, for instance, say you wanted to apply reverse/4 to elements of a list-of-lists:
findall(L_, (member(L, Ls), reverse(L, L_)), Ls_).
You can see that this is going to take the time to go through Ls, times the time to reverse each L. Same goes for the recursive version, except we need to reverse the output also to get it back in the right order:
revall(Ls, Ls_):-
revall(Ls, [], Ls_).
revall([], Ls, Ls_):-
reverse(Ls, Ls_)
,!.
revall([L|Ls],Acc,Bind):-
reverse(L, L_)
,revall(Ls, [L_|Acc], Bind).
So it's not different than any other language really, and in fact you can, up to a point, completely ignore the declarative meaning of your program if you just want to think about how fast it's going to go.