CODEWITHSUNDEEP
haskellfunctional-programming
user6023611
user6023611

Reputation:

haskell, Functor for Data Binary Tree

I am trying to write functor for Tree (form of this type is given below)

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

instance Functor Tree where
    fmap f Empty = Empty
    fmap f (Node a x y) =  Node (f a) (fmap f x) (fmap f y)

It seems to be working, but what about more elegant (I am newbie in haskell) solutions? The second issue is that lecturer wrote signature: fmap :: (a -> b) -> f a -> f b for me, it is (a->b) -> Tree a -> Tree b, but it is not accepted by compiler ghci. Where is the point ?

Upvotes: 4

Views: 2947

Answers (2)

dfeuer
dfeuer

Reputation: 48631

Your solution is quite elegant. Another option is to define fmap using traverse:

import Data.Traversable

-- Preorder traversal based on the way you defined the Node constructor. Could use any traversal.
instance Traversable Tree where
  traverse _ Empty = pure Empty
  traverse f (Node v l r) = Node <$> f v <*> traverse f l <*> traverse f r 

instance Functor Tree where
  fmap = fmapDefault

instance Foldable Tree where
  foldMap = foldMapDefault

I wouldn't say this is more elegant, but if you want all these instances, and don't want to derive them it's a pithy way to do it.

Upvotes: 0

Zeta
Zeta

Reputation: 105975

what about more elegant [...] solutions?

It's perfectly fine. All other solutions that aren't using any helper functions will look more or less the same. The only thing I would change is the alignment of the =s and the names x and y as l and r (referring to the left and right branch):

instance Functor Tree where
  fmap _ Empty        = Empty
  fmap f (Node a l r) = Node (f a) (fmap f l) (fmap f r)

However, that's my personal opinion. Let's get to the real question, fmap's type:

The second issue is that lecturer wrote signature: fmap :: (a -> b) -> f a -> f b […]

First of all, the lecturer's signature is somewhat wrong. fmap's complete signature is

fmap :: Functor f => (a -> b) -> f a -> f b

The constraint Functor f is important. It limits the use of fmap to the instances of Functor. Now that's not the problem you've encountered:

for me, it is (a->b) -> Tree a -> Tree b, but it is not accepted by compiler ghci. Where is the point?

Ah, you've tried to specify a type signature for fmap in the Functor Tree instance, right?

instance Functor Tree where
  fmap :: (a -> b) -> Tree a -> Tree b
  fmap = ...

Well, that's not allowed. After all, fmap's type isn't (a -> b) -> Tree a -> Tree b, but the more general one above. It's somewhat—but not entirely—similar to using two type signatures for a single binding:

foo :: Eq a => a ->  a -> Bool
foo ::        () -> () -> Bool

That's not allowed either. Note that you can enable instance signatures with an extension if you really want to. If you just want to do it for documentation, a comment can be used instead of -XInstanceSigs:

instance Functor Tree where
  -- fmap :: (a -> b) -> Tree a -> Tree b
  fmap = ...

TL;DR: fmap's type is given by it's declaration in class Functor, it's already specified by your choice of f in the instance definition.

Upvotes: 3

Related Questions