开发者

How to "newtype" IntSet?

Thanks to newtype and the GeneralizedNewtypeDeriving extension, one can define distinct lightweight types with little effort:

newtype PersonId = PersonId Int deriving (Eq, Ord, Show, NFData, ...)
newtype GroupId  = GroupId Int deriving (Eq, Ord, Show, NFData, ...)

which allows the type-system to make sure a PersonId is not used by accident where a GroupId was expected, but still inherit selected typeclass instances from Int.

Now one could simply define PersonIdSet and GroupIdSet as

import Data.Set (Set)
import qualified Data.Set as Set

type PersonIdSet = Set PersonId
type GroupIdSet  = Set GroupId

noGroups :: GroupIdSet
noGroups = Set.empty

-- should not type-check
foo = PersonId 123 `Set.member` noGroups

-- should type-check
bar = GroupId 123 `Set.member` noGroups

which is type safe, since map is parametrized by the key-type, and also, the Set.member operation is polymorphic so I don't need to define per-id-type variants such as personIdSetMember and groupIdSetMember (and all other set-operations I might want to use)

...but how can I use the more efficient IntSets instead for PersonIdSet and GroupIdSet开发者_高级运维 respectively in a similiar way to the example above? Is there a simple way w/o having to wrap/replicate the whole Data.IntSet API as a typeclass?


I think you have to wrap IntSet as you said. However, rather than defining each ID type separately, you can introduce a phantom type to create a family of IDs and IDSets that are compatible with one another:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import qualified Data.IntSet as IntSet
import Data.IntSet (IntSet)

newtype ID a = ID { unID :: Int }
              deriving ( Eq, Ord, Show, Num )

newtype IDSet a = IDSet { unIDSet :: IntSet }
              deriving ( Eq, Ord, Show )

null :: IDSet a -> Bool
null = IntSet.null . unIDSet

member :: ID a -> IDSet a -> Bool
member i = IntSet.member (unID i) . unIDSet

empty :: IDSet a
empty = IDSet $ IntSet.empty

singleton :: ID a -> IDSet a
singleton = IDSet . IntSet.singleton . unID

insert :: ID a -> IDSet a -> IDSet a
insert i = IDSet . IntSet.insert (unID i) . unIDSet

delete :: ID a -> IDSet a -> IDSet a
delete i = IDSet . IntSet.delete (unID i) . unIDSet

So, assuming you have a Person type, and a Group type, you can do:

type PersonID = ID Person
type PersonIDSet = IDSet Person

type GroupID = ID Group
type GroupIDSet = IDSet Group


The enummapset package implements one approach to newtype-safe IntMap/IntSets.

An example for its usage based on the types from the original question:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import           Data.EnumSet (EnumSet)
import qualified Data.EnumSet as ES

newtype PersonId = PersonId Int deriving Enum
newtype GroupId  = GroupId  Int deriving Enum

type PersonIdSet = EnumSet PersonId
type GroupIdSet  = EnumSet GroupId

noGroups :: GroupIdSet
noGroups = ES.empty

-- fails type-check: Couldn't match expected type `PersonId' with actual type `GroupId'
foo = PersonId 123 `ES.member` noGroups

-- passes type-check
bar = GroupId 123 `ES.member` noGroups

The usage of Data.EnumMap is similar.


I am under the impression you assume it is less efficient to use a type instead of a newtype. That is not true, newtypes are usually more efficiently implemented than datas.

So, your definition of PersonIdSet is perfectly safe and as efficient as you might want.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜