Extract the minimum value of a Prolog tree
I'm a very Prolog beginner, so this question might be and become useless, anyway I have defined a Prolog tree as follows:
type([null, tree(T, tree(T), tree(T))]:tree(T)).
which means that a tree is either null or has a left subtree and a right subtree.
I have then defined a predicate that should output the minimum node value of that tree, which is:
pred(min(tree(T), integer)).
%% (++ --)
pred(calc_min(integer, integer, integer, integer)).
%% (++, ++, ++, --)
min(tree(Root, null, null), Root).
min(tree(Root, Left, Right), Result):-
min(Left, LeftRes),
min(Right, RightRes),
calc_min(Root, LeftRes, RightRes, Result).
I think I have to define the base clause where the tree is the null tree, but I don't know what to output.
prolog
edited Nov 22 '18 at 19:04
false
11.5k772148
asked Nov 20 '18 at 18:09
davide m.davide m.
277
add a comment |
I'm a very Prolog beginner, so this question might be and become useless, anyway I have defined a Prolog tree as follows:
type([null, tree(T, tree(T), tree(T))]:tree(T)).
which means that a tree is either null or has a left subtree and a right subtree.
I have then defined a predicate that should output the minimum node value of that tree, which is:
pred(min(tree(T), integer)).
%% (++ --)
pred(calc_min(integer, integer, integer, integer)).
%% (++, ++, ++, --)
min(tree(Root, null, null), Root).
min(tree(Root, Left, Right), Result):-
min(Left, LeftRes),
min(Right, RightRes),
calc_min(Root, LeftRes, RightRes, Result).
I think I have to define the base clause where the tree is the null tree, but I don't know what to output.
prolog
edited Nov 22 '18 at 19:04
false
11.5k772148
asked Nov 20 '18 at 18:09
davide m.davide m.
277
1
"but I don't know what to output." - we don't know what your code should do either. What do you want the minimum value of a null tree to be?
– TessellatingHeckler
Nov 20 '18 at 18:23
Of interest: RosettaCode TreeTraversal in Prolog
– Guy Coder
Nov 20 '18 at 19:04
1
An empty (null) tree has no minimum since it has no values. Your base case should be the simplest possible tree that has a minimum. Also, check the logic in your recursivemin/2clause. After you compute the left and right minimums, what should the minimum of the resulting tree be? HINT: it's not a big calculation. You're considering 3 values: the root value, the left value, and the right value.
– lurker
Nov 20 '18 at 19:43
See also stackoverflow.com/questions/53405266/…
– Paulo Moura
Nov 21 '18 at 10:40
add a comment |
I'm a very Prolog beginner, so this question might be and become useless, anyway I have defined a Prolog tree as follows:
type([null, tree(T, tree(T), tree(T))]:tree(T)).
which means that a tree is either null or has a left subtree and a right subtree.
I have then defined a predicate that should output the minimum node value of that tree, which is:
pred(min(tree(T), integer)).
%% (++ --)
pred(calc_min(integer, integer, integer, integer)).
%% (++, ++, ++, --)
min(tree(Root, null, null), Root).
min(tree(Root, Left, Right), Result):-
min(Left, LeftRes),
min(Right, RightRes),
calc_min(Root, LeftRes, RightRes, Result).
I think I have to define the base clause where the tree is the null tree, but I don't know what to output.
prolog
edited Nov 22 '18 at 19:04
false
11.5k772148
asked Nov 20 '18 at 18:09
davide m.davide m.
277
I'm a very Prolog beginner, so this question might be and become useless, anyway I have defined a Prolog tree as follows:
type([null, tree(T, tree(T), tree(T))]:tree(T)).
which means that a tree is either null or has a left subtree and a right subtree.
I have then defined a predicate that should output the minimum node value of that tree, which is:
pred(min(tree(T), integer)).
%% (++ --)
pred(calc_min(integer, integer, integer, integer)).
%% (++, ++, ++, --)
min(tree(Root, null, null), Root).
min(tree(Root, Left, Right), Result):-
min(Left, LeftRes),
min(Right, RightRes),
calc_min(Root, LeftRes, RightRes, Result).
I think I have to define the base clause where the tree is the null tree, but I don't know what to output.
prolog
prolog
edited Nov 22 '18 at 19:04
false
11.5k772148
asked Nov 20 '18 at 18:09
davide m.davide m.
277
edited Nov 22 '18 at 19:04
false
11.5k772148
asked Nov 20 '18 at 18:09
davide m.davide m.
277
edited Nov 22 '18 at 19:04
false
11.5k772148
edited Nov 22 '18 at 19:04
false
11.5k772148
edited Nov 22 '18 at 19:04
false
11.5k772148
11.5k772148
asked Nov 20 '18 at 18:09
davide m.davide m.
277
asked Nov 20 '18 at 18:09
davide m.davide m.
277
asked Nov 20 '18 at 18:09
davide m.davide m.
277
277
1
"but I don't know what to output." - we don't know what your code should do either. What do you want the minimum value of a null tree to be?
– TessellatingHeckler
Nov 20 '18 at 18:23
Of interest: RosettaCode TreeTraversal in Prolog
– Guy Coder
Nov 20 '18 at 19:04
1
An empty (null) tree has no minimum since it has no values. Your base case should be the simplest possible tree that has a minimum. Also, check the logic in your recursivemin/2clause. After you compute the left and right minimums, what should the minimum of the resulting tree be? HINT: it's not a big calculation. You're considering 3 values: the root value, the left value, and the right value.
– lurker
Nov 20 '18 at 19:43
See also stackoverflow.com/questions/53405266/…
– Paulo Moura
Nov 21 '18 at 10:40
add a comment |
1
"but I don't know what to output." - we don't know what your code should do either. What do you want the minimum value of a null tree to be?
– TessellatingHeckler
Nov 20 '18 at 18:23
Of interest: RosettaCode TreeTraversal in Prolog
– Guy Coder
Nov 20 '18 at 19:04
1
An empty (null) tree has no minimum since it has no values. Your base case should be the simplest possible tree that has a minimum. Also, check the logic in your recursivemin/2clause. After you compute the left and right minimums, what should the minimum of the resulting tree be? HINT: it's not a big calculation. You're considering 3 values: the root value, the left value, and the right value.
– lurker
Nov 20 '18 at 19:43
See also stackoverflow.com/questions/53405266/…
– Paulo Moura
Nov 21 '18 at 10:40
1
1
"but I don't know what to output." - we don't know what your code should do either. What do you want the minimum value of a null tree to be?
– TessellatingHeckler
Nov 20 '18 at 18:23
"but I don't know what to output." - we don't know what your code should do either. What do you want the minimum value of a null tree to be?
– TessellatingHeckler
Nov 20 '18 at 18:23
Of interest: RosettaCode TreeTraversal in Prolog
– Guy Coder
Nov 20 '18 at 19:04
Of interest: RosettaCode TreeTraversal in Prolog
– Guy Coder
Nov 20 '18 at 19:04
1
1
An empty (null) tree has no minimum since it has no values. Your base case should be the simplest possible tree that has a minimum. Also, check the logic in your recursive
min/2 clause. After you compute the left and right minimums, what should the minimum of the resulting tree be? HINT: it's not a big calculation. You're considering 3 values: the root value, the left value, and the right value.– lurker
Nov 20 '18 at 19:43
An empty (null) tree has no minimum since it has no values. Your base case should be the simplest possible tree that has a minimum. Also, check the logic in your recursive
min/2 clause. After you compute the left and right minimums, what should the minimum of the resulting tree be? HINT: it's not a big calculation. You're considering 3 values: the root value, the left value, and the right value.– lurker
Nov 20 '18 at 19:43
See also stackoverflow.com/questions/53405266/…
– Paulo Moura
Nov 21 '18 at 10:40
See also stackoverflow.com/questions/53405266/…
– Paulo Moura
Nov 21 '18 at 10:40
add a comment |
1 Answer
1
active
oldest
votes
Oh, nice tree. It is easy to get min of tree but if you want to really get it you need other predicate to help first predicate find min of tree.
min(tree(X, L, _R), Min) :- min_helper(L, X, Min).
min_helper(null, X, X).
min_helper(tree(X, L, _R), _X0, Min) :- min_helper(L, X, Min).
But this only work if binary tree is search tree. Is your tree binary search tree? If not binary tree then not so easy to get min of tree. But you make it difficult because you want min of value AND left min AND right min but this is too difficult. But you say is integer tree so again not so difficult.
min(null, null).
min(tree(X, L, R), Min) :-
min(L, LMin),
min(R, RMin),
min_with_null(X, LMin, Min0),
min_with_null(Min0, RMin, Min).
min_with_null(X, Maybe_null, Min) :-
( Maybe_null == null
-> Min = X
; Min is min(X, Maybe_null)
).
But what is min of null?
?- min(null, Min).
Min = null.
I check if null but I no check if integer because you write something and it says is integer. But are you sure?
And what is min of some other tree?
?- min(tree(1, null, null), Min).
Min = 1.
?- min(tree(1, tree(0, null, null), null), Min).
Min = 0.
?- min(tree(0, tree(1, null, null), null), Min).
Min = 0.
?- min(tree(1, null, tree(0, null, null)), Min).
Min = 0.
?- min(tree(0, null, tree(1, null, null)), Min).
Min = 0.
?- min(tree(1, tree(2, null, null), tree(3, null, null)), Min).
Min = 1.
Did I forget test case? I don't know.
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53399006%2fextract-the-minimum-value-of-a-prolog-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Oh, nice tree. It is easy to get min of tree but if you want to really get it you need other predicate to help first predicate find min of tree.
min(tree(X, L, _R), Min) :- min_helper(L, X, Min).
min_helper(null, X, X).
min_helper(tree(X, L, _R), _X0, Min) :- min_helper(L, X, Min).
But this only work if binary tree is search tree. Is your tree binary search tree? If not binary tree then not so easy to get min of tree. But you make it difficult because you want min of value AND left min AND right min but this is too difficult. But you say is integer tree so again not so difficult.
min(null, null).
min(tree(X, L, R), Min) :-
min(L, LMin),
min(R, RMin),
min_with_null(X, LMin, Min0),
min_with_null(Min0, RMin, Min).
min_with_null(X, Maybe_null, Min) :-
( Maybe_null == null
-> Min = X
; Min is min(X, Maybe_null)
).
But what is min of null?
?- min(null, Min).
Min = null.
I check if null but I no check if integer because you write something and it says is integer. But are you sure?
And what is min of some other tree?
?- min(tree(1, null, null), Min).
Min = 1.
?- min(tree(1, tree(0, null, null), null), Min).
Min = 0.
?- min(tree(0, tree(1, null, null), null), Min).
Min = 0.
?- min(tree(1, null, tree(0, null, null)), Min).
Min = 0.
?- min(tree(0, null, tree(1, null, null)), Min).
Min = 0.
?- min(tree(1, tree(2, null, null), tree(3, null, null)), Min).
Min = 1.
Did I forget test case? I don't know.
add a comment |
Oh, nice tree. It is easy to get min of tree but if you want to really get it you need other predicate to help first predicate find min of tree.
min(tree(X, L, _R), Min) :- min_helper(L, X, Min).
min_helper(null, X, X).
min_helper(tree(X, L, _R), _X0, Min) :- min_helper(L, X, Min).
But this only work if binary tree is search tree. Is your tree binary search tree? If not binary tree then not so easy to get min of tree. But you make it difficult because you want min of value AND left min AND right min but this is too difficult. But you say is integer tree so again not so difficult.
min(null, null).
min(tree(X, L, R), Min) :-
min(L, LMin),
min(R, RMin),
min_with_null(X, LMin, Min0),
min_with_null(Min0, RMin, Min).
min_with_null(X, Maybe_null, Min) :-
( Maybe_null == null
-> Min = X
; Min is min(X, Maybe_null)
).
But what is min of null?
?- min(null, Min).
Min = null.
I check if null but I no check if integer because you write something and it says is integer. But are you sure?
And what is min of some other tree?
?- min(tree(1, null, null), Min).
Min = 1.
?- min(tree(1, tree(0, null, null), null), Min).
Min = 0.
?- min(tree(0, tree(1, null, null), null), Min).
Min = 0.
?- min(tree(1, null, tree(0, null, null)), Min).
Min = 0.
?- min(tree(0, null, tree(1, null, null)), Min).
Min = 0.
?- min(tree(1, tree(2, null, null), tree(3, null, null)), Min).
Min = 1.
Did I forget test case? I don't know.
add a comment |
Oh, nice tree. It is easy to get min of tree but if you want to really get it you need other predicate to help first predicate find min of tree.
min(tree(X, L, _R), Min) :- min_helper(L, X, Min).
min_helper(null, X, X).
min_helper(tree(X, L, _R), _X0, Min) :- min_helper(L, X, Min).
But this only work if binary tree is search tree. Is your tree binary search tree? If not binary tree then not so easy to get min of tree. But you make it difficult because you want min of value AND left min AND right min but this is too difficult. But you say is integer tree so again not so difficult.
min(null, null).
min(tree(X, L, R), Min) :-
min(L, LMin),
min(R, RMin),
min_with_null(X, LMin, Min0),
min_with_null(Min0, RMin, Min).
min_with_null(X, Maybe_null, Min) :-
( Maybe_null == null
-> Min = X
; Min is min(X, Maybe_null)
).
But what is min of null?
?- min(null, Min).
Min = null.
I check if null but I no check if integer because you write something and it says is integer. But are you sure?
And what is min of some other tree?
?- min(tree(1, null, null), Min).
Min = 1.
?- min(tree(1, tree(0, null, null), null), Min).
Min = 0.
?- min(tree(0, tree(1, null, null), null), Min).
Min = 0.
?- min(tree(1, null, tree(0, null, null)), Min).
Min = 0.
?- min(tree(0, null, tree(1, null, null)), Min).
Min = 0.
?- min(tree(1, tree(2, null, null), tree(3, null, null)), Min).
Min = 1.
Did I forget test case? I don't know.
Oh, nice tree. It is easy to get min of tree but if you want to really get it you need other predicate to help first predicate find min of tree.
min(tree(X, L, _R), Min) :- min_helper(L, X, Min).
min_helper(null, X, X).
min_helper(tree(X, L, _R), _X0, Min) :- min_helper(L, X, Min).
But this only work if binary tree is search tree. Is your tree binary search tree? If not binary tree then not so easy to get min of tree. But you make it difficult because you want min of value AND left min AND right min but this is too difficult. But you say is integer tree so again not so difficult.
min(null, null).
min(tree(X, L, R), Min) :-
min(L, LMin),
min(R, RMin),
min_with_null(X, LMin, Min0),
min_with_null(Min0, RMin, Min).
min_with_null(X, Maybe_null, Min) :-
( Maybe_null == null
-> Min = X
; Min is min(X, Maybe_null)
).
But what is min of null?
?- min(null, Min).
Min = null.
I check if null but I no check if integer because you write something and it says is integer. But are you sure?
And what is min of some other tree?
?- min(tree(1, null, null), Min).
Min = 1.
?- min(tree(1, tree(0, null, null), null), Min).
Min = 0.
?- min(tree(0, tree(1, null, null), null), Min).
Min = 0.
?- min(tree(1, null, tree(0, null, null)), Min).
Min = 0.
?- min(tree(0, null, tree(1, null, null)), Min).
Min = 0.
?- min(tree(1, tree(2, null, null), tree(3, null, null)), Min).
Min = 1.
Did I forget test case? I don't know.
edited Nov 21 '18 at 4:16
answered Nov 21 '18 at 2:44
user10631003
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53399006%2fextract-the-minimum-value-of-a-prolog-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
"but I don't know what to output." - we don't know what your code should do either. What do you want the minimum value of a null tree to be?
– TessellatingHeckler
Nov 20 '18 at 18:23
Of interest: RosettaCode TreeTraversal in Prolog
– Guy Coder
Nov 20 '18 at 19:04
1
An empty (null) tree has no minimum since it has no values. Your base case should be the simplest possible tree that has a minimum. Also, check the logic in your recursive
min/2clause. After you compute the left and right minimums, what should the minimum of the resulting tree be? HINT: it's not a big calculation. You're considering 3 values: the root value, the left value, and the right value.– lurker
Nov 20 '18 at 19:43
See also stackoverflow.com/questions/53405266/…
– Paulo Moura
Nov 21 '18 at 10:40