Skip to content

Instantly share code, notes, and snippets.

@kamahen
Last active March 8, 2021 19:44
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save kamahen/e570d7b101a0344a56f71d05a831ea04 to your computer and use it in GitHub Desktop.
calculate path into a binary tree for some element
% -*- mode: Prolog -*-
% See https://twitter.com/krismicinski/status/1368611779107053570?s=03
% gives a program in Racket; I've written my version in
% non-deterministic Prolog.
% Tested with SWI-Prolog 8.3.20
% (You can also try this out at https://swish.swi-prolog.org/)
% The problem is (using Racket terminology):
% Write a function (tree-path t elt) that returns a list of either
% ‘left, ‘right, or ‘here that computes the path into the tree for
% some element. Your function should return the empty list if the
% element is not present in the tree.
% A Racket solution is given here (with some typos):
% https://gist.github.com/kmicinski/f3db68d8374a43edf471702f664e17ce
tree_path(node(V, _, _), V, [here]).
tree_path(node(_, Left, _Right), V, [left|Path]) :-
tree_path(Left, V, Path).
tree_path(node(_, _Left, Right), V, [right|Path]) :-
tree_path(Right, V, Path).
% Test cases.
:- use_module(library(plunit)).
:- begin_tests(tree_path).
% (tree-path ‘(leaf 5) 5) => ‘(here)
test(t1, [nondet, true(Path == [here])]) :-
tree_path(node(5, empty, empty), 5, Path).
% (tree-path ‘(node 10 (node 5 empty empty) (node 20 (node 12 empty empty) empty)) 5) => ‘(left here)
test(t2, [nondet, true(Path == [left, here])]) :-
tree_path(node(10,
node(5, empty, empty),
node(20,
node(12, empty, empty),
empty)),
5, Path).
% (tree-path ‘(node 10 (node 5 empty empty) (node 20 (node 12 empty empty) empty)) 20) => ‘(right here)
test(t3, [nondet, true(Path == [right, here])]) :-
tree_path(node(10,
node(5, empty, empty),
node(20,
node(12, empty, empty),
empty)),
20, Path).
% (tree-path ‘(node 10 (node 5 empty empty) (node 20 (node 12 empty empty) empty)) 12) => ‘(right right here)
% ^^^^^
test(t4, [nondet, true(Path == [right, left, here])]) :-
tree_path(node(10,
node(5, empty, empty),
node(20,
node(12, empty, empty), empty)),
12, Path).
% (tree-path ‘(node 10 (node 5 empty empty) (node 20 (node 12 empty empty) empty)) 50) => ‘()
test(t5, [fail]) :-
tree_path(node(10,
node(5, empty, empty),
node(20,
node(12, empty, empty),
empty)),
50, _Path).
:- end_tests(tree_path).
:- run_tests.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment