Successor in BST
havanakoda
Given the type BST as : Void | Node a (BST a) (BST a), i have to
rewrite a BST with integer values, in an equivalent BSt that has the
couple Node (x, succ x), where succ x is the successor of x in the
BST.
How i can do?
Mark T.B. Carroll
I am not sure that I understand.
So, for example, if you had a tree like,
let x = Node 4 (Node 2 Void Void) (Node 7 Void Void)
you want to write an f so that,
f x == Node (4,5) (Node (2,3) Void Void) (Node (7,8) Void Void)
... ?
Mark
havanakoda
Now i will explain it better:
if i have a tree like
let x = Node 4 (Node 2 Void Void) (Node 5 Void Void)
i want that the function rewrites the tree in this way:
Node (4,5) (Node (2,4) Void Void) (Node (5,Nothing) Void Void)
The second element in the couple is the successor in the BST of the
first element.
Thanks
Mark T.B. Carroll
> if i have a tree like
> let x = Node 4 (Node 2 Void Void) (Node 5 Void Void)
> i want that the function rewrites the tree in this way:
> Node (4,5) (Node (2,4) Void Void) (Node (5,Nothing) Void Void)
>
> The second element in the couple is the successor in the BST of the
> first element.
Okay, I have some code now that does that. But is this homework? If so,
it might be helpful if you could tell us a little about where you're
having trouble. Do you have a good idea where to start yet? What have
you figured out about the algorithm you'll need?
For what it's worth, I'll hint at the approach I took:
I wrote functions,
smallest :: BST a -> Maybe a
which, given a tree, returns its smallest element.
remap :: BST a -> BST (a, Maybe a)
which does what you want, with the help of,
remap' :: Maybe a -> BST a -> BST (a, Maybe a)
which is given a Nothing only down the right side of the tree.
and I found a couple of uses for Control.Monad.mplus.
Mark
Mark T.B. Carroll
> remap' :: Maybe a -> BST a -> BST (a, Maybe a)
> which is given a Nothing only down the right side of the tree.
... just at the very right edge, I mean.
Mark
Lutz Donnerhacke
> if i have a tree like
> let x = Node 4 (Node 2 Void Void) (Node 5 Void Void)
> i want that the function rewrites the tree in this way:
> Node (4,5) (Node (2,4) Void Void) (Node (5,Nothing) Void Void)
>
> The second element in the couple is the successor in the BST of the
> first element.
Successor is in the context of an inorder traversal?
Then Zippers might be the natural way to solve the problem:
http://www.haskell.org/haskellwiki/Zipper
http://en.wikibooks.org/wiki/Haskell/Zippers
Implementation:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/rosezipper
havanakoda
Yes, in the context of an inorder traversal. So in my example 5 is the
successor of 4.
Dirk Thierbach
> * havanakoda wrote:
>> if i have a tree like
>> let x = Node 4 (Node 2 Void Void) (Node 5 Void Void)
>> i want that the function rewrites the tree in this way:
>> Node (4,5) (Node (2,4) Void Void) (Node (5,Nothing) Void Void)
>> The second element in the couple is the successor in the BST of the
>> first element.
> Successor is in the context of an inorder traversal?
>
> Then Zippers might be the natural way to solve the problem:
Nah, that's overkill and probably slower, too. There's a much simpler
solution.
But as Mark has said, that looks suspicously like homework, so
havanakoda should either convince us that it's not homework by telling
us what he/she needs it for, or he/she should tell us what he/she
has done so far, and where he/she is stuck. (In the latter case,
there's also the chance the teacher may be reading this NG ...)
- Dirk
Mark T.B. Carroll
I figure that enough time has passed that I can post the solution I came
up with, for criticism by others:
import Control.Monad (mplus)
data BST a = Void | Node a (BST a) (BST a) deriving Show
smallest Void = Nothing
smallest (Node value left _) = mplus (smallest left) (Just value)
remap tree =
remap' (smallest tree) Nothing tree
where
remap' :: Maybe a -- smallest in given tree
-> Maybe a -- successor to largest in given tree
-> BST a -- given tree
-> BST (a, Maybe a)
remap' _ _ Void = Void
remap' smaller larger (Node value left right) =
Node (value, mplus (smallest right) larger)
(remap' smaller (Just value) left)
(remap' (smallest right) larger right)
Mark
Dirk Thierbach
>> Hi, i'm programming with Haskell and i have to resolve this problem:
>> Given the type BST as : Void | Node a (BST a) (BST a), i have to
>> rewrite a BST with integer values, in an equivalent BSt that has the
>> couple Node (x, succ x), where succ x is the successor of x in the
>> BST.
>> How i can do?
> I figure that enough time has passed that I can post the solution I came
> up with,
I guess so, the lecture seems to have moved on from binary trees to
quadtrees :-)
> import Control.Monad (mplus)
>
> data BST a = Void | Node a (BST a) (BST a) deriving Show
>
> smallest Void = Nothing
> smallest (Node value left _) = mplus (smallest left) (Just value)
>
> remap tree =
> remap' (smallest tree) Nothing tree
> where
> remap' :: Maybe a -- smallest in given tree
> -> Maybe a -- successor to largest in given tree
> -> BST a -- given tree
> -> BST (a, Maybe a)
> remap' _ _ Void = Void
> remap' smaller larger (Node value left right) =
> Node (value, mplus (smallest right) larger)
> (remap' smaller (Just value) left)
> (remap' (smallest right) larger right)
One can do that without mplus and with one recursive call along the
tree structure instead of two (both remap' and smallest). Shall I post
code, or do you want to puzzle for yourself?
Nice exercise, BTW. The other one with the quadtrees is also nice.
Whoever does the lecture has got good taste.
- Dirk
Mark T.B. Carroll
> I guess so, the lecture seems to have moved on from binary trees to
> quadtrees :-)
Indeed, and that a few days ago.
> One can do that without mplus and with one recursive call along the
> tree structure instead of two (both remap' and smallest). Shall I post
> code, or do you want to puzzle for yourself?
remap Void = Void
remap tree =
snd (remap' Nothing tree)
where
remap' largerAbove (Node value left right) =
let (smaller, left') = maybeRemap (Just value) left
(larger, right') = maybeRemap largerAbove right
in (smaller, Node (value, larger) left' right')
maybeRemap value Void = (value, Void)
maybeRemap value tree = remap' value tree
is my next attempt. (-: I'm still trying to convince myself it's
correct.
> Nice exercise, BTW. The other one with the quadtrees is also nice.
I wonder what improvements you will have in mind for my solution to
that. I recursed twice again!
Mark
Mark T.B. Carroll
> Dirk Thierbach <dthie...@usenet.arcornews.de> writes:
>> Nice exercise, BTW. The other one with the quadtrees is also nice.
>
> I wonder what improvements you will have in mind for my solution to
> that. I recursed twice again!
Okay, now down to once. Not sure about if it could be more efficent
though.
Mark
Dirk Thierbach
>> I guess so, the lecture seems to have moved on from binary trees to
>> quadtrees :-)
> Indeed, and that a few days ago.
I'm not so sure know. My Italian isn't good enough to understand
all details, but possibly the students can hand in all the exercises
at the end.
> remap Void = Void
>
> remap tree =
> snd (remap' Nothing tree)
> where
> remap' largerAbove (Node value left right) =
> let (smaller, left') = maybeRemap (Just value) left
> (larger, right') = maybeRemap largerAbove right
> in (smaller, Node (value, larger) left' right')
> maybeRemap value Void = (value, Void)
> maybeRemap value tree = remap' value tree
>
> is my next attempt.
Nearly there. Now get rid of "maybeRemap" by figuring out how to
handle "remap' x Void". Then make sure the corner cases don't cause
problems (because of lazyness).
> I'm still trying to convince myself it's correct.
Try to visualize the whole process ("think about the whole" is
always a good trick for Haskell): Every value has to move one
step to the left in the whole tree. If you draw the tree, and
the movement as arrows following the tree structure, you'll see
that the dataflow at the interior nodes corresponds exactly to the
program above.
> I wonder what improvements you will have in mind for my solution to
> that. I recursed twice again!
No, you didn't :-) "maybeRemap" is just an intermediate step, it doesn't
recurse itself.
Followup question: Can the three exercises be represented as a
fold over the respective tree structure?
(BTW, Andrea, this is how a discussion about an exercise should look
like: One person comes up with a partial solution, and then others
can help with particular points. In that way, the one person learns
a lot more than just by copying a ready-made solution.)
- Dirk
Dirk Thierbach
>> I guess so, the lecture seems to have moved on from binary trees to
>> quadtrees :-)
> Indeed, and that a few days ago.
I'm not so sure now. My Italian isn't good enough to understand
all details, but possibly the students can hand in all the exercises
at the end.
> remap Void = Void
>
> remap tree =
> snd (remap' Nothing tree)
> where
> remap' largerAbove (Node value left right) =
> let (smaller, left') = maybeRemap (Just value) left
> (larger, right') = maybeRemap largerAbove right
> in (smaller, Node (value, larger) left' right')
> maybeRemap value Void = (value, Void)
> maybeRemap value tree = remap' value tree
>
> is my next attempt.
Nearly there. Now get rid of "maybeRemap" by figuring out how to
handle "remap' x Void". Then make sure the corner cases don't cause
problems (because of lazyness).
> I'm still trying to convince myself it's correct.
Try to visualize the whole process ("think about the whole" is
always a good trick for Haskell): Every value has to move one
step to the left in the whole tree. If you draw the tree, and
the movement as arrows following the tree structure, you'll see
that the dataflow at the interior nodes corresponds exactly to the
program above.
> I wonder what improvements you will have in mind for my solution to
> that. I recursed twice again!
No, you didn't :-) "maybeRemap" is just an intermediate step, it doesn't
Mark T.B. Carroll
> Mark T.B. Carroll <Mark.C...@aetion.com> wrote:
>> Dirk Thierbach <dthie...@usenet.arcornews.de> writes:
>
>>> I guess so, the lecture seems to have moved on from binary trees to
>>> quadtrees :-)
>
>> Indeed, and that a few days ago.
>
> I'm not so sure now. My Italian isn't good enough to understand
> all details,
It is probably better than my Italian. (-:
> but possibly the students can hand in all the exercises at the end.
Oh, what a good point but an awkward possibility. I wonder how long to
embargo my attempts for then.
>> remap Void = Void
>>
>> remap tree =
>> snd (remap' Nothing tree)
>> where
>> remap' largerAbove (Node value left right) =
>> let (smaller, left') = maybeRemap (Just value) left
>> (larger, right') = maybeRemap largerAbove right
>> in (smaller, Node (value, larger) left' right')
>> maybeRemap value Void = (value, Void)
>> maybeRemap value tree = remap' value tree
>>
>> is my next attempt.
>
> Nearly there. Now get rid of "maybeRemap" by figuring out how to
> handle "remap' x Void".
Now I'm at,
remap tree =
snd (remap' Nothing tree)
where
remap' value Void = (value, Void)
remap' largerAbove (Node value left right) =
let (smaller, left') = remap' (Just value) left
(larger, right') = remap' largerAbove right
in (smaller, Node (value, larger) left' right')
> Then make sure the corner cases don't cause problems (because of
> lazyness).
... but you've got me worried here. (-:
> Try to visualize the whole process ("think about the whole" is
> always a good trick for Haskell): Every value has to move one
> step to the left in the whole tree. If you draw the tree, and
> the movement as arrows following the tree structure, you'll see
> that the dataflow at the interior nodes corresponds exactly to the
> program above.
Oh, that's an interesting approach. Thank you.
>> I wonder what improvements you will have in mind for my solution to
>> that. I recursed twice again!
>
> No, you didn't :-) "maybeRemap" is just an intermediate step, it doesn't
> recurse itself.
I was thinking of my QuadTree attempt. Except I since got rid of that
second recursion. (-: I fear it looks a bit ugly though.
> Followup question: Can the three exercises be represented as a
> fold over the respective tree structure?
A /fold/? Gosh. Do you mean, with actually flattening the tree in the
interim, and rebuilding it from scratch incrementally?
Mark
Dirk Thierbach
> Oh, what a good point but an awkward possibility. I wonder how long to
> embargo my attempts for then.
The problems already discussed are solved anyway, so I say for those it
doesn't matter.
> remap tree =
> snd (remap' Nothing tree)
> where
> remap' value Void = (value, Void)
> remap' largerAbove (Node value left right) =
> let (smaller, left') = remap' (Just value) left
> (larger, right') = remap' largerAbove right
> in (smaller, Node (value, larger) left' right')
Yep. Same as mine, modulo some style differences.
>> Then make sure the corner cases don't cause problems (because of
>> lazyness).
> ... but you've got me worried here. (-:
Sorry, "lazyness" was maybe a red herring. The Void case for remap'
works fine in a larger tree, because it just returns the values
from "above". My "make sure corner cases also work" reflex says that
one should inspect the Void case for the outer remap also (which
is fine, but one has to spend 5 seconds to think about it).
The obvious follow-up exercise is to combine the BST and the Quadtree
ideas and write a function to, say, not only shift each element of
the BST, but rotate it. For example,
4 5
/ \ / \
2 5 becomes 3 1
/ \ / \
1 3 2 4
Again with visiting each node only once. Isn't lazyness fun? :-)
>> Followup question: Can the three exercises be represented as a
>> fold over the respective tree structure?
> A /fold/? Gosh. Do you mean, with actually flattening the tree in the
> interim, and rebuilding it from scratch incrementally?
More or less. I meant anything that can be expressed with the folding
"recursion scheme", in the sense that "foldr (:) []" is also a fold,
though the result is a list.
What I'm aiming at is that some are, some aren't, but the ones which
aren't still look somewhat similar to a fold. So if it's not a fold,
what is it? Some sort of bi-fold? It doesn't look like a catamorphism
or hylomorphism, either (though I may be wrong here). Folds have a
nice characterization as F-algebras, and it looks like one should be
able to do something similar here, but I don't see exactly how.
- Dirk
Mark T.B. Carroll
> Mark T.B. Carroll <Mark.C...@aetion.com> wrote:
>> Oh, what a good point but an awkward possibility. I wonder how long to
>> embargo my attempts for then.
>
> The problems already discussed are solved anyway, so I say for those it
> doesn't matter.
Ah, okay, I'll go ahead and dig out the ugly QuadTree thing I did then
to see where it could be improved.
> The Void case for remap' works fine in a larger tree, because it just
> returns the values from "above". My "make sure corner cases also work"
> reflex says that one should inspect the Void case for the outer remap
> also (which is fine, but one has to spend 5 seconds to think about
> it).
Yes, very true. I did indeed have to think about that. (-:
> The obvious follow-up exercise is to combine the BST and the Quadtree
> ideas and write a function to, say, not only shift each element of
> the BST, but rotate it. For example,
>
> 4 5
> / \ / \
> 2 5 becomes 3 1
> / \ / \
> 1 3 2 4
>
> Again with visiting each node only once. Isn't lazyness fun? :-)
Oh, yes, that's a nice problem! The wraparound from end to beginning is
a great wrinkle.
(snip)
> What I'm aiming at is that some are, some aren't, but the ones which
> aren't still look somewhat similar to a fold. So if it's not a fold,
> what is it? Some sort of bi-fold? It doesn't look like a catamorphism
> or hylomorphism, either (though I may be wrong here). Folds have a
> nice characterization as F-algebras, and it looks like one should be
> able to do something similar here, but I don't see exactly how.
Yes, you may be correct. Though this reminds me of the Applicative and
Traversable classes which, to my embarrassment, I've not yet properly
got my head around: I would wonder if I should wheel out either or both
of those in an attempt at some solution.
Mark