Haskell 中的多项式

Question

周四我有一场关于函数式编程的考试，我很确定我必须用多项式做 TAD。我现在正在添加这样的多项式：

type Pol = [(Int,Int)] 

suma :: Pol -> Pol -> Pol
suma [] ys = ys
suma xs [] = xs
suma ((c1,g1):xs) ((c2,g2):ys)
    | g1 == g2  = ((c1+c2,g1):(suma xs ys))
    | g1 > g2 = ((c1,g1):(suma xs ((c2,g2):ys)))
    | g1 < g2 = ((c2,g2):(suma ((c1,g1):xs) ys))

它完美地工作，但老师不喜欢。她更喜欢这样做：

data Pol = P [(Int,Int)] deriving Show

一开始，我认为改变结构很容易，但事实并非如此，因为我在编译中遇到了很多麻烦。有人可以帮我吗？我尝试了这种方法，但它不起作用：

data Pol = P [(Int,Int)] deriving Show

suma :: Pol -> Pol -> Pol
suma (P []) (P ys) = P ys
suma (P xs) (P []) = P xs
suma (P ((c1,g1):xs)) (P ((c2,g2):ys))
    | g1 == g2  = P ((c1+c2,g1):suma (P xs) (P ys))
    | g1 > g2   = P ((c1,g1):(suma (P xs) (P ((c2,g2):ys))))
    | g1 < g2   = P ((c2,g2):(suma (P ((c1,g1):xs)) (P ys)))

我收到此错误：

ERROR file:.\Febrero 2011.hs:7 - Type error in application
*** Expression     : P (c1 + c2,g1) : suma (P xs) (P ys)
*** Term           : suma (P xs) (P ys)
*** Type           : Pol
*** Does not match : [a]

非常感谢！

Answer 1

如果某些事情不起作用，请在问题中解释原因。如果有编译器错误，请发布。

在本例中，问题是 suma 最后一个分支中的类型错误。看看

suma (P ((c1,g1):xs)) (P ((c2,g2):ys))
    | g1 == g2  = P ((c1+c2,g1):suma (P xs) (P ys))

P ((c1+c2,g1):suma (P xs) (P ys)) 中，您正在尝试创建 [(Int,Int) 类型的列表] 与

(c1+c2,g1):suma (P xs) (P ys)

您正在尝试构造一个列表，其头部为 (Int,Int) 类型，但尾部为 Pol 类型（结果类型suma）。其他情况也有类似的错误。

Answer 2

让 suma 在 List 上工作，这样：

suma :: [(Int,Int)] -> [(Int,Int)] -> [(Int,Int)]
suma [] ys = ys
suma xs [] = xs
suma ((c1,g1):xs) ((c2,g2):ys)
    | g1 == g2  = ((c1+c2,g1):(suma xs ys))
    | g1 > g2 = ((c1,g1):(suma xs ((c2,g2):ys)))
    | g1 < g2 = ((c2,g2):(suma ((c1,g1):xs) ys))

那么 Pol 的 Sum 可以定义为：

sumPol :: Pol -> Pol -> Pol
sumPol (P a) (P b) = P (suma a b)

如果你想要更时尚或更单子 :) 那么你可以让 Pol 成为单子并使用 do 表示法来做这些事情

Answer 3

首先，让我们考虑一下您的原始代码

type Pol = [(Int,Int)] 

suma :: Pol -> Pol -> Pol
suma [] ys = ys
suma xs [] = xs
suma ((c1,g1):xs) ((c2,g2):ys)
    | g1 == g2  = ((c1+c2,g1):(suma xs ys))
    | g1 > g2 = ((c1,g1):(suma xs ((c2,g2):ys)))
    | g1 < g2 = ((c2,g2):(suma ((c1,g1):xs) ys))

如果您这样做：

let p1 = [(5,0),(1,1),(7,2)]::Pol
let p2 = [(1,2),(3,1),(2,0)]::Pol

那么您会得到：

suma p1 p2
[(1,2),(3,1),(7,0),(1,1),(7,2)]

这不是“错误”，但这不是人们对两个多项式求和所期望的结果：您可能希望获得简化形式的结果：

[(7,0),(4,1),(8,2)]

一更多评论：你了解过 Haskell record 吗语法？我认为它可以简化你的工作并使事情变得清晰。这里有一个提示：

data Term = Term { coeff :: Int,
                   expnt :: Int
                 } deriving Show

data Pol = Pol { terms :: [Term] } deriving Show

有了这个，在不简化结果的情况下对两个多项式求和就像……连接它们的项一样简单:)……一切都可以显示：

Main> let p1 = Pol [Term 5 0, Term 1 1, Term 7 2]
Main> p1
Pol {terms = [Term {coeff = 5, expnt = 0},Term {coeff = 1, expnt = 1},Term {coeff = 7, expnt = 2}]}
Main> let p2 = Pol [Term 1 2, Term 3 1, Term 2 0]
Main> p2
Pol {terms = [Term {coeff = 1, expnt = 2},Term {coeff = 3, expnt = 1},Term {coeff = 2, expnt = 0}]}
Main> let p3 = sumpol p1 p2
Main> p3
Pol {terms = [Term {coeff = 5, expnt = 0},Term {coeff = 1, expnt = 1},Term {coeff = 7, expnt = 2},Term {coeff = 1, expnt = 2},Term {coeff = 3, expnt = 1},Term {coeff = 2, expnt = 0}]}

多项式的简化有点棘手，但这是一个很好的练习。

我希望这有帮助。