mercoledì 13 ottobre 2010

RPN calculator without stack

I'm tring to write an RPN calculator that do not use a stack (a part from the recursion callstack itself).

While it seem easy at a first look, it's not.

I asked some question about the approach on the #haskell freenode.net channel and got an interesting link from mm_freak and a wonderful solution from sipa.

data RPN = Const Float | Op (Float -> RPN)

count :: RPN -> Int -> Int
count (Const _) i = i
count (Op f) i = count (f 0) (1 + i)

instance Show RPN where
  show (Const v) = show v
  show q = "<<" ++ (show $ count q 0) ++ "-ary function>>"

infixr 3 @@

(@@) :: RPN -> RPN -> RPN
_ @@ (Const v) = Const v
(Const v) @@ (Op f) = f v
(Op f1) @@ r = Op (\v -> f1 v @@ r)

rpnBinOp :: (Float -> Float -> Float) -> RPN
rpnBinOp op = Op (\a -> Op (\b -> Const $ b `op` a))
rpnUnOp :: (Float -> Float) -> RPN
rpnUnOp op = Op (\a -> Const $ op a)

push :: Float -> RPN
push v = Const v
rpnAdd = rpnBinOp (+)
rpnSub = rpnBinOp (-)
rpnMult = rpnBinOp (*)
rpnNeg = rpnUnOp negate

main = do
  let rpn = push 2 @@ push 3 @@ rpnSub @@ push 5 @@ rpnMult @@ rpnNeg
  print rpn



Even if the solution is not still what I'm looking for, it's extremely clear and mind opening.

I blogged it for further studies...

Nessun commento:

Posta un commento