Haskell fmap functor

Question

I have a problem with functors over queue based on designated algebraic datastructures.

data DQueue a = Empty | Enqueue a (DQueue a)
    deriving (Eq, Show, Read)


instance Functor DQueue
  where
    fmap f (Enqueue x xs) = Enqueue (f x) $ fmap f xs

instance Foldable DQueue
  where
    foldr = error "not done"

sample1 :: DQueue Int
sample1 =  Enqueue 5 $ Enqueue 7 $ Enqueue 9 Empty

and result should be like that:

fmap (+1) sample1 ~?= Enqueue 6 (Enqueue 8 (Enqueue 10 Empty))
foldr (+) 0 sample1 ~?= 24

fmap seems to be logicaly correct but I get an error: Non-exhaustive patterns in function fmap

Thank you in advance.

Answer 1

Your Functor instance definition is non-exhaustive because it doesn't handle all possible type constructors of DQueue. Namely, it is missing a pattern matching Empty. You need to define how to handle fmap when your value is Empty.

Answer 2

The error speaks for itself: your definition for Functor is defined as:

data DQueue a = Empty | Enqueue a (DQueue a) deriving (Eq, Show, Read)

instance Functor DQueue where
    fmap f (Enqueue x xs) = Enqueue (f x) $ fmap f xs

There is however the possibility (in this case, if I understand your data-structure correctly, the certainty) that eventually fmap will be fed an Empty instance. You thus have to expand your definition to:

instance Functor DQueue where
    fmap f (Enqueue x xs) = Enqueue (f x) $ fmap f xs
    fmap _ Empty = Empty

---

Most compilers support a flag such that the compiler complains about non-exhaustive patterns, for the Glasgow Haskell Compiler (ghc), you can use the -fwarn-incomplete-patterns flag. For example:

$ ghc queue.hs -fwarn-incomplete-patterns
[1 of 1] Compiling Main             ( queue.hs, queue.o )

queue.hs:7:5: Warning:
    Pattern match(es) are non-exhaustive
    In an equation for ‘fmap’: Patterns not matched: _ Empty
Linking queue ...