Haskell functor for red and black wood

Question

So, I am studying Haskell, and I have a red-black tree with different types in red and black nodes, implemented like this:

data Rbtree a1 b1 = EmptyTree | Node a1 (Rbtree b1 a1) (Rbtree b1 a1) deriving (Show, Read, Eq)

And now I need to define an instance of a functor for it. Since it Rbtreeis a type constructor that takes two parameters, I have to make an instance for Rbtree c. And after that I got stuck. Now my code looks something like this:

instance Functor (Rbtree c) where
fmap f EmptyTree = EmptyTree
fmap f (Node x left right) = Node x (fmap f left) (fmap f right)

As you might have guessed, that does not compile. ( compilation errors ). I understand that it fmapmust be for him (a -> b) -> (Rbtree c) a -> (Rbtree c) band for the deeper part Nodeshould be (a -> b) -> (Node c (Rbtree a c) (Rbree a c)) -> (Node c (Rbtree b c) (Rbree b c)). I do not understand how to deploy leftand right, therefore, I can fonly apply to part of it. I think something is missing here.

Answer 1

instance Functor (Rbtree c) where
  fmap = fmap_even where
     fmap_even _ EmptyTree = EmptyTree
     fmap_even f (Node x left right) = Node x (fmap_odd f left) (fmap_odd f right)
     fmap_odd  _ EmptyTree = EmptyTree
     fmap_odd  f (Node x left right) = Node (f x) (fmap_even f left) (fmap_even f right)

Your definition of the RB tree does not make much sense to me, but if I missed something, here is an instance of Functor that is compatible with it.

Answer 2

You can make your Rbtreea Bifunctor(see bifunctorspackage ) as follows:

import Data.Bifunctor

data Rbtree a1 b1 = EmptyTree | Node a1 (Rbtree b1 a1) (Rbtree b1 a1)

instance Bifunctor Rbtree where
  bimap _ _ EmptyTree = EmptyTree
  bimap f g (Node x l r) = Node (f x) (bimap g f l) (bimap g f r)

With that instance, you now have a function firstand secondto display on red or black knots ( second~ fmap). In fact, you can define an instance Functoras follows:

instance Functor (Rbtree c) where
  fmap = second

---

Example

>>> let t = Node 1 (Node "hello" EmptyTree EmptyTree) EmptyTree
>>> bimap show length t
Node "1" (Node 5 EmptyTree EmptyTree) EmptyTree
>>> fmap length t
Node 1 (Node 5 EmptyTree EmptyTree) EmptyTree
>>> first show t
Node "1" (Node "hello" EmptyTree EmptyTree) EmptyTree

Answer 3

- , GADTs ( , , ). :

• A node , .
• .
• (NIL) .
• Each red node must have two black child nodes.
• Each path from a given node to any of its descendants leaves contain the same number of black nodes.

And here is a sample code:

{-# LANGUAGE GADTs, StandaloneDeriving, ExistentialQuantification,
             KindSignatures, DataKinds #-}

data Nat = Zero | Succ Nat
data Color = Red | Black

data Node :: Color -> Nat -> * -> * where
    Nil :: Node Black Zero a
    RedNode :: a -> Node Black n a -> Node Black n a -> Node Red n a
    BlackNode :: a -> Node c1 n a -> Node c2 n a -> Node Black (Succ n) a

data RBTree a = forall n. RBTree (Node Black n a)

deriving instance (Show a) => Show (Node c n a)
deriving instance (Show a) => Show (RBTree a)

instance Functor (Node c n) where
    fmap f Nil = Nil
    fmap f (RedNode   x l r) = RedNode   (f x) (fmap f l) (fmap f r)
    fmap f (BlackNode x l r) = BlackNode (f x) (fmap f l) (fmap f r)

instance Functor RBTree where
    fmap f (RBTree t) = RBTree (fmap f t)

You can use it as follows:

tree = RBTree $ BlackNode 3 (RedNode 4 Nil Nil) (RedNode 5 Nil Nil)
main = print $ fmap (*5) tree

Result:

RBTree (BlackNode 15 (RedNode 20 Nil Nil) (RedNode 25 Nil Nil))

But this does not compile:

tree = RBTree $ BlackNode 3 (RedNode 4 Nil Nil) (BlackNode 5 Nil Nil)

You will get a good error message:

Couldn't match type `Succ Zero' with `Zero'
Expected type: Node Black Zero a0
  Actual type: Node Black (Succ Zero) a0
In the return type of a call of `BlackNode'
In the third argument of `BlackNode', namely
  `(BlackNode 5 Nil Nil)'
In the second argument of `($)', namely
  `BlackNode 3 (RedNode 4 Nil Nil) (BlackNode 5 Nil Nil)'