Toggle navigation
?
users online
Logout
Open hangout
Open chat for current file
% -*- mode: Prolog -*- % (This code, with unit tests, is also at https://gist.github.com/kamahen/e570d7b101a0344a56f71d05a831ea04 ) % 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. % (tree-path ‘(leaf 5) 5) => ‘(here) t1(Path) :- % 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) t2(Path) :- % Path = [right, 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) t3(Path) :- % 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) % ^^^^^ t4(Path) :- % 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) => ‘() t5(Path) :- % fail tree_path(node(10, node(5, empty, empty), node(20, node(12, empty, empty), empty)), 50, Path). /** <examples> ?- t4(Path). */