Haskell 来自 F# 的 RPN 计算器

Question

我是 Haskell 的新手，谁能建议我如何将 F# 中的以下程序重写为 Haskell，以便尽可能相似。

不知道如何在 Haskell 中定义堆栈数据类型。

谢谢

let calc input (stck:Stack<double>) =
    match input with
        | "*" -> stck.Push(stck.Pop() * stck.Pop())
        | "+" -> stck.Push(stck.Pop() + stck.Pop())
        | "-" -> stck.Push(stck.Pop() - stck.Pop())
        | "/" -> stck.Push(stck.Pop() / stck.Pop())
        | _ -> stck.Push(System.Convert.ToDouble(input))

let evalu (inputStr:string) =
    let stk = Stack<double>()

    let elem = inputStr.Split([|' '|])

    Array.iter (fun ent -> calc ent stk) elem
    stk.Pop()

//Call
Console.WriteLine(evalu("3 5 +"))

想要这样的东西：

calc input stck
    | input == '*' = stck.push(stck.pop * stck.pop)
    | input == '+' = stck.push(stck.pop + stck.pop)
    | input == '-' = stck.push(stck.pop - stck.pop)
    | input == '/' = stck.push(stck.pop / stck.pop)
    | otherwise   = stck.push(input)

main = calc "3 5 +" [] //Somehow do folding

Answer 1

这个（非常受欢迎的）教程解决了这个问题：

http://learnyouahaskell.com/functionally-solving-problems#reverse-polish-notation-calculator

Answer 2

这是一个非常基本的翻译：

module Main where

type Stack = [Double]

push :: Stack -> Double -> [Double]
push s v = v:s

pop :: Stack -> (Double, Stack)
pop []    = error "empty stack"
pop (v:s) = (v,s)

calc :: Stack -> String -> Stack
calc stck "+" = let (v1,stck') = pop stck
                    (v2,stck'') = pop stck'
                in push stck'' $ v1+v2
calc stck n = push stck $ read n

eval :: String -> Double
eval = head . foldl calc [] . words

main :: IO ()
main = print $ eval "3 5 +"

因为 .net 的 Stack 不是纯粹的我选择使用一个简单的列表作为替代，这当然意味着你必须线程 state （堆栈）通过你的计算（这是那些 let (v1,stck)... 部分的工作）

我认为这对初学者来说是最简单的 - 如果你稍微进步一点，你可能会回来并使用 state-monad 重新实现它（实际上我用它来伪装 let's）使它成为一个多一点 readable/beautiful

当然你必须为你的运营商添加其他案例

备注

对于格式错误的输入，这将失败（您的版本也是如此）- 如果您愿意，可以加入 Maybe（在 pop、calc 和 eval 中） ...

让它更好一点

如果您自己实施案例，您会发现 let ... pop ... push 内容重复了很多 - 所以让我们 DRY:

apply :: (Double -> Double -> Double) -> Stack -> Stack
apply op stack =
  let (a,stack')  = pop stack
      (b,stack'') = pop stack'
  in push stack'' (b `op` a)

calc :: Stack -> String -> Stack
calc stack "+" = apply (+) stack
calc stack "*" = apply (*) stack
calc stack "-" = apply (-) stack
calc stack "/" = apply (/) stack
calc stack n = push stack $ read n

另请注意，您必须反转操作，因为您 pop 的顺序错误

如果你不介意 `flip`ing:

calc :: String -> Stack -> Stack
calc "+" = apply (+)
calc "*" = apply (*)
calc "-" = apply (-)
calc "/" = apply (/)
calc n   = flip push $ read n

eval :: String -> Double
eval = head . foldl (flip calc) [] . words

这里有一个例子：

λ> eval "3 5 + 2 - 3 /"
2.0

Haskell 来自 F# 的 RPN 计算器

Haskell RPN calculator from F#

stack

f#

haskell

rpn

备注

让它更好一点

如果你不介意 `flip`ing:

Haskell 来自 F# 的 RPN 计算器

Haskell RPN calculator from F#

stack

f#

haskell

rpn

备注

让它更好一点

如果你不介意 fliping:

如果你不介意 `flip`ing: