Skip to content

Instantly share code, notes, and snippets.

@WillNess
Last active September 10, 2018 13:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save WillNess/b48a13e4ee740fd19ac0112204fd15c0 to your computer and use it in GitHub Desktop.
Save WillNess/b48a13e4ee740fd19ac0112204fd15c0 to your computer and use it in GitHub Desktop.
/**
* Lazy lists represented as Closure (like plus(1)) that gives
* NextElt, NextClosure on call to call(Closure, NextElt, NextClosure) -- remarks and edits by wn
* cf. unfold :: (b -> (a, b)) -> b -> [a] -- for my personal readability
*
* Copyright 2018, XLOG Technologies GmbH, Switzerland
* Jekejeke Prolog 1.3.0 (a fast and small prolog interpreter)
*/
%% source:
%% https://stackoverflow.com/questions/52122727/solve-dynamic-programming-in-prolog-via-corecursion
%% by https://stackoverflow.com/users/502187/j4n-bur53
% take(+Integer, +LazyList, -List)
take(0, _, L) :- !,
L = [].
take(N, C, [X | L]) :- N > 0,
call(C, X, C2),
N2 is N - 1,
take( N2, C2, L).
% drop_while(+LazyList, -Element)
drop_while(C, P) :-
call( C, X, C2),
( X = P
; drop_while(C2, P)
).
/**
* Co-recursive dynamic programming
*
* 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.
*
* Copyright 2018, XLOG Technologies GmbH, Switzerland
* Jekejeke Prolog 1.3.0 (a fast and small prolog interpreter)
*/
:- use_module(library(basic/lists)).
% elevator(+Integer, +Integer, +Integer, -Path)
elevator(N, I, J, [J|L]) :-
drop_while( steps(N, [[I]]), [J|L]).
% ?- 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
% steps(+Integer, +Paths, -Path, -LazyPaths)
steps(N, [X|XS], X, steps(N, Z)) :-
up(N, X, P, []),
down( X, Q, P),
append( XS, Q, Z).
% up(+Integer, +Path, -Paths, +Paths)
up(N, [I|L], P, Q) :-
J is I+2,
J =< N, !,
P = [[J, I | L] | Q].
up(_, _, R, R).
% down(+Path, -Paths, +Paths)
down([I|L], P, Q) :-
J is I-3,
J >= 1, !,
P = [[ J, I | L] | Q].
down(_, R, R).
% ?- 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]]
/********************************************************************/
/* Binary Tree Example */
/********************************************************************/
% tree(-Path, -LazyPaths)
tree(H, T) :-
tree([[]], H, T).
% tree(+Paths, -Path, -LazyPaths)
tree([X|Y], X, tree(Z)) :-
append(Y, [[0|X],[1|X]], Z).
% ?- 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]]
/**
* Some common lazy lists.
*
* Copyright 2018, XLOG Technologies GmbH, Switzerland
* Jekejeke Prolog 1.3.0 (a fast and small prolog interpreter)
*/
% map(+Function, +LazyList, -Element, -LazyList)
map( F, C, X, map(F, C2)) :-
call(C, Y, C2),
call(F, Y, X).
% ints_from_by(+Integer, +Integer, -Elment, -LazyList)
ints_from_by( N, D, N, ints_from_by(N2, D)) :-
N2 is N + D.
% recip(+Number, -Number)
recip( X, Y) :-
Y is 1/X.
% ?- take( 4, map( recip, ints_from_by( 4, -1)), L).
% L = [0.25,0.3333333333333333,0.5,1.0]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment