haskell 反向波兰表示法

Question

作为 haskell 的新手，我决定尝试实现一个迷你反向抛光符号函数：

接收类型为 int 的 list 和字符串运算符 ('*','+','/','-')

将运算符应用于 tail 元素和 tail-1 元素

return 结果 list 弹出操作中涉及的两个元素，结果元素附加到尾部，如下所示：

Where e0 = original element at index 0

r = result of the operation:

result = [e0,e1,e2...r] (elements popped off: eN, eN-1)

这是我目前的代码：

import Data.List
import System.IO

step :: [Int] -> String -> [Int]
step stack operator
    | (x:y:ys) "*" = (x * y):ys
    | (x:y:ys) "+" = (x + y):ys
    | (x:y:ys) "-" = (x - y):ys
    | (x:y:ys) "/" = (x / y):ys

它给了我以下编译错误：

• Couldn't match expected type ‘[Char] -> Bool’
                  with actual type ‘[a3]’
    • The function ‘x : y : ys’ is applied to one argument,
      but its type ‘[a3]’ has none
      In the expression: (x : y : ys) "/"
      In a stmt of a pattern guard for
                     an equation for ‘step’:
        (x : y : ys) "/"

我认为这是我语法错误的结果，欢迎任何帮助！

Answer 1

你已经正确地实现了这个功能，但是你的语法有点错误——你在你想使用模式匹配的时候使用了守卫：

模式匹配用于将一个参数分解成更小的部分或分几种情况处理；而
Guards 用于 select 基于布尔条件的函数的一个分支，类似于 if/then/else 表达式。（因此守卫的条件必须是 Bool 类型的有效表达式。）

在你的代码中，你使用了守卫，但你真的想要模式匹配，就像这样：

step :: [Int] -> String -> [Int]
step (x:y:ys) "*" = (x * y):ys
step (x:y:ys) "+" = (x + y):ys
step (x:y:ys) "-" = (x - y):ys
step (x:y:ys) "/" = (x / y):ys

但是这样还是会报错：

* No instance for (Fractional Int) arising from a use of `/'
* In the first argument of `(:)', namely `(x / y)'
  In the expression: (x / y) : ys
  In an equation for `step': step (x : y : ys) "/" = (x / y) : ys

这个错误很明显：您试图 / 一个整数，但整数不是 Fractional，所以您不能这样做。如果要整数除法，可以用div x y代替，否则可以在类型签名中将Int改为Float，允许非整数值

但是，即使进行了此更改，仍然存在一个微妙的错误：如果列表中的元素少于两个，或者使用了不受支持的运算符，会发生什么情况？此处正确的做法是在末尾使用 step _ _ = (something) 进行模式匹配，其中 _ 是一种匹配任何内容的特殊语法。（或者你也可以使用 step stack operator = (something)，如果你想返回参考 stack 和 operator 来获取错误信息。

编辑： 在下面的评论中，@chepner 建议了另一种同时使用模式匹配和守卫的方法：

step :: [Int] -> String -> [Int]
step (x:y:ys) op
    | op == "*" = (x * y):ys
    | op == "+" = (x + y):ys
    -- etc.
    | otherwise = (some error case)

这又说明了两者的区别：模式匹配用于将第一个参数分解为x、y和ys，而守卫则与布尔条件一起使用（ otherwise 实际上在 Prelude 中被定义为等于 True).

haskell 反向波兰表示法

haskell reverse polish notation

haskell

functional-programming

postfix-notation