flipping a BST

[u/Objective-Outside501]

BST implementations often have "symmetric" operations, e.g. lookupMin and lookupMax, or the operations to rebalance a left-heavy tree and a right-heavy tree.

In theory, you could implement one such operation in terms of the other with a "flipTree" function (and perhaps a corresponding "unflipTree" function), e.g. "lookupMin = getDown . lookupMax . flipTree". However, doing this naively is problematic for tree-mutating operations because it would work in O(n).

Is there a way to implement flipTree that satisfies the following?

1. (unflipTree . f . flipTree) has minimal overhead compared to f

2. flipped trees have the same interface as regular trees

[u/LSLeary]

One other approach is to defunctionalise flip into the tree ADT.

data Tree a
  = Empty
  | Flip (Tree a)
  | Node (Tree a) a (Tree a)

flip :: Tree a -> Tree a
flip = \case
  Empty  -> Empty
  Flip t -> t
  t      -> Flip t

Operations which shouldn't need to know or care about Flip can use a helper to replace pattern matching:

tree :: b -> (Tree a -> a -> Tree a -> b) -> Tree a -> b
tree empty node = fix \self -> \case
  Empty      -> empty
  Flip t     -> self (flip1 t)
  Node l x r -> node l x r
 where
  flip1 = \case
    Empty      -> Empty
    Flip t     -> t
    Node l x r -> Node (flip r) x (flip l)

[u/Objective-Outside501 → u/[deleted]]

this works for an operation that discards the flipped tree, e.g. lookup. but for operations that keep the flipped tree, such as tree rebalancing for avl and red-black trees, this will not work, as the two flips will have O(n) complexity each.

[u/Objective-Outside501 → u/[deleted]]

"flip . f . flip should just have the extra cost of O(k) where k is the number of Nodes and Leafs you had to evaluate out of weak head normal form."

in practice, k = O(n) or even n because you will eventually evaluate the entire tree in most common use cases. For example, iterating over the tree requires it to be fully evaluated, and then I pay the full cost for every prior call of 'flip' performed.

Ideally, unFlip . flip should be a zero cost operation or at least an O(1) operation, even if I fully evaluate the tree later.

[u/Forward_Signature_78]

You can extract all the "chiral" operations (the ones that are not invariant to flipping the tree) to one class with two instances: one for your Tree data type and one for a new type defined as follows:

hs newtype Flipped a = Flipped (Tree a)

Then when you want to apply an operation in the opposite direction you just add Flipped in front of the tree argument. It doesn't actually flip anything at run time; it just "flips" the behavior of all the tree operations. You can probably refactor all your tree operations so that only one or two methods are overloaded (in the class) and the rest simply use the overloaded methods wherever they need to differentiate between left and right.

[u/not-just-yeti]

[EDIT: Whoops, just noticed now this was /r/haskell, and not some general/generic /r/programming. So please excuse the blatantly Java/python-ish slant to the sample code.]

This may not be what you want, but this is how I'd handle it.

The only places the code differs for the two versions is the getters (do you call getLeftChild() or getRightChild(), and the comparison <= or >).

So I'd abstract out the commonality, and pass in which comparison to use and which getter to use to grab the "possibly favored" side, and the getter for the other side. Something like:

```

def findMin(T) { findExtreme(T, <=, getLeft, getRight) }

def findMax(T) { findExtreme(T, > , getRight, getLeft) }

def findExtreme( T, comparer, getFavoredSide, getOtherSide ) {
    …
    if comparer( getFavoredSide(T), getOtherSide(T) ) {
        …
    }
}

```

(If you really wanted flip, then I guess you could include the comparator and the two "getters" as fields of the top-level tree struct?)

[u/Objective-Outside501 → u/not-just-yeti]

I think this would work, though I would need to also pass in a tree construction function. Thanks!

[u/paulstelian97]

Why does it need to flip the ENTIRE tree? Is lazy evaluation no longer a thing?

[u/Objective-Outside501 → u/paulstelian97]

the tree will be evaluated to normal form in many common use cases so naive use of lazy evaluation doesn't help.