Haskell: 更好地理解代数数据类型

Question

我正在尝试构建一个代表多项式的代数数据类型。根据定义，整数常量是多项式，并且如果你将两个多项式相加或相乘，结果仍然是一个多项式。

我很难理解代数数据类型的工作原理，也不知道如何生成这个数据类型。我目前有：

data Poly = Const Int | 
            Add Poly Poly | 
            Mult Poly Poly

然而，我并不知道这是什么意思，也不知道如何使用它，我只是根据我看到的代数数据类型示例来学习。

我见过像下面这样的类型：

data Tree = NullT |
            Node Int Tree Tree

我觉得这更有意义，并且涉及到it技术。多项式的例子似乎太抽象，我不知道从哪里开始。

编辑：当我尝试执行简单的测试函数时，例如：

evalPoly :: Poly -> Int
evalPoly (Const n) = n

我遇到了一个错误。

*Polynomial> evalPoly Poly 1

<interactive>:25:10: Not in scope: data constructor ‘Poly’
*Polynomial> 

再次编辑：感谢您提供的所有建议和帮助，这些对我有所帮助，使我制作出了符合自己需求的东西！

- Aserian

---

你最好使用以下类似的代码：data Poly = Const Int | Var Char | Add Poly Poly | Mult Poly Poly | Pow Poly Poly。只需为每个所需操作添加一个新构造函数。 - bheklilr

你把类型（Poly）和它的构造器（Const，Add，Int）搞混了；Const 1 用来构造一个 Poly；而 Poly 1 则不行。 - daf

@daf 谢谢！@bheklilr 谢谢，这对我有所帮助。Pow 不只是 Pow Int 吗？ - Aserian

@bheklilr 谢谢，我明白了。我想对于这个小程序的目的，我不需要把多项式提高到多项式次幂，只需要显示多项式即可。感谢你的帮助！ - Aserian

就目前而言，你最好将单变量的多项式表示为元组列表：x^2 + 2x^7 = [(1, 2), (2, 7)] :: [(系数，指数)]。 - Noon Silk

Answer 1

这里提供一种与我之前发布的另一种解决方案不同的备选方案。

你似乎想为多项式创建一个ADT，而我会使用Map，但我们可以使用术语列表。首先导入一些内容：

import Data.Function (on)
import Data.List (sortBy, groupBy, foldl1')

在这种情况下，多项式是一个项的列表，按最高幂排序，而每个项都表示为 aX^n，用 X a n 表示。

newtype Poly a n = Poly {terms :: [Term a n]} deriving (Show)
data Term a n = X {coeff :: a, power :: n}  deriving (Eq,Show)

让我们制作一些简单的多项式：

zero = Poly []
x = Poly [X 1 1]

constant :: (Num a,Eq a,Num n) => a -> Poly a n
constant 0 = zero
constant a = Poly [X a 0]

一旦我们定义了Num实例，就可以通过写3*x^4来创建X 3 4。

对于多项式的标准操作是使用特定的x值进行求值。

subst :: (Num a, Integral n) => a -> Term a n -> a
subst x (X a n) = a * x ^ n

evalAt :: (Num a, Integral n) => a -> Poly a n -> a
evalAt x = sum . map (subst x) . terms

我希望能够映射系数，但我不想将其作为Functor的实例，因为这是一个经典的学生错误，会逐项应用操作，例如平方、三角函数或对数函数，或者取平方根，而实际上只有极少数事物，如标量乘法、微分和积分才能像这样工作。提供fmap会鼓励您做错误的事情，例如而不是(+ (constant 1))。

mapCoeffs :: (a -> b) -> Poly a n -> Poly b n
mapCoeffs f = Poly . map f' . terms
  where f' (X a n) = X (f a) n

我们需要进行项的加法和乘法，并将同类项合并。当我们将同类项合并时，按幂的逆序排序并省略系数为零的项。

addTerm (X a n) (X b m) | n == m = X (a+b) n
                        | otherwise = error "addTerm: mismatched powers" 
multTerm (X a n) (X b m) = X (a*b) (n+m)

collectLikeTerms :: (Num a, Ord n, Eq a) => Poly a n -> Poly a n
collectLikeTerms =  Poly . filter ((/= 0).coeff)            -- no zero coeffs
                         . map (foldl1' addTerm)            -- add the like powers
                         . groupBy ((==) `on` power)        -- group the like powers
                         . sortBy (flip compare `on` power) -- sort in reverse powers
                         . terms                            

现在我们可以创建实例：

instance (Eq a,Num a,Ord n,Num n) => Eq (Poly a n) where
   f == g = f - g == zero

instance (Eq a,Num a,Num n,Ord n) => Num (Poly a n) where
   fromInteger = constant . fromInteger
   signum (Poly []) = zero
   signum (Poly (t:_)) = constant . signum . coeff $ t
   abs =  mapCoeffs abs
   negate = mapCoeffs negate
   (+) = (collectLikeTerms.) . (Poly.) . ((++) `on` terms)
   (Poly ts) * (Poly ts') = collectLikeTerms $ Poly [multTerm t t' | t<-ts, t'<-ts']

实战应用：

ghci> 5*x^2 + 6*x^7 + 2
Poly {terms = [X {coeff = 6, power = 7},X {coeff = 5, power = 2},X {coeff = 2, power = 0}]}

- AndrewC

Answer 2

您似乎想为多项式创建一个ADT，但我更喜欢使用Map。首先要导入一些内容：

import qualified Data.Map as M
import Data.Function (on)

一个多项式是从x的幂到系数的映射。

newtype Poly a n = Poly {coeffMap :: M.Map n a} deriving (Show)
lift f = Poly . f . coeffMap

让我们制作一些简单的多项式：

zero = Poly M.empty                  -- none of the powers have non-zero coefficients
x = Poly $ M.singleton 1 1           -- x^1 has coefficient 1

constant 0 = zero
constant a = Poly $ M.singleton 0 a  -- x^0 has coefficient a

对于多项式来说，标准的做法是使用特定的 x 值进行计算。

这里的 fold 操作将部分计算得到的 b 和新项 a*x^n 相加：

evalAt :: (Num a, Integral n) => a -> Poly a n -> a
evalAt x = M.foldrWithKey (\n a b -> b + a*x^n) 0 . coeffMap

如果我们想使用Map函数，我们可以将它从Map n a提升到Poly n a。我想能够在系数上进行映射，但我不想将其作为Functor的实例，因为这是一个典型的学生错误，会导致错误的操作，例如平方、三角或对数函数的应用，或逐项取平方根，而实际上只有极少数的操作，如标量乘法、微分和积分才能像这样工作。提供fmap会鼓励您做错误的事情，例如fmap (+1)而不是(+ (constant 1))。

mapCoeffs :: (a -> b) -> Poly a n -> Poly b n
mapCoeffs f = lift (fmap f)

地图已经可以自动收集类似项，但我们需要省略系数为零的项：

strikeZeros :: (Num a,Eq a) => Poly a n -> Poly a n
strikeZeros =  lift $  M.filter (/= 0)                      

现在我们可以创建实例：

instance (Eq a,Num a,Ord n,Num n) => Eq (Poly a n) where
   f == g = f - g == zero

instance (Eq a,Num a,Num n,Ord n) => Num (Poly a n) where
   fromInteger = constant . fromInteger
   signum (Poly m) | M.null m = zero
                   | otherwise = let (n,a) = M.findMax m in 
                        Poly $ M.singleton n (signum a)
   abs =  mapCoeffs abs
   negate = mapCoeffs negate
   (+) = (strikeZeros.) . (Poly.) . ((M.unionWith (+)) `on` coeffMap)
   (Poly m) * (Poly m') = Poly $ 
          M.fromListWith (+) [(n+n',a*a') | (n,a)<-M.assocs m, (n',a')<-M.assocs m']

实际应用：

ghci> 3*x^4 + 6 + 2*x^7
Poly {coeffMap = fromList [(0,6),(4,3),(7,2)]}

- AndrewC