Prolog Accumulators. Are they really a “different” concept?

by

When you give something a name, it suddenly becomes more real than it used to be. Discussing something can now be done by simply using the name of the concept. Without getting any more philosophical, no, there is nothing special about accumulators, but they are useful.

In practice, going through a list without an accumulator:

foo([]).
foo([H|T]) :-
    foo(T).

The head of the list is left behind, and cannot be accessed by the recursive call. At each level of recursion you only see what is left of the list.

Using an accumulator:

bar([], _Acc).
bar([H|T], Acc) :-
    bar(T, [H|Acc]).

At every recursive step, you have the remaining list and all the elements you have gone through. In your len/3 example, you only keep the count, not the actual elements, as this is all you need.

Some predicates (like len/3) can be made tail-recursive with accumulators: you don’t need to wait for the end of your input (exhaust all elements of the list) to do the actual work, instead doing it incrementally as you get the input. Prolog doesn’t have to leave values on the stack and can do tail-call optimization for you.

Search algorithms that need to know the “path so far” (or any algorithm that needs to have a state) use a more general form of the same technique, by providing an “intermediate result” to the recursive call. A run-length encoder, for example, could be defined as:

rle([], []).
rle([First|Rest],Encoded):- 
    rle_1(Rest, First, 1, Encoded).               

rle_1([], Last, N, [Last-N]).
rle_1([H|T], Prev, N, Encoded) :-
    (   dif(H, Prev) 
    ->  Encoded = [Prev-N|Rest],
        rle_1(T, H, 1, Rest)
    ;   succ(N, N1),
        rle_1(T, H, N1, Encoded)
    ).

Hope that helps.

More Related Contents:

  1. count the number of calls of a clause
  2. Should I avoid tail recursion in Prolog and in general?
  3. What is tail recursion?
  4. What is tail call optimization?
  5. Way to go from recursion to iteration
  6. Solution for “Fatal error: Maximum function nesting level of ‘100’ reached, aborting!” in PHP
  7. Determining complexity for recursive functions (Big O notation)
  8. Tower of Hanoi: Recursive Algorithm
  9. Does Python optimize tail recursion?
  10. What is recursion and when should I use it?
  11. How can I make recursive templates in AngularJS when using nested objects?
  12. Tail recursion in C++
  13. Is Cmake set variable recursive?
  14. Recursive function causing a stack overflow
  15. “application: not a procedure” in binary arithmetic procedures
  16. recursive variadic template to print out the contents of a parameter pack
  17. Recursion vs loops
  18. Generate tail call opcode
  19. Real-world examples of recursion [closed]
  20. Implications of foldr vs. foldl (or foldl’)
  21. How does the fibonacci recursive function “work”?
  22. Examples of Recursive functions [closed]
  23. Is it possible to make a recursive closure in Rust?
  24. Tail Call Optimisation in Java
  25. Does PHP optimize tail recursion?
  26. Are there problems that cannot be written using tail recursion?
  27. What does “Overflow evaluating the requirement” mean and how can I fix it?
  28. SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process
  29. Tail recursion in gcc/g++
  30. Which recursive functions cannot be rewritten using loops? [duplicate]

Leave a Comment