Haskell类参数依赖于其他类参数

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

Haskell class argument that depends on other class arguments

问题

{-# LANGUAGE AllowAmbiguousTypes #-}

module SetMap where
  
import Data.Map
import Data.Set

class SetMap k v m where
  add :: k -> v -> m -> m -- add value to corresponding set
  delete :: k -> m -> m   -- delete all values associated with this key   
  get :: k -> m -> [v]    -- get values associated with this key
  
type SetMapImpl k v = Map k (Set v)  

instance SetMap k v (SetMapImpl k v) where -- duplication here!
  ...
class SetMap k v m where
  add :: k -> v -> m -> m -- add value to corresponding set
  delete :: k -> m -> m   -- delete all values associated with this key   
  get :: k -> m -> [v]    -- get values associated with this key
  
type SetMapImpl k v = Map k (Set v)  

instance SetMap k v (SetMapImpl k v) where
  ...

你提供的代码已经基本正确了,不需要进行额外的翻译或更改。

英文:

I want to implement a simple one-to-many data structure in Haskell. Each key of type k associated with set of elements of type v.

{-# LANGUAGE AllowAmbiguousTypes #-}

module SetMap where
  
import Data.Map
import Data.Set

class SetMap k v m where
  add :: k -> v -> m -> m -- add value to corresponding set
  delete :: k -> m -> m   -- delete all values associated with this key   
  get :: k -> m -> [v]    -- get values associated with this key
  
type SetMapImpl k v = Map k (Set v)  

instance SetMap k v (SetMapImpl k v) where -- duplication here!
  ...

m here is a type of implementation. But it is also parametrized with k and v.
Any ways how can I declare it? Or is it OK to do as shown above?

I expect something like this but it does not compile.

class SetMap k v m where
  add :: k -> v -> m k v -> m k v-- add value to corresponding set
  delete :: k -> m k v -> m k v  -- delete all values associated with this key   
  get :: k -> m k v -> [v]    -- get values associated with this key
  
type SetMapImpl k v = Map k (Set v)  

instance SetMap k v SetMapImpl where
  ...

答案1

得分: 3

我认为如果您利用类型族,这会更容易。
您可能需要启用一些扩展。

class SetMap m where
  type Key m
  type Val m
  add :: Key m -> Val m -> m -> m
  delete :: Key m -> m -> m
  get :: Key m -> m -> [Val m]

instance (Ord k, Ord v) => SetMap (Map k (Set v)) where
   type Key (Map k (Set v)) = k
   type Val (Map k (Set v)) = v
   add k v m = ...
   ...

我不确定在这里使用类型类是否是一个好主意。如果您有多个类型是该类的实例,这可能值得一试。也许吧。请小心不要过于泛化。

英文:

I think it's easier if you exploit type families.
You'll probably need to enable a few extensions.

class SetMap m where
  type Key m
  type Val m
  add :: Key m -> Val m -> m -> m
  delete :: Key m -> m -> m
  get :: Key m -> m -> [Val m]

instance (Ord k, Ord v) => SetMap (Map k (Set v)) where
   type Key (Map k (Set v)) = k
   type Val (Map k (Set v)) = v
   add k v m = ...
   ...

I don't know if using a type class here is a good idea. If you have multiple types that are instances of that class, it might be worth it. Maybe. Be careful not to overgeneralize.

答案2

得分: 3

以下是您要翻译的内容:

0. 无类别

首先考虑为什么需要类别。为什么不直接将这些方法实现为具体函数呢?

type SetMapImpl k v = Map k (Set v)  -- 实际上我更倾向于在这个版本中将其称为 `SetMap`。

add :: k -> v -> SetMapImpl k v -> SetMapImpl k v
add = ...

delete :: k -> SetMapImpl k v -> SetMapImpl k v
delete = ...

...

请注意,在这种情况下,您不需要新类型(newtype),因为 SetMapImpl 只会在两个参数都完全应用的情况下提到。但是为了更清晰的封装、错误消息等,将其定义为新类型仍然是个好主意。

显然,这种方法意味着您不能编写多态于不同实现的代码,但除非您有充分的理由编写这样的代码,否则最好不要担心这个问题。保持简单。由于 Haskell 具有强类型系统,以后如果需要的话,仍然很容易将代码泛化。

1. 用于参数化类型的类别

如果您希望方法看起来像 add :: k -> v -> m k v -> m k v,那么 kv 是类型和方法的参数,但不是由类别表示的抽象的参数。因此,它应该像这样:

class SetMap m where
  add :: k -> v -> m k v -> m k v

在这个版本中,您 必须SetMapImpl 定义为 newtypedata,因为类别头中提到了没有参数的 m。不过这并不是什么大问题。问题在于 add 方法现在必须适用于 任何 类型的 kv,但它不能这样做:对于 Set,您需要 Ord 约束。有几种方法可以实现这一点:

1a. 固定的约束

class SetMap m where
  add :: (Ord k, Ord v) => k -> v -> m k v -> m k v

newtype SetMapImpl k v = ...
instance SetMap SetMapImpl where
  add = ...

简单但不灵活。特别是,拥有类别的主要动机之一是您可以使用其他约束(如 Hashable)来实现其他实现;这种方法不支持这种情况。

1b. 用户可选择的约束

{-# LANGUAGE TypeFamilies, ConstraintKinds #-}
import Data.Kind (Constraint)

class SetMap m where
  type KeyConstraint m k :: Constraint
  type ValueConstraint m v :: Constraint
  add :: (KeyConstraint m k, ValueConstraint m v)
         => k -> v -> m k v -> m k v

newtype SetMapImpl k v = ...
instance SetMap SetMapImpl where
  type KeyConstraint SetMapImpl k = Ord k
  type ValueConstraint SetMapImpl v = Ord v
  add = ...

我相当喜欢这种方法,因为它表明 SetMap 实现是参数化的,但仍然允许对包含的类型强加任何必需的约束。不过,要搞清楚这一点有点复杂,很容易在不同的抽象约束中混淆。

1c. 在值级别将约束包装起来

由于您的所有方法都以一个已经存在的集合映射作为参数,而且要构建这个集合映射,已经需要知道键和值是 Ord(或 Hashable),所以实际上您可以在方法中没有任何约束的情况下做到这一点。但是您确实需要在类型本身中包装约束。

{-# LANGUAGE GADTs #-}

class SetMap m where
  add :: k -> v -> m k v -> m k v

data SetMapImpl k v where
  SetMapImpl :: (Ord k, Ord v) => Map k (Set v) -> SetMapImpl k v

instance SetMap SetMapImpl where
  add k v (SetMapImpl m) = ...

现在在 ... 中,您将通过类别无需了解它们的方式获得 Ord kOrd v 约束。

我不太建议使用这种方法。必须在值级别传递约束通常会变得很笨拙,而且对于通用地 创建新 集合映射,您仍然需要在类型级别上使用它们。

2. 一个类别,但没有集合映射上的参数性

参见 chi 的回答。这可能是我会选择的方法。尽管可以争论说,类别根本不具有参数形式的 m,但这实际上并不是限制(因为实例仍然可以在所有适当的键和值类型上是多态的,您可以直接在那里声明约束)。这种方法更加明确,在我看来,当键和值类型实际上被称为 Key mValue m 时,更容易理解正在做什么。这确实会带来一些冗长的问题,但可能是值得的。

另一个优点是,这可以轻松处理确实不是参数化的实现;例如,IntMap 仅允许类型为 Int 的键。

英文:

You have several options:

0. Classless

First consider why you need a class at all. Why not just implement those methods right away as concrete functions?

type SetMapImpl k v = Map k (Set v)  -- In fact I would tend to call this
                                     -- simply `SetMap` in this version.

add :: k -> v -> SetMapImpl k v -> SetMapImpl k v
add = ...

delete :: k -> SetMapImpl k v -> SetMapImpl k v
delete = ...

...

Notice that you don't need a newtype in this case, because SetMapImpl is only ever mentioned with both arguments fully applied. But it might still be a good idea to make it a newtype, for clearer encapsulation, error messages etc..

Obviously, this approach means you can't write code that's polymorphic over different implementations, but unless you have a good reason to write such code it is best not to worry about this. Keep it simple. Thanks to Haskell's strong type system it is still easy to generalize your code later on, should that become necessary.

1. Class for parameterised types

If you want the methods to look like add :: k -> v -> m k v -> m k v, then k and v are parameters of the type and of the methods, but not of the abstraction that's expressed by the class. Hence this should rather look like this:

class SetMap m where
  add :: k -> v -> m k v -> m k v

In this version, you must make the SetMapImpl a newtype or data, because m is mentioned without parameters in the class head. That's not much of a problem though. What is a problem is that the add method would now have to work with any types k and v, which it can't: for Set you need the Ord constraint. There are a couple of ways this can be achieved:

1a. Hard-coded constraints

class SetMap m where
  add :: (Ord k, Ord v) => k -> v -> m k v -> m k v

newtype SetMapImpl k v = ...
instance SetMap SetMapImpl where
  add = ...

Simple, but inflexible. In particular, a main motivation for having a class at all is that you could have other implementations using other constraints like Hashable; this approach does not support that.

1b. User-selectable constraints

{-# LANGUAGE TypeFamilies, ConstraintKinds #-}
import Data.Kind (Constraint)

class SetMap m where
  type KeyConstraint m k :: Constraint
  type ValueConstraint m v :: Constraint
  add :: (KeyConstraint m k, ValueConstraint m v)
             => k -> v -> m k v -> m k v

newtype SetMapImpl k v = ...
instance SetMap SetMapImpl where
  type KeyConstraint SetMapImpl k = Ord k
  type ValueConstraint SetMapImpl v = Ord v
  add = ...

I rather like this approach, because it expresses that the SetMap-implementations are parametric, but still allows imposing any required constraint on the contained types. It is a bit complicated to get this right, though, and easy to get confused with the different abstract constraints.

1c. Wrap the constraints into the value level

Since all your methods take one already existing set-map as the argument, and that set-map would already need the knowledge that the keys and values are Ord (or Hashable) to be constructed in the first place. So you can in fact get away without any constraints on the method. But you do need to wrap the constraints in the type itself.

{-# LANGUAGE GADTs #-}

class SetMap m where
  add :: k -> v -> m k v -> m k v

data SetMapImpl k v where
  SetMapImpl :: (Ord k, Ord v) => Map k (Set v) -> SetMapImpl k v

instance SetMap SetMapImpl where
  add k v (SetMapImpl m) = ...

And now in the ... you will have the Ord k and Ord v constraints available though the class knows nothing about them.

I would rather not recommend this approach though. It tends to become awkward having to pass the constraints at the value level, and for generically creating new set-maps you'll need them on the type level anyway.

2. A class, but without parametricity on the set-maps

See chi's answer. This is what I would probably go with. Although it is arguably less elegant that the class doesn't have m in parameterised form at all, this is not really a restriction (since the instance can still be polymorphic over all appropriate key- and value types, and you can simply state the constraints right there). This approach is more explicit, and in my experience it tends to be a lot clearer what you're doing when the key- and value types are actually called Key m and Value m. This does come with some verbosity penalty, but it's probably worth it.

Another advantage is that this can easily deal with implementations that really are not parametric at all; e.g. IntMap only allows keys of type Int.

答案3

得分: 2

您的最后一个代码示例无法编译,因为诸如 SetMapImpl 这样的类型别名需要在您可以在实例头中使用它们之前完全应用于它们的参数。如果您添加一个 newtype 包装器,将 SetMapImpl 变成一个实际的类型而不仅仅是一个别名,那么以下代码将可以编译成功:

class SetMap k v m where
  add :: k -> v -> m k v -> m k v
  delete :: k -> m k v -> m k v
  get :: k -> m k v -> [v]

newtype SetMapImpl k v = SetMapImpl (Map k (Set v))

instance (Ord k, Ord v) => SetMap k v SetMapImpl where
  add k v (SetMapImpl s) = SetMapImpl $ ...
  delete k (SetMapImpl s) = SetMapImpl $ ...
  get k (SetMapImpl s) = ...

实例方法将需要一些包装和解包的样板代码,但在编译后的代码中不会产生额外的开销。

英文:

Your last code example doesn't compile because type aliases like SetMapImpl need to be fully applied to their arguments before you can use them in an instance head. If you add a newtype wrapper to make SetMapImpl an actual type instead of just an alias, the following will compile fine:

class SetMap k v m where
  add :: k -> v -> m k v -> m k v
  delete :: k -> m k v -> m k v
  get :: k -> m k v -> [v]

newtype SetMapImpl k v = SetMapImpl (Map k (Set v))

instance (Ord k, Ord v) => SetMap k v SetMapImpl where
  add k v (SetMapImpl s) = SetMapImpl $ ...
  delete k (SetMapImpl s) = SetMapImpl $ ...
  get k (SetMapImpl s) = ...

The instance methods will require a little wrapping and unwrapping boilerplate as shown, but it will be cost-free in the compiled code.

huangapple
  • 本文由 发表于 2023年1月9日 01:32:21
  • 转载请务必保留本文链接:https://go.coder-hub.com/75049953.html
匿名

发表评论

匿名网友

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

确定