HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Math eval function for Haskell

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
functionmathforhaskelleval

Problem

I recently finished reading Learn you a Haskell for great good!. Even though some topics are a bit over my head (Monads anyone?), I wanted to try my hand at a fairly difficult problem. I chose to write a eval function that correctly handles parenthesis and the order of operations. I think this is pretty good, but I can see some things that need improvement.

`module Eval where

data Token = Times | Div | Add | Sub | LPren | RPren | Number Float
deriving (Show, Eq)

tokenise :: String -> Token
tokenise n = case n of
"*" -> Times
"/" -> Div
"+" -> Add
"-" -> Sub
"(" -> LPren
")" -> RPren
_ -> Number $ read n

parse :: String -> [Token]
parse s = map tokenise $ tokens s

reduce :: [Token] -> Float
reduce tokens = let groups = prenGroups tokens
results = map reduce groups
leftover = substitute tokens results
orderOfOps = [Times, Div, Add, Sub]
in unpackNum $ head $ foldl (flip reduceAllOfOp) leftover orderOfOps

-- The expression passed to this function must be ONLY numbers an ops in proper form,
-- num, (op, num)*
reduceAllOfOp :: Token -> [Token] -> [Token]
reduceAllOfOp tok (x:op:y:rest) = if op == tok
then let xn = unpackNum x
yn = unpackNum y
oper = getOp op
in reduceAllOfOp tok ((Number $ oper xn yn):rest)
else x:op:(reduceAllOfOp tok (y:rest))
reduceAllOfOp _ toks = toks

-- substitute numbers in for prenthisis groups, pram 1 is the problem, pram 2 is a list of numbers
substitute :: [Token] -> [Float] -> [Token]
substitute ts [] = ts
substitute ts ns = let head' = takeWhile (/=LPren) ts
tail' = tail $ dropWhile (/=LPren) ts

Solution

If you aren't going to use actual compiler libraries—which would be the right move in production code, but maybe less interesting for learning—then you need an intermediate step between tokenizing and evaluation, which is to build tree structure representing your expression.

Whenever you have potentially nested structured in your data, such as parens around sub-expressions, you need to look to stacks and trees to manage them cleanly.

Context

StackExchange Code Review Q#121998, answer score: 4

Revisions (0)

No revisions yet.