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

Question

我正在尝试构建表示多项式的代数数据类型。给定整数常量是多项式的定义，并且如果您将两个多项式相加或将两个多项式相乘，则会得到一个多项式。

我很难理解代数数据类型的一般工作方式以及我将如何着手生成它。我现在有

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

但是我什至不知道这意味着什么或如何使用它，我只是放弃我见过的代数数据类型的例子。

我见过这样的类型

data Tree = NullT |
            Node Int Tree Tree

这对我来说更有意义，以及如何使用它。多项式的例子看起来太抽象了，我不知道从哪里开始。

编辑:当我尝试实现简单的测试功能时:

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

我遇到了错误

*Polynomial> evalPoly Poly 1

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

再次编辑:感谢您的所有建议和帮助，它帮助我制作了符合我的目的的东西!

Answer 1

您似乎想为多项式创建 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 值对其进行计算。

此处的折叠采用部分计算的 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)

map 已经自动收集相似的项，但我们要忽略系数为零的项:

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)]}