3
0
This challenge is about Haskell point-free style polynomial functions.
Although you don't need to know Haskell language to do this challenge, Haskellers might have an advantage here.
Point-free means roughly that variables(points) are not named and the function is created from compositions of others functions.
For example, in Haskell, the function f : x->x+1 can be defined by:
f x = x+1 which uses the variable x and is not point-free. But it can be simplified to its point-free version: f=(+1). Likewise, you have f x=x^k -> f=(^k), and f x=x*k -> f=(*k), f x y=x*y -> f=(*)
More complex functions can be constructed using the Haskell's function composition operator (.):
f x = x->2*x+1 is converted to f = (+1).(*2): Multiply by 2 then add 1.
In this challenge you will have to create a point-free style Haskell code generator. This generator will take a polynomial function of multiple variables as input and output corresponding code in Haskell language and in point-free style.
This is way harder than the previous simple functions, so if you don't know Haskell at all, or if you are not comfortable with operators (.), (>>=), (<*>) on functions, You should follow the Construction Process which is detailled bellow or start directly from its Python Implementation.
Example
Say you want to write the polynomial function x, y -> x²+xy+1 point-free.
Your program might output the folowing code:
((<*>).(.)((<*>).(.)(+))) -- sum 2 functions of 2 variables
(
((<*>).(.)((<*>).(.)(+))) -- sum 2 functions of 2 variables
(
(
((.)((.(^0)).(*))) -- g x y = y^0 * f x => g x y = x^2
(((.(^2)).(*))(1)) -- f x = 1*x^2
)
)
(
((.)((.(^1)).(*))) -- g x y = y^1 * f x => g x y = x*y
(((.(^1)).(*))(1)) -- f x = 1*x^1
)
)
(
((.)((.(^0)).(*))) -- g x y = y^0 * f x => g x y=1
(((.(^0)).(*))(1)) -- f x = 1*x^0
)
This is a really ugly yet valid Haskell code, and this is really not the shortest one ((.).(.)(+1).(*)<*>(+) works as well), but we will see how it can be generalized to any multivariable polynomial.
Construction Process:
One possible algorithm is to first write each monomial function in point-free style (step 1), then create operators to add functions two at a time (step 2), and apply this to the list of monomials, writing f+g+h as (f+(g+h)) (step 3).
Write each monomial, taking each of the factors successively. Example:
11*a^12*b^13*c^14.- Start with
(11), a 0-argument function. - Take the previous function
f0and write((.(^12)).(*))(f0); this is a 1-argument functiona->11*a^12 - Take the previous function
f1and write((.)((.(^13)).(*)))(f1); this is a 2-argument functiona->b->11*a^12*b^13. - Finally, take the previous function
f2and write((.)((.)((.(^14)).(*))))(f2). Thusa->b->c->11*a^12*b^13*c^14is converted to point-free style as((.)((.)((.(^14)).(*))))(((.)((.(^13)).(*)))(((.(^12)).(*))(11))). - In general, continue transforming
fto something of the form((.) ((.) ((.) ... ((.(^k)).(*)) ))) (f)until your monomial is built and takes the desired number of arguments. - Warning: If using this construction algorithm, each monomial must take the same number of arguments. Add some
^0for missing variables (a^2*c^3->a^2*b^0*c^3) - You can test your monomial generator here with this example and the next iteration: Try it online!
- Start with
Create the operator \$O_n\$ that adds two functions of \$n\$ arguments:
- \$O_0\$ is
(+) - For \$n\geq0\$, \$O_{n+1}\$ can be constructed recursively as
((<*>).(.)( O_n )) - E.g.
((<*>).(.)(((<*>).(.)(+))))adds two 2-argument functions.
- \$O_0\$ is
Chain the addition: The operator from step 2 only adds two monomials, so we must manually fold addition. For example, for monomials f, g, h, write
f+g+h=>O_n(f)( O_n(g)( h ) )replacing f, g, and h with their point-free equivalents from step 1, and \$O_n\$ by the correct operator from step 2 depending on the number of variables.
Implementation in Python
This is an ungolfed implementation in Python 3 which reads polynomials as list of monomials where monomial is a list of integers:
def Monomial(nVar,monoList):
if nVar==0:
return "({})".format(monoList[0])
else:
left = "((.(^{})).(*))"
mono = "({})".format(monoList[0])
for i in range (0,nVar):
p = monoList[i+1] if i+1<len(monoList) else 0
mono = left.format(p) + "(" + mono + ")"
left = "((.)" + left + ")"
return mono
def Plus(nVar):
if nVar==0:
return "(+)"
else:
return "((<*>).(.)(" + Plus(nVar-1) + "))"
def PointFree(l):
nVar = 0
for monoList in l:
if nVar<len(monoList)-1: nVar = len(monoList)-1
pointfree = Monomial(nVar,l[0])
plusTxt = Plus(nVar)
for monoList in l[1:]:
pointfree = plusTxt + "(" + Monomial(nVar,monoList) + ")(" + pointfree + ")"
return pointfree
Input
The input is the polynomial function to be converted.
The input format shall consist of a list of Integers in any format you want.
For example, you might define the polynomial 5*a^5+2*a*b^3+8 as the list [[5,5,0],[2,1,3],[8]]
Output code
The output is the Haskell code for that polynomial as a function of n Integers,
written in point-free style with only numeric literals and base functions(no Import).
Of course, the above process and implementation comply to these rules.
For Haskell programmers, this means no list comprehension, no lambdas and only Prelude functions(no import, language extensions..):
(+) (-) (*) (^) (.) (<*>) (>>=) flip sum zip uncurry curry ($) ...
Test cases
Your program should work for all valid inputs, but will be scored on on these five polynomials:
f1 a b c d = 5*a^4*b^3*c^2 + a^2*b^3*c^4*d^5
f2 a b c = -5*a^5*c^8 + 3*b^3*c^4 + 8
f3 a b = 5*a^5+3*b^3+8
f4 a = a^3+a^2+a+1
f5 = 1+2-3
Tests cases with the Python code given above:Try it online!
Once you have run your program on these samples, copy/paste your output code into the following program (in the "Code" section) and run it in order to check your outputs:
If your functions are correct, it will output:
f1 : +++ OK, passed 100 tests.
f2 : +++ OK, passed 100 tests.
f3 : +++ OK, passed 100 tests.
f4 : +++ OK, passed 100 tests.
f5 : +++ OK, passed 100 tests.
Scoring
Code length + (sum of the test cases output length)/8.
-300 if your program consist in a point-free style Haskell function (with the same rules as for output).
I'll give a Bounty of 250 points if you beat my score of 73.125 (272 + 809/8 - 300).
The Python solution given above is 797 bytes long, and outputs functions of length: 245, 282, 180, 132, and 24 so the score would be 797 + (245+282+180+132+24)/8 = 904.875.
The smallest score wins!!
Damien
Posted 2019-07-05T09:31:12.993
Reputation: 2 407
Comments are not for extended discussion; this conversation has been moved to chat.
– James – 2019-07-11T17:05:18.837