表示 Haskell 中的交换半群多项式

Question

我正在尝试表示如下术语：

a0 <> a1 <> ... <> an-1

其中 ai 必须是交换半群的元素。为此，可以选择如下数据表示形式：

newtype SemigroupPolynomial a = SP Map a Integer

其中地图包含多项式的不同项及其计数。

这样，我们就可以表示和

3 + 3 + 6

as（假设 OverloadedLists）：

SP [(3, 2), (6, 1)]

但我们也可以表示这样的术语：

3 * 3 * 6

SemigroupPolynomial 可以是 Semigroup 的实例：

instance ??? a => Semigroup (SemigroupPolynomial a) where
    (MP p0) <> (MP p1) = 
        MP $ Map.filter (0/=) $ Map.unionWith (+) p0 p1

不，问题是我必须在 ??? 中加入哪些约束，以便：

<> 运算是可交换和结合的。
它可以用来表示和和乘积，如上例所示。

关于如何表示可交换幺半群的类似问题 was already asked here。然而，约束 (Abelian m, Monoidal m) 似乎太强了（我不需要零元素），它会阻止我用它来表示产品。

Answer 1

正如@leftroundabout 评论的那样，您不需要 此处的约束。不要被 "constraint" 这个词所迷惑。在 Haskell 中，约束的主要目的不是以某种方式约束特定类型或操作的行为。相反，它将函数将接受的类型集限制为支持一组操作的类型。

当我写的时候：

fmapTwice :: (Functor f) => (a -> a) -> f a -> f a
fmapTwice f = fmap (f . f)

我并没有真正限制类型 f 像仿函数一样工作并遵守仿函数所需的规则。相反，我将 fmapTwice 函数限制为仅适用于支持 fmap 操作的类型 f。

没有什么能阻止一些混蛋写作：

data Foo a = Foo a | NoFoo deriving (Show)
instance Functor Foo where
    fmap _ _ = NoFoo   -- invalid functor violates:  fmap id = id

并将我的函数应用到这个无效的仿函数：

> fmapTwice (*2) (Foo 10)
NoFoo
>

Haskell 依靠程序员纪律来确保声明为具有 Functor 实例的东西是行为良好的函子。

在您的示例中，实例：

import Data.Semigroup
import qualified Data.Map as Map
import Data.Map.Strict (Map)

data SemigroupPolynomial a = SP (Map a Integer) deriving (Show)
instance (Ord a) => Semigroup (SemigroupPolynomial a) where
    (SP p0) <> (SP p1) = 
        SP $ Map.filter (0/=) $ Map.unionWith (+) p0 p1

不需要除 Ord a 以外的任何约束，以确保 a 可以用作 Map 键。

现在，由您来确保只使用 SemigroupPolynomial 来表示交换运算：

foldSP :: (a -> a -> a) -> SemigroupPolynomial a -> a
foldSP f (SP m) = foldr1 f $ concatMap (\(a, n) -> replicate (fromIntegral n) a)
                                       (Map.assocs m)

main = do let sp = singleton 3 <> singleton 3 <> singleton 6
          print sp
          print $ foldSP (*) sp
          print $ foldSP (+) sp
          print $ foldSP (-) sp   -- wrong, but it's your own damn fault

如果你想以某种方式将交换性要求引入你的数据类型，一种方法（根本不涉及 Haskell "constraints"）是这样写：

data CommutativeOp a = CO (a -> a -> a)
foldSP :: CommutativeOp a -> SemigroupPolynomial a -> a
foldSP (CO f) (SP m) = <same as above>

现在，只要你在写的时候意识到：

plusOp = CO (+)
timesOp = CO (*)

您正在声明 (+) 和 (*) 是交换运算，这将确保 foldSP 仅应用于此类运算：

main = do let sp = singleton 3 <> singleton 3 <> singleton 6
          print $ foldSP plusOp sp
          print $ foldSP timesOp sp

如果你想以某种方式在类型 a 上引入交换约束以确保 SemigroupPolynomial a 是有效的表示，那么你不能对 a 等于Int，显然，因为这取决于折叠使用的是哪种二元操作Int -> Int -> Int。

相反，您需要将操作嵌入到类型中，可能使用代表操作的 newtype，例如 Data.Semigroup 中的 Sum 或 Product。然后，你可以引入一个类型class（没有操作）来表示交换约束：

class Commutative a
instance Commutative (Sum a)
instance Commutative (Product a)
instance (Ord a, Commutative b) => SemigroupPolynomial b where
    ...definition on (<>) as above...

现在折叠操作将使用新类型中隐含的操作（这里，只使用 monoid 实例）：

foldSP' :: (Monoid a) => SemigroupPolynomial a -> a
foldSP' (SP m) = mconcat $ concatMap (\(a, n) -> replicate (fromIntegral n) a)
                                     (Map.assocs m)

也许这就是您想要的。如果是这样，完整的示例如下所示：

import Data.Semigroup
import qualified Data.Map as Map
import Data.Map.Strict (Map)

newtype SemigroupPolynomial a = SP (Map a Integer) deriving (Show)

class Commutative a
instance Commutative (Sum a)
instance Commutative (Product a)
instance (Ord a, Commutative a) => Semigroup (SemigroupPolynomial a) where
    (SP p0) <> (SP p1) = 
        SP $ Map.filter (0/=) $ Map.unionWith (+) p0 p1

singleton :: a -> SemigroupPolynomial a
singleton x = SP $ Map.singleton x 1

foldSP' :: (Monoid a) => SemigroupPolynomial a -> a
foldSP' (SP m) = mconcat $ concatMap (\(a, n) -> replicate (fromIntegral n) a)
                                     (Map.assocs m)

main = do let sp1 = singleton (Sum 3) <> singleton (Sum 3) <> singleton (Sum 6)
          print sp1
          print (foldSP' sp1)
          let sp2 = singleton (Product 3) <> singleton (Product 3) 
                          <> singleton (Product 6)
          print sp2
          print (foldSP' sp2)

Answer 2

你在那里构建的是一个自由的幺半群，它又只是一个列表。您可能会使用 [(a, Integer)] 而不是地图，这对于某些用例来说会很好。由于 Haskell 没有依赖类型，我怀疑在类型方面会有更好的选择。

No the question is which constraints do I have to put in ??? so that:

The <> operation is commutative and associative.

It can be used to represent sums and products, as exemplified above.

您可能应该创建一个 Ring 类型类，或者使用 numeric-prelude. That will let users know your data type is associative, and has addition and multiplication. There's not any great type-level way to indicate these to my knowledge. You could use a property test to make sure that everything worked via hspec 或类似库的类型类。

However it seems that the constraint (Abelian m, Monoidal m) might be too strong (I don't require a zero element), and it will prevent me to use this to represent products.

没有与“超过”半群的多项式相关联的代数结构，因此您可能必须自己实现它。既然你说 <> 是可交换的，你的元素将满足 Abelian m。只是增加一个单位的问题

表示 Haskell 中的交换半群多项式

Representing commutative semigroups polynomials in Haskell

haskell

algebra

symbolic-math