F# - a "simple" math formula solver or my first steps learning F#
As i earlier mentioned in my blog, F# is an awesome language and i want to try to build a domain logic with it. So I began to port an older ecommerce project of mine to F# with all the nice things like DDD, CQRS and Eventsourcing (or should I say "Ereignisquellenspeicherung" - at this current time Greg's favorite word, and i am responsible for that. :D )
Ereignisquellenspeicherung is my new favourite word.
— gregyoung (@gregyoung) May 19, 2018
Event-Sourcing = Ereignisquellenspeicherung :D
— DieselMeister (@DieselMeister) April 25, 2018
CQRS = Befehls- und Abfragenverantwortungsteilung :D
Muhahaha
Nevertheless, while i am porting my old project in my spare free time, i got to a requirement that the admin can add a formula to a product, which will set the actual price of the product, based on a so called "base price".
So for example: the awesome product hast a base price of 100 € and the admin will add some formula like "base * 1.05", so the actual price of the awesome product will be 105 €.
There are hundreds of math formula solvers i think and i had a open source F# math solver in the first place. but this wasn't compatible with .NET Core. So i decided, that it is a good lesson to write an math formula solver on my own. It is a good exercise and a I'll be able to blog about my experience.
I know there is nice parsing stuff in F#, but in that case I use Regex. But i will learn the parser later on.
So easy enough i thought and so i started to build a very simple formula solver in F#. The solver should work with plus, minus, multiply, divide and power. So my first approach was so simple, that it doesn't accept the simplest math rule: order before multiply and divide before plus and minus. So my second approach, which i describe soon in this post, should work with the simple math rule. And to complete this, yeah i add the support of brackets to it.
so what are the rules of the simple math solver?
- obey the simple order rule of math
- add the ability to use special "symbols/placeholders" like in the example "base" for the base price or something else like the exchange value of bitcoin or the current platin price or something.
First at all, i am new in F# and maybe i did something wrong or clumsy or dirty or way too complicated or even totally wrong. But it works and there is always room for improving. So please give me feedback.
Note: the solver has a problem with multiple power operations. So instead to resolve 2^2^3 to 256, it resolves it to 64. Because it resolves the formula from left to right and this edge case is not relevant in the domain. Maybe someone of you has a simple way to implement that.
So how should this solver works?
So basically and in my first try (the one without the order to solve math formula), i split the formula into pairs of a symbol and a value. And to be consistent, i add a leading "+" to the front of the formula, if there is a positive number. (in case of a negative first number, i had already a symbol)
1 + 2 * 3 - 4 / 5 ->
(+,1)
(+,2)
(*,3)
(-,4)
(/,5)
// or in case of a negative number
-1 + 2 * 3 ->
(-,1)
(+,2)
(*,3)
so this was it, if you don't want to have the correct order of operations in math. one function to replace any symbols like "base" with a value is not a problem.
I am using the RegexTypeProvider, if you wonder.
Listing split formula into pairs:
type MathPairRegex =
Regex< @"(?<MathSymbol>[\+\-\*\/\^])(?<Number>[\-]*[0-9.]*)" >
type IsMathSymbolRegex =
Regex< @"[\+\-\*\/\^\(\)]" >
let isMathSymbol (input:char) =
IsMathSymbolRegex().IsMatch(input.ToString())
let tryAddLeadingPlus (formula:string) =
let isFirstCharMath = formula.[0] |> isMathSymbol
if isFirstCharMath then formula
else "+" + formula
let splitFormula (formula:string) =
formula
|> tryAddLeadingPlus
|> MathPairRegex().TypedMatches
|> Seq.map (fun i -> (i.MathSymbol.Value,i.Number.Value))
As in F# you read from bottom to top. So the function at the bottom do what it's named for, and split the formula into the symbol and value pairs. In case of a mission math symbol at the front of the formula, the "tryAddLeadingPlus" function adds a + if it's necessary.
The nice thing of TypeProviders is, that it gives us property names from our data source. So in the SQL TypeProvider you get table names and table cloumns names as properties in your code.
In this case you get the named groups in the Regex as properties.
You will find "?<MathSymbol>" and "?<Number>" in the mapping function i.MathSymbol.Value and i.Number.Value. (Note: I called the value from the symbol and value pair here number, because it seems confusing, when i use "Value" as name in the Regex. It would end as i.Value.Value. That's not pretty.)
Now write a calculate function and the very simple solver is done.
Listing calculate sequence of symbol/value pairs:
let usCulture = new CultureInfo("en-us")
let (|ParsedDecimal|) value =
Decimal.Parse(value,usCulture)
let calculate (symbolValues:(string * string) seq) =
(0.0m,symbolValues)
||> Seq.fold (fun state item ->
match item with
|("+",(ParsedDecimal value)) ->
state + value
|("-",(ParsedDecimal value)) ->
state - value
|("*",(ParsedDecimal value)) ->
state * value
|("/",(ParsedDecimal value)) ->
state / value
|("^",(ParsedDecimal value)) ->
(decimal ((float state) ** (float value)))
| _ -> state
)
So the calculate function gets a sequence of symbol/value pairs and fold it to the result.
The C# developer knows "fold" as the "Aggregate"-Function in LINQ. So fold iterate to the sequence and perform a function that return the next "state" for the next item in the sequence.
"fold" needs a initial "state" a list of items and the function to perform.
In the case of the fold function i love the ||> (double pipe) operator, because it make the fold function more readable.
// without pipe
Seq.fold (fun state item -> // bla ...) initialState sequence
// with single pipe
sequence |> Seq.fold (fun state item -> // bla ...) initialState
// with the double pipe
(initialState,sequence) ||> Seq.fold (fun state item -> // bla ...)
See it for your self: if i had to describe the behavior, i would say: "Take the initial state and the sequence and fold it with "bla"."
So the next thing I use is a ActivePattern. With an ActivePattern you are able to perform operation to a value you want to math in a pattern match.
In that case i parse the Value from string to decimal, so i can use it directly and do the needed operation. I also need the us-en culture, because here in germany the decimal parser will use our number system and would parse "1.00" into "100", because we use "," as decimal not "."
Hey, and the external symbols like "base" oder "bitcoinRate" or "PlatinRate" or something?
i almost forget but it is very simple to do that.
Listing replace external symbol with values:
type SymbolToValue = SymbolToValue of string * decimal
let replaceSymbols symbolToValueList formula =
(formula,symbolToValueList)
||> List.fold (fun (state:string) (item:SymbolToValue) ->
let (SymbolToValue (symbol,value)) = item
state.Replace(symbol,value.ToString(usCulture))
)
So this function replaces all external symbols with values. So the input parameter is a list of symbol to values and the formula. This function iterates the list of symbols and fold with a string replace, so that in the end all symbols in the formula will be removed and replaced with actually values.
For example a list of symbols:
let symbols = [SymbolToValue ("base",100.0m);SymbolToValue ("BASE",100.0m);SymbolToValue ("Base",100.0m)]
The "Order" of rules of calculation
Yeah, the very simple formula solver is basically enough for very simple formulas, but there are rules and we want to obey them.
The strategy I want to use, is to reduce all higher operations than add and subtract to get a bunch of simple symbol/value pairs we put into our "calculate" method.
For example:
1 + 2 * (3 + 4) ^ 3
// first the brackets (3+4) -> 7
1 + 2 * 7 ^ 3
// now the power 7^3 -> 343
1 + 2 * 343
// now the multiply 2*343 -> 686
1 + 686
// we get the pairs
(+,1)
(+,686)
The Brackets
The Brackets are the first in line. So we need an Regex to extract all, what is inside a bracket and runs it to all other rules including the brackets rule. In the end, we want a list of symbols of plus and minus operation we can easily put into our "calculate" method, because in the end with only add and subtract operation we get to the point.
Listing of the function to resolve the Brackets:
type BracketsFilter = Regex< @"\((?<InsideBrackets>[0-9.\+\-\*\/\^]*)\)" >
let (|ContainsBrackets|NotContainsBrackets|) (str:string) =
let is = str.Contains("(") || str.Contains(")")
match is with
|true -> ContainsBrackets
|false -> NotContainsBrackets
let rec resolveBrackets formula =
let insideBracketsParts =
formula
|> BracketsFilter().TypedMatches
|> Seq.map (fun x -> x.InsideBrackets.Value)
let calculatedParts =
insideBracketsParts
|> Seq.map (fun formulaPart ->
(formulaPart |> sprintf "(%s)" ,formulaPart |> resolvePower |> resolveMultiply))
|> Seq.map (fun (part,multiresolved) ->
(part,multiresolved |> splitFormula))
|> Seq.map (fun (part,split) ->
(part,split |> calculate))
let resolvedFormula =
(formula,calculatedParts)
||> Seq.fold (fun state calculatedPart ->
let (formulaPart,resolvedPart) = calculatedPart
state |> replaceStringOnlyFirstHit formulaPart (resolvedPart |> decimalToSymbol)
)
match resolvedFormula with
| ContainsBrackets -> resolvedFormula |> resolveBrackets
| NotContainsBrackets -> resolvedFormula
First I use an active pattern to check, if the formula contains some brackets. And yeah if could done this in a simple if then, but it want to use active pattern and it makes the function at the end more understandable.
The function is recursively and runs as long brackets are there.
In the first step i extract all whats inside brackets with a Regex.
The Regex take at first the inner brackets, that's because the function must run recursively.
here you see how the regex works:
Now I take all the extracted formula parts, whats inside a bracket and map this into a tuple of the formula part itself as string with brackets sprintf "(%s)". That string do i need to replace it later the result of the calculation. The second part of the tuple contains the to add and subtract reducted partial formula. So I pipe the partial forumla to the "resolvePower" and the "resolveMultiply" functions.
Listing the calulatedParts function inside the resolveBrackets:
let calculatedParts =
insideBracketsParts
|> Seq.map (fun formulaPart ->
(formulaPart |> sprintf "(%s)" ,formulaPart |> resolvePower |> resolveMultiply))
|> Seq.map (fun (part,multiresolved) ->
(part,multiresolved |> splitFormula))
|> Seq.map (fun (part,split) ->
(part,split |> calculate))
Than I map this to the "splitFormula" function and than I map these to the "calculate" function.
The last mapping step is actually a folding step. So I replace the solved partial formulas with the result.
let resolvedFormula =
(formula,calculatedParts)
||> Seq.fold (fun state calculatedPart ->
let (formulaPart,resolvedPart) = calculatedPart
state |> replaceStringOnlyFirstHit formulaPart (resolvedPart |> decimalToSymbol)
)
I almost forget, there is a little helper function to replace a string only on the first hit. So i could avoid to replace parts multiple parts of the formula. Actually as I now think about it, maybe I cloud have used the normal replace function, because the resolved parts are the same. But now it is so as it is.
let replaceStringOnlyFirstHit (search:string) replace (input:string) =
let pos = input.IndexOf(search)
if pos < 0 then input
else
input.Substring(0,pos) + replace + input.[pos+search.Length..]
The last is only a fancy way to check if there are brackets left in the formula, so the function can be called recursively.
match resolvedFormula with
| ContainsBrackets -> resolvedFormula |> resolveBrackets
| NotContainsBrackets -> resolvedFormula
Power
The function has basically the same structure. It resolve the power operation.
Listing resolvePower function:
type PowerFilter = Regex< @"(?<Power>[\+\-\*\/\^][0-9.]*[\^]{1}[\-]{0,1}[0-9.]*)" >
let rec resolvePower formula =
let formula = formula |> tryAddLeadingPlus
let powerParts =
formula
|> PowerFilter().TypedMatches
|> Seq.map (fun x -> x.Power.Value)
let calculatedParts =
powerParts
|> Seq.map (fun formulaPart ->
let leadingMathSymbol = formulaPart.[0]
(formulaPart, formulaPart.[1..] |> splitFormula, leadingMathSymbol ))
|> Seq.map (fun (part,split,leadingMathSymbol) -> (part,split |> calculate,leadingMathSymbol))
let resolvedFormula =
(formula,calculatedParts)
||> Seq.fold (fun state calculatedPart ->
let (formulaPart,resolvedPart,leadingMathSymbol) = calculatedPart
state |> replaceStringOnlyFirstHit formulaPart (resolvedPart |> decimalToSymbol |> sprintf "%c%s" leadingMathSymbol)
)
if resolvedFormula.Contains("^") then resolvedFormula |> resolvePower
else resolvedFormula
The little difference is, that i remember the leading math symbol in front of the power operation, so i can add the symbol afterward to the result. Also I did not run any of this towards another rolver function like in the "resolveBrackets".
As i mentioned a formula like "2^2^3" results here in 64, the real result should according to wolfram alpha 256. This is because as I mentioned in the brackets part, the regex resolves from left to right. It is possible to change that behavior, but in our case it's overkill, because in the real world, nobody uses that to calculate a price. But maybe someone of you has an idea.
The both functions for brackets and power uses following little helper function:
let decimalToSymbol (dec:decimal) =
dec.ToString(usCulture)
Multiply and Divide
The function has also the same structure as the both others. It resolve multiply and divide operations.
Listing of the resolveMultipy function:
type MultiplyDivideFilter = Regex< @"(?<MultiplyDivide>[\+\-][0-9.]*[\*\/]{1}[\-]{0,1}[0-9.]*)" >
let (|ContainsMultiplyDivideSymbol|NotContainsMultiplyDivideSymbol|) (str:string) =
//let is = ["*";"/"] |> Seq.exists (fun symb -> symb |> str.Contains)
let is = str.Contains("*") || str.Contains("/")
match is with
|true -> ContainsMultiplyDivideSymbol
|false -> NotContainsMultiplyDivideSymbol
let decimalToSymbolWithPrefix (dec:decimal) =
let decStr = dec.ToString(usCulture)
if dec < 0.0m then decStr
else decStr |> sprintf "+%s"
let rec resolveMultiply formula =
let formula = formula |> tryAddLeadingPlus
let multiplyDivideParts =
formula
|> MultiplyDivideFilter().TypedMatches
|> Seq.map (fun x -> x.MultiplyDivide.Value)
let calculatedParts =
multiplyDivideParts
|> Seq.map (fun formulaPart -> (formulaPart, formulaPart |> splitFormula))
|> Seq.map (fun (part,split) -> (part,split |> calculate))
let resolvedFormula =
(formula,calculatedParts)
||> Seq.fold (fun state calculatedPart ->
let (formulaPart,resolvedPart) = calculatedPart
state |> replaceStringOnlyFirstHit formulaPart (resolvedPart |> decimalToSymbolWithPrefix)
)
match resolvedFormula with
| ContainsMultiplyDivideSymbol -> resolvedFormula |> resolveMultiply
| NotContainsMultiplyDivideSymbol -> resolvedFormula
There is the little active pattern function to have an fancy way to check if there are multiply or divide symbols in the formula (and a commented fancy way to check this more functional ... overkill I know, but I am learning).
The other helper function converts a decimal to a string with maybe a leading + if the result is positive. This i need, because maybe in front of the part I resolve is another number. So look, why i do that:
1+2*3
// split +2*3
(+,2)
(*,3)
// calculate and replace
// without leading + the result would be 6
// so replace +2*3 with 6 i've got
16
// with leading + i got
1+6
I could have worked with the "leadingMathSymbol" from the power part, it also does the trick. But in that case the function to solve multiply and divide was written a little bit earlier than the resolve power function.
So that's because i have this little helper.
In this function there will be alway added a + in front of the formula when there is no other math symbol in front. that's because in most cases the formula will not start with a symbol, and the function must split the formula into pairs and that will fail, when the first number has no leading math symbol.
Now compose to the one and only calculation function
let calculateFormula formula symbolToValueList =
let valid = formula |> formulaValidator symbolToValueList
if (not valid) then
Result.Error "invalid formula"
else
formula
|> removeSpaces
|> replaceSymbols symbolToValueList
|> resolveBrackets
|> resolvePower
|> resolveMultiply
|> splitFormula
|> calculate
|> Result.Ok
As you see here. I have a also a validation function and some helpers like "removeSpaces" to get the formula well formed into my functions.
So that's all. Maybe a few words to the regex i used.
MathPairRegex
(?<MathSymbol>[\+\-\*\/\^])(?<Number>[\-]*[0-9.]*)
There are 2 groups the allowed math symbols are +,-,*,/,^ and the number. Allowed are only 0-9 and . and maybe a - in front
BracketsFilter Regex
\((?<InsideBrackets>[0-9.\+\-\*\/\^]*)\)
The bracket filter is easy, give me all allowed characters inside a bracket.
PowerFilter Regex
(?<Power>[\+\-\*\/\^][0-9.]*[\^]{1}[\-]{0,1}[0-9.]*)
The power filter gives you every math symbol before the first number, than the first number, the power symbol, maybe a minus and the second number.
MultiplyDivideFilter Regex
(?<MultiplyDivide>[\+\-][0-9.]*[\*\/]{1}[\-]{0,1}[0-9.]*)
The MultiplyDivideFilter takes a always a number with a leading + or - than at least a * or / and maybe a - and a value
That's all.
I hope you read at least to the end. So this was my first journey to F# to solve a business rule.
I'll be please if you leave a comment or contact me for further discussions, help, ideas, critics or at least nice words.
oh. and the full listing you will find here, until i setup my github page.
Full Listing:
#r "..[here the path to the regex type provider dll].."
open System.Text.RegularExpressions
open System.Linq
open System
open System.Globalization
open FSharp.Text.RegexProvider
//Simple Parser for the price formula to be independent of an heavy weight dependency
type MathPairRegex = Regex< @"(?<MathSymbol>[\+\-\*\/\^])(?<Number>[\-]*[0-9.]*)" >
type AllowedFormulaSymbolsRegex = Regex< @"[0-9.\+\-\*\/\^ \(\)]" >
type IsMathSymbolRegex = Regex< @"[\+\-\*\/\^\(\)]" >
type BracketsFilter = Regex< @"\((?<InsideBrackets>[0-9.\+\-\*\/\^]*)\)" >
type PowerFilter = Regex< @"(?<Power>[\+\-\*\/\^][0-9.]*[\^]{1}[\-]{0,1}[0-9.]*)" >
type MultiplyDivideFilter = Regex< @"(?<MultiplyDivide>[\+\-][0-9.]*[\*\/]{1}[\-]{0,1}[0-9.]*)" >
let isMathSymbol (input:char) =
IsMathSymbolRegex().IsMatch(input.ToString())
type SymbolToValue = SymbolToValue of string * decimal
let usCulture = new CultureInfo("en-us")
let formulaValidator symbolToValueList formula =
let clearedFormula:string =
(formula,symbolToValueList)
||> List.fold (fun (state:string) (item:SymbolToValue) ->
let (SymbolToValue (symbol,_)) = item
state.Replace(symbol,"")
)
let countMatches =
AllowedFormulaSymbolsRegex().Matches(clearedFormula).Count
let onlyAllowedSymbols = (countMatches = clearedFormula.Length)
if not onlyAllowedSymbols then false
else
// count the brackets
let openBracketCount = clearedFormula.Count(fun x-> x = '(')
let closedBracketsCount = clearedFormula.Count( fun x -> x = ')')
openBracketCount = closedBracketsCount
let replaceSymbols symbolToValueList formula =
(formula,symbolToValueList)
||> List.fold (fun (state:string) (item:SymbolToValue) ->
let (SymbolToValue (symbol,value)) = item
state.Replace(symbol,value.ToString(usCulture))
)
let removeSpaces (formula:string) = formula.Replace(" ","")
let tryAddLeadingPlus (formula:string) =
let isFirstCharMath = formula.[0] |> isMathSymbol
if isFirstCharMath then formula
else "+" + formula
let splitFormula (formula:string) =
formula
|> tryAddLeadingPlus
|> MathPairRegex().TypedMatches
|> Seq.map (fun i -> (i.MathSymbol.Value,i.Number.Value))
let (|ParsedDecimal|) value =
Decimal.Parse(value,usCulture)
let calculate (symbolValues:(string * string) seq) =
(0.0m,symbolValues)
||> Seq.fold (fun state item ->
match item with
|("+",(ParsedDecimal value)) ->
state + value
|("-",(ParsedDecimal value)) ->
state - value
|("*",(ParsedDecimal value)) ->
state * value
|("/",(ParsedDecimal value)) ->
state / value
|("^",(ParsedDecimal value)) ->
(decimal ((float state) ** (float value)))
| _ -> state
)
let (|ContainsMultiplyDivideSymbol|NotContainsMultiplyDivideSymbol|) (str:string) =
//let is = ["*";"/"] |> Seq.exists (fun symb -> symb |> str.Contains)
let is = str.Contains("*") || str.Contains("/")
match is with
|true -> ContainsMultiplyDivideSymbol
|false -> NotContainsMultiplyDivideSymbol
let decimalToSymbolWithPrefix (dec:decimal) =
let decStr = dec.ToString(usCulture)
if dec < 0.0m then decStr
else decStr |> sprintf "+%s"
let decimalToSymbol (dec:decimal) =
dec.ToString(usCulture)
let replaceStringOnlyFirstHit (search:string) replace (input:string) =
let pos = input.IndexOf(search)
if pos < 0 then input
else
input.Substring(0,pos) + replace + input.[pos+search.Length..]
// resolve Multiply
let rec resolveMultiply formula =
let formula = formula |> tryAddLeadingPlus
let multiplyDivideParts =
formula
|> MultiplyDivideFilter().TypedMatches
|> Seq.map (fun x -> x.MultiplyDivide.Value)
let calculatedParts =
multiplyDivideParts
|> Seq.map (fun formulaPart -> (formulaPart, formulaPart |> splitFormula))
|> Seq.map (fun (part,split) -> (part,split |> calculate))
let resolvedFormula =
(formula,calculatedParts)
||> Seq.fold (fun state calculatedPart ->
let (formulaPart,resolvedPart) = calculatedPart
state |> replaceStringOnlyFirstHit formulaPart (resolvedPart |> decimalToSymbolWithPrefix)
)
match resolvedFormula with
| ContainsMultiplyDivideSymbol -> resolvedFormula |> resolveMultiply
| NotContainsMultiplyDivideSymbol -> resolvedFormula
// resolve power
let rec resolvePower formula =
let formula = formula |> tryAddLeadingPlus
let powerParts =
formula
|> PowerFilter().TypedMatches
|> Seq.map (fun x -> x.Power.Value)
let calculatedParts =
powerParts
|> Seq.map (fun formulaPart ->
let leadingMathSymbol = formulaPart |> Seq.head
(formulaPart, formulaPart.[1..] |> splitFormula, leadingMathSymbol ))
|> Seq.map (fun (part,split,leadingMathSymbol) -> (part,split |> calculate,leadingMathSymbol))
let resolvedFormula =
(formula,calculatedParts)
||> Seq.fold (fun state calculatedPart ->
let (formulaPart,resolvedPart,leadingMathSymbol) = calculatedPart
state |> replaceStringOnlyFirstHit formulaPart (resolvedPart |> decimalToSymbol |> sprintf "%c%s" leadingMathSymbol)
)
if resolvedFormula.Contains("^") then resolvedFormula |> resolvePower
else resolvedFormula
let (|ContainsBrackets|NotContainsBrackets|) (str:string) =
let is = str.Contains("(") || str.Contains(")")
match is with
|true -> ContainsBrackets
|false -> NotContainsBrackets
let rec resolveBrackets formula =
let insideBracketsParts =
formula
|> BracketsFilter().TypedMatches
|> Seq.map (fun x -> x.InsideBrackets.Value)
let calculatedParts =
insideBracketsParts
|> Seq.map (fun formulaPart -> (formulaPart |> sprintf "(%s)" ,formulaPart |> resolvePower |> resolveMultiply))
|> Seq.map (fun (part,multiresolved) -> (part,multiresolved |> splitFormula))
|> Seq.map (fun (part,split) -> (part,split |> calculate))
let resolvedFormula =
(formula,calculatedParts)
||> Seq.fold (fun state calculatedPart ->
let (formulaPart,resolvedPart) = calculatedPart
state |> replaceStringOnlyFirstHit formulaPart (resolvedPart |> decimalToSymbol)
)
match resolvedFormula with
| ContainsBrackets -> resolvedFormula |> resolveBrackets
| NotContainsBrackets -> resolvedFormula
let calculateFormula formula symbolToValueList =
let valid = formula |> formulaValidator symbolToValueList
if (not valid) then
Result.Error "invalid formula"
else
formula
|> removeSpaces
|> replaceSymbols symbolToValueList
|> resolveBrackets
|> resolvePower
|> resolveMultiply
|> splitFormula
|> calculate
|> Result.Ok