卷曲产品类型

Question

使用类型族,我们可以定义一个类型的函数fold和该类型的底层代数,表示为函数和常量值的n元组.这允许定义在Foldable类型类中定义的通用foldr函数:

import Data.Set (Set)
import Data.Map (Map)
import qualified Data.Set as S
import qualified Data.Map as M

class Foldable m where
  type Algebra m b :: *
  fold :: Algebra m b -> m -> b

instance (Ord a) => Foldable (Set a) where
  type Algebra (Set a) b = (b, a -> b -> b)
  fold = uncurry $ flip S.fold

instance (Ord k) => Foldable (Map k a) where
  type Algebra (Map k a) b = (b, k -> a -> b -> b)
  fold = uncurry $ flip M.foldWithKey

类似地,约束种类允许定义广义映射函数.的地图功能不同于FMAP通过考虑一个代数数据类型的每个值字段:

class Mappable m where
  type Contains m     :: *
  type Mapped   m r b :: Constraint
  map :: (Mapped m r b) => (Contains m -> b) -> m -> r

instance (Ord a) => Mappable (Set a) where
  type Contains (Set a)     = a
  type Mapped   (Set a) r b = (Ord b, r ~ Set b)
  map = S.map

instance (Ord k) => Mappable (Map k a) where
  type Contains (Map k a)     = (k, a)
  type Mapped   (Map k a) r b = (Ord k, r ~ Map k b)
  map = M.mapWithKey . curry

从用户的角度来看,这两种功能都不是特别友好.特别是,这两种技术都不允许定义curried函数.这意味着用户无法轻易地部分应用折叠或映射功能.什么我想的是咖喱的功能和价值的元组,以产生上述的咖喱版本类型级功能.因此,我想写一些近似于以下类型函数的东西:

Curry :: Product -> Type -> Type
Curry ()       m = m
Curry (a × as) m = a -> (Curry as m b)

如果是这样,我们可以从底层代数生成一个curried折叠函数.例如:

  fold :: Curry (Algebra [a] b) ([a] -> b)
? fold :: Curry (b, a -> b -> b) ([a] -> b)
? fold :: b -> (Curry (a -> b -> b)) ([a] -> b)
? fold :: b -> (a -> b -> b -> (Curry () ([a] -> b))
? fold :: b -> ((a -> b -> b) -> ([a] -> b))

  map :: (Mapped (Map k a) r b) => (Curry (Contains (Map k a)) b) -> Map k a -> r
? map :: (Mapped (Map k a) r b) => (Curry (k, a) b) -> Map k a -> r
? map :: (Mapped (Map k a) r b) => (k -> (Curry (a) b) -> Map k a -> r
? map :: (Mapped (Map k a) r b) => (k -> (a -> Curry () b)) -> Map k a -> r
? map :: (Mapped (Map k a) r b) => (k -> (a -> b)) -> Map k a -> r

我知道Haskell没有类型函数,并且n元组的正确表示可能类似于类型级长度索引的类型列表.这可能吗？

编辑:为了完整性,我目前尝试解决方案如下.我使用空数据类型来表示类型的产品,并键入族来表示上面的函数Curry.此解决方案似乎适用于地图功能,但不适用于折叠功能.我相信,但我不确定,咖喱在进行类型检查时没有得到适当的减少.

data Unit
data Times a b

type family Curry a m :: *
type instance Curry Unit        m = m
type instance Curry (Times a l) m = a -> Curry l m

class Foldable m where
  type Algebra m b :: *
  fold :: Curry (Algebra m b) (m -> b)

instance (Ord a) => Foldable (Set a) where
  type Algebra (Set a) b = Times (a -> b -> b) (Times b Unit)
  fold = S.fold

instance (Ord k) => Foldable (Map k a) where
  type Algebra (Map k a) b = Times (k -> a -> b -> b) (Times b Unit)
  fold = M.foldWithKey

 class Mappable m where
   type Contains m     :: *
   type Mapped   m r b :: Constraint
   map :: (Mapped m r b) => Curry (Contains m) b -> m -> r

 instance (Ord a) => Mappable (Set a) where
   type Contains (Set a)     = Times a Unit
   type Mapped   (Set a) r b = (Ord b, r ~ Set b)
   map = S.map

 instance (Ord k) => Mappable (Map k a) where
   type Contains (Map k a)     = Times k (Times a Unit)
   type Mapped   (Map k a) r b = (Ord k, r ~ Map k b)
   map = M.mapWithKey

Answer 1

好吧，我认为我的其他答案实际上并不能真正回答您的问题。对此感到抱歉。

fold在最终代码中，比较和的类型map：

fold :: Curry (Algebra m b) (m -> b)
map  :: (Mapped m r b) => Curry (Contains m) b -> m -> r

这里有一个很大的区别。的类型fold只是一个类型族应用程序，而 的类型map包含final m -> r，提及类参数m。因此，在 的情况下map，GHC 很容易从上下文中了解您想要以哪种类型实例化该类。

不幸的是，在 的情况下并非如此fold，因为类型族不需要是单射的，因此不容易反转。因此，通过查看您使用的特定类型fold，GHC 不可能推断出它m是什么。

此问题的标准解决方案是使用代理参数来修复 的类型m，通过定义

data Proxy m = P

然后给出fold这个类型：

fold :: Proxy m -> Curry (Algebra m b) (m -> b)

您必须调整实例以接受和丢弃代理参数。然后你可以使用：

fold (P :: Proxy (Set Int)) (+) 0 (S.fromList [1..10])

或类似于在集合上调用折叠函数。

为了更清楚地了解为什么 GHC 难以解决这种情况，请考虑以下玩具示例：

class C a where
  type F a :: *
  f :: F a

instance C Bool where
  type F Bool = Char -> Char
  f = id

instance C () where
  type F () = Char -> Char
  f = toUpper

现在，如果您调用f 'x'，GHC 就没有有意义的方法来检测您指的是哪个实例。代理在这里也会有帮助。