I'm not sure how to write the semigroup instance for this map newtype:
import Data.Map (Map)
import qualified Data.Map as Map
newtype mymap = MyMap (Map Int String)
instance Semigroup (MyMap k v) where
MyMap a <> MyMap b = Map.compose a b
error:
• Expected kind ‘k -> k1 -> *’, but ‘MyMap’ has kind ‘*’
• In the first argument of ‘Semigroup’, namely ‘(MyMap k v)’
In the instance declaration for ‘Semigroup (MyMap k v)’
|
6 | instance Semigroup (MyMap k v) where
| ^^^^^^^^^
I thought that MyMap (Map Int String)
would have kind * -> * -> *
as it takes two types (Int and String) and returns a mymap type
Thanks!
You should write your datatype capitalized
newtype MyMap = MkMyMap (Map Int String)
Type MyMap
has no arguments, notice that I renamed the constructor MkMyMap
to disambiguate between them:
instance Semigroup MyMap where
MkMyMap a <> MkMyMap b = MkMyMap (Map.compose a b)
Map.compose
will not work as a semigroup operation unless the map has type Map A A
:
compose :: Ord b => Map b c -> Map a b -> Map a c
Let's see what happens when the first argument is Map Int String
:
compose :: Map Int String -> Map a Int -> Map a String
If we are returning Map Int String
as well, it forces the second argument to be Map Int Int
compose :: Map Int String -> Map Int Int -> Map Int String
There is a template for how maps can be defined, using a Monoid to accumulate conflicts: MonoidalMap key a.
newtype MyMap = MkMyMap (Map Int String)
deriving
newtype IsList
deriving
stock Show
-- >> :set -XOverloadedLists
-- >> [(2, "two"), (0, "zero")] <> [(1, "einn"), (2, "tveir")] :: MyMap
-- MkMyMap (fromList [(0,"zero"),(1,"einn"),(2,"twotveir")])
deriving (Semigroup, Monoid)
via MonoidalMap Int String -- (<>) = unionWith (++)
This unions the two Maps using the Semigroup String
for the value of every duplicate key. If we used a different Semigroup instance Semigroup.First String
then the first key is chosen:
-- >> [(2, "two"), (0, "zero")] <> [(1, "einn"), (2, "tveir")] :: MyMap
-- MkMyMap (fromList [(0,"zero"),(1,"einn"),(2,"two")])
deriving (Semigroup, Monoid)
via MonoidalMap Int (Semigroup.First String) -- (<>) = union
-- = unionWith const
-- = unionWith \a _ -> a
and the last key is chosen if we use Semigroup.Last String
.
-- >> [(2, "two"), (0, "zero")] <> [(1, "einn"), (2, "tveir")] :: MyMap
-- MkMyMap (fromList [(0,"zero"),(1,"einn"),(2,"tveir")])
deriving (Semigroup, Monoid)
via MonoidalMap Int (Semigroup.Last String) -- (<>) = unionWith \_ b -> b
There are also other combinations, some of which are rather strange. For example using Applicative lifting (Ap
):
-- >> [(2, "two"), (0, "zero")] <> [(1, "einn"), (2, "tveir")] :: MyMap
-- MkMyMap (fromList [(0,"zero"),(1,"einn"),(2,"tttttwwwwwooooo")])
deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap [] (Semigroup.First Char)) -- (<>) = unionWith (liftA2 \a _ -> a)
-- = unionWith (<*)
-- >> [(2, "two"), (0, "zero")] <> [(1, "einn"), (2, "tveir")] :: MyMap
-- MkMyMap (fromList [(0,"zero"),(1,"einn"),(2,"tveirtveirtveir")])
deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap [] (Semigroup.Last Char)) -- (<>) = unionWith (liftA2 \_ b -> b)
-- = unionWith (*>)
-- >> [(2, "two"), (0, "zero")] <> [(1, "einn"), (2, "tveir")] :: MyMap
-- MkMyMap (fromList [(0,"zero"),(1,"einn"),(2,"two")])
deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap ZipList (Semigroup.First Char)) -- (<>) = unionWith (zipWith \a _ -> a)
-- >> [(2, "two"), (0, "zero")] <> [(1, "einn"), (2, "tveir")] :: MyMap
-- MkMyMap (fromList [(0,"zero"),(1,"einn"),(2,"tve")])
deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap ZipList (Semigroup.Last Char)) -- (<>) = unionWith (zipList \_ b -> b)
-- >> [(2, "two"), (0, "zero")] <> [(1, "einn"), (2, "tveir")] :: MyMap
-- MkMyMap (fromList [(0,"zero"),(1,"einn"),(2,"two")])
deriving (Semigroup, Monoid)
via MonoidalMap Int (Max String) -- (<>) = unionWith max
-- >> [(4, "four")] <> [(4, "fjórir")] :: MyMap
-- MkMyMap (fromList [(4,"foór")])
deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap ZipList (Max Char)) -- (<>) = unionWith (zipWith max)