Haskell如何将Ratio (Poly)组合类型声明为Polynom类的实例？

问题描述 #

我声明了如下数据类型：

data Poly a = Poly [a]

同时定义了如下类型类：

class Polynom p where
  substitute :: p a -> a -> a
  compose :: p a -> p a -> p a

我已经可以为该数据类型实现类型类实例：

instance Polynom Poly where
  substitute = ...
  compose = ...

现在我希望Poly的Ratio类型也成为该类的实例，我尝试了多种语法和语言扩展都无法生效，例如以下写法均报错：

instance Polynom (Ratio . Poly) where ...
-- error: cannot use (.) there

instance Poly p => Polynom (Ratio (p _)) where ...
-- error: no wildcards allowed

type X a = Ratio (Poly x)
instance Polynom X where ...
-- error: X needs another param

instance Polynom (* -> Ratio (Poly *)) where ...
-- error: wrong kind

我的目标是让substitute和compose可以作用于Ratio (Poly *)类型，示例用法如下：

rf1 = Poly [1,2,3] % Poly [4,5,6] :: Ratio (Poly Int)
rf2 = Poly [0,1] % Poly [1,0] :: Ratio (Poly Int)
rf = rf1 `compose` rf2 :: Ratio (Poly Int)
result = substitute rf 10 :: Int

请问该需求在Haskell中是否可以实现？如果可以，我需要使用什么语法或者语言扩展？

问题更新 #

我已经按照@leftaroundabout的建议使用TypeFamilies解决了该问题，可正常运行的实例声明如下*：

instance Integral a => Polynom (Ratio (Poly a)) where
  type Domain (Ratio (Poly a)) = Ratio a
  substitute (n :% d) x = substitute ((%1) <$> n) x
                        / substitute ((%1) <$> d) x
  compose (n :% d) = substitute ((pure <$> n) % (pure <$> d))

*（我实际修改了不合理的命名，此处保留原命名避免混淆）

解答 #

报错核心原因 #

你最初定义的Polynom类型类对参数p的kind要求是* -> *（即需要接受一个类型参数才能成为具体类型），而Ratio (Poly a)本身已经是kind为*的具体类型，完全不符合类型类的参数kind要求，这是你之前所有写法报错的根本原因。

可行实现方案 #

你已经用到的**关联类型家族（TypeFamilies）**是最简洁的实现方案，不需要额外的类型包装，具体步骤如下：

1. 首先开启必要的语言扩展，在源文件头部添加：

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleInstances #-}

2. 修改原始的Polynom类型类定义，把定义域作为关联类型声明：

class Polynom p where
  -- 关联类型，代表该多项式类型的输入值类型
  type Domain p :: *
  -- 代入求值：输入多项式和一个值，输出计算结果
  substitute :: p -> Domain p -> Domain p
  -- 多项式组合：把第二个多项式代入第一个的变量位置
  compose :: p -> p -> p

3. 调整原有Poly类型的实例实现适配新的类型类：

instance Num a => Polynom (Poly a) where
  type Domain (Poly a) = a
  -- substitute的示例实现：按多项式系数展开求和
  substitute (Poly coeffs) x = sum $ zipWith (*) coeffs (iterate (*x) 1)
  compose poly1 poly2 = substitute (fmap pure poly1) poly2

4. 再实现Ratio (Poly a)的实例，也就是你更新里的写法即可正常运行。

如果不想修改原始类型类的定义，也可以用newtype包装把Ratio . Poly提升到符合要求的* -> * kind：

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype RatioPoly a = RatioPoly (Ratio (Poly a))
  deriving (Num, Fractional, Show)

instance Polynom RatioPoly where
  substitute (RatioPoly (n :% d)) x = substitute n x / substitute d x
  compose (RatioPoly (n :% d)) (RatioPoly inner) = 
    RatioPoly $ compose n inner % compose d inner

这种方案的缺点是使用时需要手动做RatioPoly的包装和解包，代码冗余度更高。

内容的提问来源于stack exchange，提问作者Wilco Verhoef