4

I would like to solve the following dynamic programming problem via corecursion in Prolog. But I am stuck in doing the breadth first search, that I would like to implement, in a correcursive fashion:

There is a building of n floors with an elevator that can only go up 2 floors at a time and down 3 floors at a time. Using dynamic programming write a function that will compute the number of steps it takes the elevator to get from floor i to floor j.

I have already decided about a lazy list representation. A lazy list would be simply a Prolog closure C, which can be called to yield a head and a new closure for the tail.

Example a stream of ones:

 one(1, one).

A Haskell take predicate can then be simply coded as follows:

 take(0, _, L) :- !, L = [].
 take(N, C, [X|L]) :- N > 0, 
    call(C, X, D), 
    M is N-1, 
    take(M, D, L).

Here is an example run:

 ?- take(5, one, X).
 X = [1, 1, 1, 1, 1].

 ?- take(10, one, X).
 X = [1, 1, 1, 1, 1, 1, 1, 1, 1|...].
  • on a tangential note, `take(1, C, L)` shouldn't force C's tail. It might be causing errors, needlessly. SRFI-40 lists one such example, take(4, map((1/), intsFromBy(4, -1)), L). – Will Ness Sep 02 '18 at 06:56
  • 1
    There is no problem, I get: ?- take(4, map(rezi,ints_from_by(4,-1)), L). L = [0.25,0.3333333333333333,0.5,1.0] . Source code is here: https://gist.github.com/jburse/b0afd3efc9fa12919b61a032d449545f#file-ness-pl –  Sep 02 '18 at 09:25
  • ah, indeed. there is no already available 'current' head, in your implementation. It's closer to SRFI-41 streams. I didn't read your code close enough before commenting. thanks, very interesting. – Will Ness Sep 02 '18 at 10:43
  • Yes, of course. I'm saying, conceptually it is like that implementation. the other possibility is having a pair of current element (already forced) and something to create the next pair from (like I have in some of my answers; modeled after SICP streams; similar to the SRFI-40). – Will Ness Sep 02 '18 at 14:40
  • In retrosprect, I guess I was using unconsciously Richard O'Keefes the Craft of Prolog, Chapter 6: Sequences. There you find almost everything, also for example why I coded "up" and "down" the way I coded it, for the "steps". See his Section 6.3.6: Enumerator to List. –  Sep 02 '18 at 14:54
  • thanks for the reference! (haven't opened it in ages...) – Will Ness Sep 02 '18 at 14:54

1 Answers1

2

In this co-recursive Prolog solution we need two building blocks.

One building block is a way to enumerate a search tree co-recursively in Prolog. We adopt the idea that the Prolog closure term should carry an agenda with the paths and thus nodes that should be expanded. We can then start with an agenda that only contains the root:

% tree(-Path, -LazyPaths)
tree(H, T) :-
   tree([[]], H, T).

To archive breadth first enumeration we will append the new expanded paths and thus nodes at the end of the agenda. This can be done by a simple list append predicate call, so that the missing definition reads as follows. In the full binary tree paths and thus nodes are always expanded twice:

% tree(+Paths, -Path, -LazyPaths)
tree([X|Y], X, tree(Z)) :-
   append(Y, [[0|X],[1|X]], Z).

Here is an example run:

?- take(5, tree, L).
L = [[],[0],[1],[0,0],[1,0]]

?- take(10, tree, L).
L = [[],[0],[1],[0,0],[1,0],[0,1],[1,1],[0,0,0],[1,0,0],[0,1,0]]

In case of the evaluator problem we will have a path and thus node expansion that will not always lead to two successors. If we are at a level k, the elevator can go to a level k+2 or k-3, only provided the elevator stays inside the building. So we readly arrive at a co-recursive predicate steps that does simulate all possible paths of the elevator:

?- take(5, steps(7,[[2]]), L).
L = [[2],[4,2],[1,4,2],[6,4,2],[3,1,4,2]]

?- take(10, steps(7,[[2]]), L).
L = [[2],[4,2],[1,4,2],[6,4,2],[3,1,4,2],[3,6,4,2],
    [5,3,1,4,2],[5,3,6,4,2],[2,5,3,1,4,2],[7,5,3,1,4,2]]

The last hurdle and second building block is to get a Haskell dropWhile in Prolog. We didn't aim at a predicate that takes a Prolog closure term argument for the boolean condition, but instead only provide a predicate that enumerates the lazy list elements, and the user of the predicate can filter in the Prolog continuation.

% drop_while(+LazyList, -Element)
drop_while(C, P) :-
   call(C, Q, T),
   (P = Q; drop_while(T, P)).

If we put everything together we get a co-recusive Prolog solution, that can even potentially enumerate all infinite solutions to the evaluator problem via backtracking besides calculating the results in breadth first order:

?- elevator(7,2,6,L), length(L,N).
L = [6,4,2],
N = 3 ;
L = [6,4,2,5,3,1,4,2],
N = 8 ;
L = [6,4,7,5,3,1,4,2],
N = 8