#StackBounty: #code-challenge #polynomials #functional-programming #haskell Point-free madness

Bounty: 250

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
    )

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).

  1. 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 f0 and write ((.(^12)).(*))(f0); this is a 1-argument function a->11*a^12
    • Take the previous function f1 and write ((.)((.(^13)).(*)))(f1); this is a 2-argument function a->b->11*a^12*b^13.
    • Finally, take the previous function f2 and write ((.)((.)((.(^14)).(*))))(f2). Thus a->b->c->11*a^12*b^13*c^14 is converted to point-free style as ((.)((.)((.(^14)).(*))))(((.)((.(^13)).(*)))(((.(^12)).(*))(11))).
    • In general, continue transforming f to 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 ^0 for 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!
  2. Create the operator $O_n$ that adds two functions of $n$ arguments:
    • $O_0$ is (+)
    • For $ngeq0$, $O_{n+1}$ can be constructed recursively as ((<*>).(.)( O_n ))
    • E.g. ((<*>).(.)(((<*>).(.)(+)))) adds two 2-argument functions.
  3. 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:

Try it online!

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!!


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.