CODEWITHSUNDEEP
haskell
Walter
Walter

Reputation: 125

Instance Applicative of a datatype

I'm trying to write an instance of Applicative for my datatype

data Multinode k v = Multinode { key :: k
                               , values :: [v]
                               } deriving Show

data Multimap k v = Multimap [Multinode k v] deriving Show

I'm still learning Haskell. So I may make funny mistakes. If I understood properly, Applicative is a subset of Functor. The operators that have to be defined are pure and <*>.

pure :: a -> f a

(<*>) :: f (a -> b) -> f a -> f b

My attempt is the following

instance Applicative (Multimap k) where
  pure x = Multimap [(Multinode x [x])]
  (Multimap mf@((Multinode kf vsf):nsf)) <*> (Multimap mx@((Multinode kx vsx):nsx)) =
Multimap [Multinode kf (vsf <*> vsx)]

Upvotes: 1

Views: 93

Answers (1)

dfeuer
dfeuer

Reputation: 48591

Maps and multimaps are not naturally Applicative. Here's why: you need

pure
  :: (...) -- Possible constraint involving k, but not v
  =>  v -> MultiMap k v

Since there are no constraints on v, pure cannot use its argument to generate any keys. So the set of keys in the result must always be the same, which doesn't work out for any meaningful notion of <*> that I know of.

The semigroupoids package offers a class called Apply, which is much more promising:

class Functor f => Apply f where
  (<.>) :: f (a -> b) -> f a -> f b
  liftF2 :: (a -> b -> c) -> f a -> f b -> f c
  (.>) :: f a -> f b -> f b
  (<.) :: f a -> f b -> f a

This is just like Applicative but without pure. <.> is analogous to <*>, liftF2 is analogous to liftA2, etc. The semigroupoids package includes an instance Ord k => Apply (Map k). You should be able to think of a couple different instances for your type based on the general idea of that one.

Upvotes: 5

Related Questions