haskelltime-complexitybinary-treerecursion-schemes# Selectively recurse into left or right subtree of a binary tree using a catamorphism (or any recursion scheme)

I'm trying to implement a binary search tree (or set) using fixed points of functors. I've defined my fixed point as follows:

```
newtype Fix f = In (f (Fix f))
out :: Fix f -> f (Fix f)
out (In f) = f
-- Catamorphism
type Algebra f a = f a -> a
cata :: (Functor f) => Algebra f a -> Fix f -> a
cata f = f . fmap (cata f) . out
```

To make the binary tree, I'm using a red-black tree like so:

```
data NodeColor = Red | Black deriving (Eq, Show)
data RedBlackTreeF a r = EmptyRedBlackTreeF | RedBlackTreeNodeF NodeColor r a r deriving (Eq, Show)
instance Functor (RedBlackTreeF a) where
fmap _ EmptyRedBlackTreeF = EmptyRedBlackTreeF
fmap f (RedBlackTreeNodeF color r1 a r2) =
RedBlackTreeNodeF color (f r1) a (f r2)
type RedBlackTreeF' a = Fix (RedBlackTreeF a)
```

The traditional benefit of a binary tree is being able to cut down search time by choosing whether to search further in the left or right subtree like so (in psuedocode):

```
fun member (x, E) = false
| member (x, T (_, a, y, b)) =
if x < y then member (x, a)
else if x > y then member (x, b)
else true
```

The function `member`

will go left if the element that is being searched for is less than the current element and right if the opposite is true. It therefore improves search time to `O(logn)`

.

However, in a recursion scheme, the algebra is recursively applied to the entire data structure. I've written an `member`

algebra here:

```
memberPAlg :: Ord a => a -> RedBlackTreeF a Bool -> Bool
memberPAlg _ EmptyRedBlackTreeF = False
memberPAlg elem (RedBlackTreeNodeF _ left cur right) =
(elem == cur) || (left || right)
```

But it seems to be `O(nlogn)`

rather than `O(logn)`

. Is there any way to selectively recurse using a recursion scheme to save time complexity? Am I thinking about this the wrong way?

Solution

Because of laziness, `left`

and `right`

are evaluated only if you ask for them. So, just compare the current node with the value being searched for to decide which subtree to go into:

```
memberPAlg :: Ord a => a -> RedBlackTreeF a Bool -> Bool
memberPAlg _ EmptyRedBlackTreeF = False
memberPAlg elem (RedBlackTreeNodeF _ left cur right) =
case compare elem cur of
EQ -> True
LT -> left
GT -> right
```

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code