受约束元素类型的构造函数类/函子? [英] Constructor Class/Functor for a constrained element type?

问题描述

这是一个常见问题——例如这个答案；或部分类型构造函数"中的第 3.2 节格式良好的应用程序的约束"[Jones、Morris、Eisenberg 2020].常见的答案是你做不到.我想我已经做到了.(但它并不漂亮.)

data Set a = NilSet |ConsSet a (Set a) 派生 (Eq, Show, Read)mySet = ConsSet 'a' $ ConsSet 'b' $ ConsSet 'A' NilSet

我的 Set 类型不应该有重复的元素.所以如果我fmap toUpper mySet，我想避免两个'A'.然后考虑

添加:回应评论.(以下保留原代码，供参考.)

<块引用>

@Carl [语言报告中的限制] 仅适用于对 u 类型的限制.

是的，我什至没有尝试完全输入 u"，因为我认为它会被禁止.但是......我现在可以处理@Fyodor关于是否可能存在一些残留限制的问题:

我需要的最小语言扩展是MultiParamTypeClasses, FlexibleInstances——我对此很放松；它们长期存在/稳定/久经考验.我什至不需要 FunctionalDependencies.这也适用于 Hugsmode.

class Functorish2 f wherefmapish2 :: (FConstr2 f a b) =>(a -> b) ->f a ->f b——嗯?编译正常instance Functorish2 f where -- 需要 FlexibleInstancesfmapish2 = fmapish3类 FConstr2 f a b 其中 fmapish3 :: (a -> b) ->f a ->fb-- IOW 与 fmap 相同的签名.这给了我自由的手.实例(Eq b)＝＞FConstr2 设置一个 b 其中 -- 需要 FlexibleInstancesfmapish3 f NilSet = NilSetfmapish3 f (ConsSet x xs) = uqCons (f x) (fmapish3 f xs)其中 uqCons fx xss |fElem fx xss = xss|否则 = ConsSet fx xssfElem fx (ConsSet y ys) = fx == y ||元素 fx ysfElem fx NilSet = False

并且确实 fmapish2 toUpper mySet 消除了重复项.更现实的是，Set 实现将使用 BST 或 hashmap 或类似的东西，因此对元素的约束将比 Eq b 更复杂.尽管如此，我似乎可以对 Set 的元素添加任何约束.

或者有什么问题吗?这是我可以滥用导致类型不安全的错误吗?据推测，语言报告限制(下一段)不希望 fmapish2 的多态性低于班级负责人所指出的.

令人惊讶的是我标记了嗯?"的那一行.根据 2010 年语言报告第 4.3.1 节类声明"对方法签名的约束cxi 可能仅约束 w-bar；特别是，cxi 不能约束 u."-- u 是班长的 tyvar(s).(顺便说一句，Set 上的 deriving (Eq) 不是必需的.)

第二个惊喜是，这不仅在 GHC (8.10.2, 7.10) 中有效，在 Hugs (2006) 中也有效.

(来自原始 q 的代码.)

{-# LANGUAGE MultiParamTypeClasses、FlexibleInstances、FlexibleContexts、UndecidableInstances #-}导入 Data.Char -- toUpper类函式 f wherefmapish :: (FConstr (f b)) =>(a -> b) ->f a ->f b——嗯?编译正常类 FConstr fb 其中 fMerge :: fb ->fb->脸书实例函子集 wherefmapish f NilSet = NilSetfmapish f (ConsSet x xs) = fMerge (ConsSet (f x) NilSet) (fmapish f xs)实例(等式a)＝＞FConstr (Set a) wherefMerge (ConsSet x NilSet) yss |fElem x yss = yss|否则 = ConsSet x yss其中 fElem x (ConsSet y ys) = x == y ||元素 x ysfElem x NilSet = False

解决方案

令人惊讶的是我标记了嗯?"的那一行.根据 2010 年语言报告第 4.3.1 节类声明"对方法签名的约束cxi 可能仅约束 w-bar；特别是，cxi 可能不会约束 u."-- u 是班长的 tyvar(s).(顺便说一句， Set 上的推导 (Eq) 不是必需的.)

将我的评论变成答案，我认为相关的 GHC 扩展名为 ConstrainedClassMethods 由 MultiParamTypeClasses 隐含.

例如，此代码无法编译:

class 测试一个 where测试 :: 等式 a =>->->布尔值

你会得到错误:

Test.hs:2:3: 错误:• 测试"类型中的约束Eq a"仅约束类类型变量启用 ConstrainedClassMethods 以允许它• 检查类方法时:测试 :: forall a.(测试a，等式a)＝＞->->布尔值在Test"的类声明中|2 |测试 :: 等式 a =>->->布尔值|^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

如果你启用了 ConstraintClassMethods 那么它会编译.

在您的情况下，ConstraintedClassMethods 由 MultiParamTypeClasses 隐含，这也修复了此测试示例中的错误.

但即使没有它，它也会编译，因为 FConstr2 f a b 约束约束的不仅仅是实例头中提到的变量.从链接的 GHC 指南中查看此示例，特别是 op5:

<块引用>

class C a whereop3 :: 等式 a =>->a -- Rejected:仅约束类变量op4::D b =>->b -- 接受:约束局部量化变量`b`op5 :: D (a,b) =>->b -- 接受:约束局部量化变量`b`

因此约束 FConstr2 f a b 也将被接受，因为它约束了局部量化的变量 a 和 b.

This is a FAQ -- for example this answer; or Section 3.2 'A Constraint for Well-Formed Applications' in 'Partial Type Constructors' [Jones, Morris, Eisenberg 2020]. And the frequent answer is you can't do it. I think I kinda have done it. (But it ain't pretty.)

data Set a = NilSet | ConsSet a (Set a)    deriving (Eq, Show, Read)
mySet = ConsSet 'a' $ ConsSet 'b' $ ConsSet 'A' NilSet

My Set type should not have duplicate elements. So if I fmap toUpper mySet, I want to avoid two 'A's. Then consider

Addit: in response to comments. (Original code retained below, for reference.)

@Carl [the restriction in the Language Report] applies only to constraints on exactly the type u.

Yes I didn't even try "exactly type u", because I assumed it would be banned. But ... I can now dispose of @Fyodor's line of questions about whether there might be some residual restrictions:

The minimal language extensions I need are MultiParamTypeClasses, FlexibleInstances -- which I'm relaxed about; they're long-standing/stable/well-tried. I don't even need FunctionalDependencies. And this also works in Hugsmode.

class Functorish2 f  where
  fmapish2 :: (FConstr2 f a b) => (a -> b) -> f a -> f b    -- huh? compiles ok
instance Functorish2 f  where                               -- needs FlexibleInstances
  fmapish2 = fmapish3

class FConstr2 f a b  where fmapish3 :: (a -> b) -> f a -> f b

-- IOW same signature as fmap. This gives me a free hand.

instance (Eq b) => FConstr2 Set a b  where                  -- needs FlexibleInstances
  fmapish3 f NilSet = NilSet
  fmapish3 f (ConsSet x xs) = uqCons (f x) (fmapish3 f xs)
    where uqCons fx xss | fElem fx xss = xss
                        | otherwise    = ConsSet fx xss
          fElem fx (ConsSet y ys) = fx == y || fElem fx ys
          fElem fx NilSet         = False

And indeed fmapish2 toUpper mySet squishes out the duplicates. More realistically, a Set implementation would use a BST or hashmap or some such, so the constraint on elements would be more complex than Eq b. Never the less, seems I can add any constraints on the elements of the Set.

Or is there a catch? Is this a fault I could abuse to cause type-unsafety? Presumably the Language Report restriction (next para) doesn't want to allow fmapish2 to be less polymorphic than the class head would indicate.

The surprise is the line I've marked "huh?". According to the 2010 Language Report Section 4.3.1 'Class Declarations' constraints on method signatures "The cxi may constrain only w-bar; in particular, the cxi may not constrain u." -- the u being the tyvar(s) from the class head. (BTW the deriving (Eq) on Set isn't essential.)

The second surprise is that not only does this work in GHC (8.10.2, 7.10), it also works in Hugs (2006).

(Code from original q.)

{-# LANGUAGE  MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, 
          UndecidableInstances   #-}

import Data.Char                                          -- toUpper

class Functorish f  where
  fmapish :: (FConstr (f b)) => (a -> b) -> f a -> f b    -- huh? compiles ok

class FConstr fb  where fMerge :: fb -> fb -> fb

instance Functorish Set  where
  fmapish f NilSet         = NilSet
  fmapish f (ConsSet x xs) = fMerge (ConsSet (f x) NilSet) (fmapish f xs)

instance (Eq a) => FConstr (Set a)  where            
  fMerge (ConsSet x NilSet) yss | fElem x yss = yss
                                | otherwise   = ConsSet x yss
        where fElem x (ConsSet y ys) = x == y || fElem x ys
              fElem x NilSet         = False

解决方案

The surprise is the line I've marked "huh?". According to the 2010 Language Report Section 4.3.1 'Class Declarations' constraints on method signatures "The cxi may constrain only w-bar; in particular, the cxi may not constrain u." -- the u being the tyvar(s) from the class head. (BTW the deriving (Eq) on Set isn't essential.)

Turning my comment into an answer, I think the relevant GHC extension is called ConstrainedClassMethods which is implied by MultiParamTypeClasses.

For example, this code doesn't compile:

class Test a where
  test :: Eq a => a -> a -> Bool

You'll get the error:

Test.hs:2:3: error:
    • Constraint ‘Eq a’ in the type of ‘test’
        constrains only the class type variables
      Enable ConstrainedClassMethods to allow it
    • When checking the class method:
        test :: forall a. (Test a, Eq a) => a -> a -> Bool
      In the class declaration for ‘Test’
  |
2 |   test :: Eq a => a -> a -> Bool
  |   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

If you enable ConstraintClassMethods then it does compile.

In your case ConstraintedClassMethods is implied by MultiParamTypeClasses, which also fixes the error in this test example.

But even without that, it would compile, because the FConstr2 f a b constraint constrains more than just the variables mentioned in the instance head. See this example from the linked GHC guide, in particular op5:

class C a where
  op3 :: Eq a => a -> a    -- Rejected: constrains class variable only
  op4 :: D b => a -> b     -- Accepted: constrains a locally-quantified variable `b`
  op5 :: D (a,b) => a -> b -- Accepted: constrains a locally-quantified variable `b`

So the constraint FConstr2 f a b would also be accepted, because it constrains locally-quantified variables a and b.

这篇关于受约束元素类型的构造函数类/函子?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！