2

我正在尝试在 Haskell 中实现一个 RPN 计算器。这是Learn You a Haskell中的一个练习。这是我的代码：

import Data.List
solveRPN :: String -> Int
solveRPN str = head $ foldl putStack [] (words str) 
         where putStack accumulator token 
            | token == "+" = pFunction (+)
            | token == "-" = pFunction (-)
            | token == "*" = pFunction (*)
            | token == "/" = pFunction (`div`)
            | otherwise    = accumulator ++ [read token :: Float]
            where pFunction function =  (int $ init accumulator) ++ [function argu1 argu2]
                  argu1 = last accumulator
                  argu2 = last $ init accumulator

该函数solveRPN首先将字符串拆分为标记。（例如："4 3 2 + *"-> ["4","3","2","+","*"]）然后，一个一个令牌被推入堆栈。如果遇到运算符，则堆栈中的最后两项由运算符处理，然后将产生的值放回堆栈中。当遍历整个列表时，堆栈中只剩下一项，这就是答案。

这里有一些问题：

  1. 在(int $ init accumulator)我想取消堆栈中的最后两个元素。有什么替代方法(int $ init accumulator)吗？

  2. 代码无法通过编译。GHC 说“输入时解析错误（”
    在这一行：| token == "/" = pFunction (div )。我怀疑问题可能来自pFunction。它的参数是一个运算符（或者我可以称它为函数吗？）我不确定“函数是否作为参数函数”在 Haskell 中是合法的。这合法吗？还有其他选择吗？

  3. 我在 GHCi 中做了一些实验，发现了一些奇怪的东西：

Prelude> let plus = (+) 
Prelude> :t (+) 
(+) :: Num a => a -> a -> a
Prelude> :t plus 
plus :: Integer -> Integer -> Integer

为什么加号的类型与（+）的类型不同？

感谢您的关注和耐心。（：

4

2 回答 2

2

在(int $ init accumulator)

你的意思是init $ init accumulator？话虽如此，您可以编写自己的dropLast2函数，该函数与列表相同init . init但仅遍历一次，例如

dropLast2 :: [a] -> [a]
dropLast2 []       = []
dropLast2 [_]      = []
dropLast2 [_,_]    = []
dropLast2 (x:xs) = x : dropLast2 xs

代码无法通过编译。

        | token == "/" = pFunction (`div`)

您使用反引号 (`) 是为了将具有两个参数的函数用作中缀函数。但是，通过在周围使用括号来div尝试立即取消它，这既有点不对劲，也是解析器错误。只需使用

        | token == "/" = pFunction div

反而。但是，有一件重要的事情。div的类型是

div :: Integral a => a -> a -> a

但是，您的累加器是Float. div不可能在这些上工作。但是，Float是Fractional该类的一个实例，因此您可以简单地使用(/)：

(/) :: Fractional a => a -> a -> a

因此得到

        | token == "/" = pFunction (/)

我在 GHCi 中做了一些实验，发现了一些奇怪的东西

(+)是Num班级的一部分。您plus不是任何函数的一部分，GHC 会尝试推断其类型。然后单态限制开始了。有关更多信息，请参阅编写 max 函数时的类型错误。

于 2014-02-10T13:43:50.520 回答
1

关于你的第一个问题：

我的印象是您使用列表的方式错误。如果将元素压入堆栈，则应使用:运算符将​​其添加到列表中。弹出前两个元素然后变成drop 2 stack，我认为这要好得多。

这样做也会更有效率，因为:它是一个恒定时间操作，而++第一个参数的大小（即堆栈的大小）是线性的。

于 2014-02-10T13:46:55.457 回答