I have written a data structure,
data Bit a = Add a (Bit a) | End deriving (Show,Eq)
data Bits a = Bits (Bit a) (Bit a) deriving (Show,Eq)
but am struggling to create a map and foldr function for them.
So far I have this:
instance Functor Bit
where
fmap _ (End) = End
fmap f (Add x (y)) = Add (f x) $ (fmap f y)
instance Foldable Bit
where
foldr _ z (End) = z
foldr f z (Add x (y)) = f x $ foldr f z y
instance Functor Bits
where
fmap _ (Bits (End) (End)) = Bits (End) (End)
fmap f (Bits (Add x (y)) (End)) = error "dont know what to put here"
instance Foldable Bits
where
foldr _ z (Bits (End) (End)) = z
foldr f z (Bits (Add x (y)) (End) = Bits (f x $ f y) (End)
foldr f z (Bits (Add x (y)) (Add a (b)) = error "dont know"
Any idea on how to implement them? Also not sure if I am missing anything so please let me know if that is also the case.
Perhaps it's easier to implement the Foldable instances via foldMap:
import Data.Monoid
data Bit a = Add a (Bit a) | End deriving (Show,Eq)
data Bits a = Bits (Bit a) (Bit a) deriving (Show,Eq)
instance Functor Bit where
fmap _ End = End
fmap f (Add x b) = Add (f x) $ fmap f b
instance Foldable Bit where
foldMap _ End = mempty
foldMap f (Add x b) = f x <> foldMap f b
instance Functor Bits where
fmap f (Bits l r) = Bits (fmap f l) (fmap f r)
instance Foldable Bits where
foldMap f (Bits l r) = foldMap f l <> foldMap f r
Here's some GHCi examples:
*Q51009307> foldr (\x a -> show x ++ a) "" $ End
""
*Q51009307> foldr (\x a -> show x ++ a) "" $ Add 1 $ End
"1"
*Q51009307> foldr (\x a -> show x ++ a) "" $ Add 1 $ Add 2 $ End
"12"
*Q51009307> foldr (\x a -> show x ++ a) "" $ Add 1 $ Add 2 $ Add 3 $ End
"123"
*Q51009307> foldMap Sum $ Bits (Add 1 $ End) End
Sum {getSum = 1}
*Q51009307> foldMap Sum $ Bits (Add 1 $ Add 2 $ End) (Add 1 $ End)
Sum {getSum = 4}
*Q51009307> foldr (+) 0 $ Bits (Add 1 $ Add 2 $ End) (Add 1 $ End)
4