Data.Map 的 Semigroup 实例

huangapple go评论58阅读模式
英文:

Semigroup instace for Data.Map

问题

错误:
 预期的种类为‘k -> k1 -> *’,但‘MyMap’的种类为‘*
 在‘Semigroup’的第一个参数中,即‘(MyMap k v)
  在‘Semigroup (MyMap k v)’的实例声明中
  |
6 | instance Semigroup (MyMap k v) where
  |                     ^^^^^^^^^

我认为MyMap (Map Int String)应该具有种类* -> * -> *,因为它接受两种类型(Int和String),并返回一个mymap类型。

英文:

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!

答案1

得分: 4

你应该将你的数据类型大写:

newtype MyMap = MkMyMap (Map Int String)

类型 MyMap 没有参数,注意我将构造函数 MkMyMap 重命名以消除歧义:

instance Semigroup MyMap where
  MkMyMap a <> MkMyMap b = MkMyMap (Map.compose a b)

Map.compose 仅在地图的类型为 Map A A 时才能作为半群操作工作:

compose :: Ord b => Map b c -> Map a b -> Map a c

让我们看看当第一个参数是 Map Int String 时会发生什么:

compose :: Map Int String -> Map a Int -> Map a String

如果我们也返回 Map Int String,它会强制第二个参数为 Map Int Int

compose :: Map Int String -> Map Int Int -> Map Int String

有一个关于如何定义地图的模板,使用 Monoid 来累积冲突:MonoidalMap key a

newtype MyMap = MkMyMap (Map Int String)
  deriving newtype IsList
  deriving stock Show
  deriving (Semigroup, Monoid)
  via MonoidalMap Int String

这将使用 Semigroup String 来处理每个重复键的值,将两个地图联合起来。如果我们使用不同的 Semigroup 实例 Semigroup.First String,那么将选择第一个键:

deriving (Semigroup, Monoid)
via MonoidalMap Int (Semigroup.First String)

如果我们使用 Semigroup.Last String,则选择最后一个键:

deriving (Semigroup, Monoid)
via MonoidalMap Int (Semigroup.Last String)

还有其他组合,其中一些相当奇怪。例如使用 Applicative lifting (Ap)

deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap [] (Semigroup.First Char))

deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap [] (Semigroup.Last Char))

deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap ZipList (Semigroup.First Char))

deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap ZipList (Semigroup.Last Char))

deriving (Semigroup, Monoid)
via MonoidalMap Int (Max String)

deriving (Semigroup, Monoid)
via MonoidalMap Int (Ap ZipList (Max Char))
英文:

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 &lt;&gt; 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 =&gt; Map b c -&gt; Map a b -&gt; Map a c

Let's see what happens when the first argument is Map Int String:

compose :: Map Int String -&gt; Map a Int -&gt; 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 -&gt; Map Int Int -&gt; 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

  -- &gt;&gt; :set -XOverloadedLists
  -- &gt;&gt; [(2, &quot;two&quot;), (0, &quot;zero&quot;)] &lt;&gt; [(1, &quot;einn&quot;), (2, &quot;tveir&quot;)] :: MyMap
  -- MkMyMap (fromList [(0,&quot;zero&quot;),(1,&quot;einn&quot;),(2,&quot;twotveir&quot;)])
  deriving (Semigroup, Monoid)
  via MonoidalMap Int String -- (&lt;&gt;) = 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:

  -- &gt;&gt; [(2, &quot;two&quot;), (0, &quot;zero&quot;)] &lt;&gt; [(1, &quot;einn&quot;), (2, &quot;tveir&quot;)] :: MyMap
  -- MkMyMap (fromList [(0,&quot;zero&quot;),(1,&quot;einn&quot;),(2,&quot;two&quot;)])
  deriving (Semigroup, Monoid)
  via MonoidalMap Int (Semigroup.First String) -- (&lt;&gt;) = union
                                               --      = unionWith const
                                               --      = unionWith \a _ -&gt; a

and the last key is chosen if we use Semigroup.Last String.

  -- &gt;&gt; [(2, &quot;two&quot;), (0, &quot;zero&quot;)] &lt;&gt; [(1, &quot;einn&quot;), (2, &quot;tveir&quot;)] :: MyMap
  -- MkMyMap (fromList [(0,&quot;zero&quot;),(1,&quot;einn&quot;),(2,&quot;tveir&quot;)])
  deriving (Semigroup, Monoid)
  via MonoidalMap Int (Semigroup.Last String) -- (&lt;&gt;) = unionWith \_ b -&gt; b

There are also other combinations, some of which are rather strange. For example using Applicative lifting (Ap):

  -- &gt;&gt; [(2, &quot;two&quot;), (0, &quot;zero&quot;)] &lt;&gt; [(1, &quot;einn&quot;), (2, &quot;tveir&quot;)] :: MyMap
  -- MkMyMap (fromList [(0,&quot;zero&quot;),(1,&quot;einn&quot;),(2,&quot;tttttwwwwwooooo&quot;)])
  deriving (Semigroup, Monoid)
  via MonoidalMap Int (Ap [] (Semigroup.First Char)) -- (&lt;&gt;) = unionWith (liftA2 \a _ -&gt; a)
                                                     --      = unionWith (&lt;*)

  -- &gt;&gt; [(2, &quot;two&quot;), (0, &quot;zero&quot;)] &lt;&gt; [(1, &quot;einn&quot;), (2, &quot;tveir&quot;)] :: MyMap
  -- MkMyMap (fromList [(0,&quot;zero&quot;),(1,&quot;einn&quot;),(2,&quot;tveirtveirtveir&quot;)])
  deriving (Semigroup, Monoid)
  via MonoidalMap Int (Ap [] (Semigroup.Last Char)) -- (&lt;&gt;) = unionWith (liftA2 \_ b -&gt; b)
                                                    --      = unionWith (*&gt;)

  -- &gt;&gt; [(2, &quot;two&quot;), (0, &quot;zero&quot;)] &lt;&gt; [(1, &quot;einn&quot;), (2, &quot;tveir&quot;)] :: MyMap
  -- MkMyMap (fromList [(0,&quot;zero&quot;),(1,&quot;einn&quot;),(2,&quot;two&quot;)])
  deriving (Semigroup, Monoid)
  via MonoidalMap Int (Ap ZipList (Semigroup.First Char)) -- (&lt;&gt;) = unionWith (zipWith \a _ -&gt; a)

  -- &gt;&gt; [(2, &quot;two&quot;), (0, &quot;zero&quot;)] &lt;&gt; [(1, &quot;einn&quot;), (2, &quot;tveir&quot;)] :: MyMap
  -- MkMyMap (fromList [(0,&quot;zero&quot;),(1,&quot;einn&quot;),(2,&quot;tve&quot;)])
  deriving (Semigroup, Monoid)
  via MonoidalMap Int (Ap ZipList (Semigroup.Last Char)) -- (&lt;&gt;) = unionWith (zipList \_ b -&gt; b)

  -- &gt;&gt; [(2, &quot;two&quot;), (0, &quot;zero&quot;)] &lt;&gt; [(1, &quot;einn&quot;), (2, &quot;tveir&quot;)] :: MyMap
  -- MkMyMap (fromList [(0,&quot;zero&quot;),(1,&quot;einn&quot;),(2,&quot;two&quot;)])
  deriving (Semigroup, Monoid)
  via MonoidalMap Int (Max String) -- (&lt;&gt;) = unionWith max

  -- &gt;&gt; [(4, &quot;four&quot;)] &lt;&gt; [(4, &quot;fj&#243;rir&quot;)] :: MyMap
  -- MkMyMap (fromList [(4,&quot;fo&#243;r&quot;)])
  deriving (Semigroup, Monoid)
  via MonoidalMap Int (Ap ZipList (Max Char)) -- (&lt;&gt;) = unionWith (zipWith max)

huangapple
  • 本文由 发表于 2023年3月10日 00:23:43
  • 转载请务必保留本文链接:https://go.coder-hub.com/75687368.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定