3
\$\begingroup\$

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

  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 \$n\geq0\$, \$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!!

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – DJMcMayhem Jul 11 at 17:05
5
+250
\$\begingroup\$

Haskell, 278+448/8-300=34

(foldr.pure.pure.((++).(foldr(('(':).(++".)")<$id).((++).("(sum.zipWith(*)"++).show.map head<*>(".flip(map.(product.).zipWith(^))"++).(++")").show.map tail)<*>tail.head)<*>(++" pure)").("("++).foldr(("(("++).(++".flip(:)).)")<$id)"id".drop 2.head))<*>show.sum.concat<*>tail.head

Saved 14 bytes by having a closer look at parens as suggested by @Damien, then saved 8 more using another hint from them.

Since input is "list of Integers in any format you want", I take list of lists with first elements the multiplicative constants of the summands, and the rest all the corresponding exponents in reverse order. So the example polynomial 5*a^5+2*a*b^3+8 is given by [[5,0,5],[2,3,1],[8,0,0]]. (Didn't try [(5,[0,5]),(2,[3,1]),(8,[0,0])] - would that be allowed?)

The result for this example polynomial is this:

(((sum.zipWith(*)[5,2,8].flip(map.(product.).zipWith(^))[[0,5],[3,1],[0,0]]).).)(((id.flip(:)).) pure)

See the results for the test cases or try your own polynomial at the TIO-Link:

Try it online!

Check the results for the test cases here:

Check it online! (testing code from OP with my results)

\$\endgroup\$
  • \$\begingroup\$ Yes, it's allowed. Great job! \$\endgroup\$ – Damien Jul 10 at 13:08
  • \$\begingroup\$ You can still save many bytes removing parenthesis \$\endgroup\$ – Damien Jul 10 at 13:21
  • \$\begingroup\$ @Damien Yes, quite a lot of them indeed, still not completely sure I got them all. \$\endgroup\$ – Christian Sievers Jul 10 at 14:37
  • \$\begingroup\$ I found the same, you can also replace <$> by . and pure$ by <$id \$\endgroup\$ – Damien Jul 10 at 15:12
  • \$\begingroup\$ Amazing, thanks! \$\endgroup\$ – Christian Sievers Jul 10 at 16:05
2
\$\begingroup\$

05AB1E, score: 167 (111 bytes + 448/8)

¬g©i˜Oëøć',ý’.Œ¬With(’DŠ’(¬€ÿ*)[ÿ].ÒÀ(‚é.(‚ª.)ÿ^))’sø',ý€…[ÿ]',ý…[ÿ]s…ÿÿ)®G"(ÿ.)"}„id®ÍF’((ÿ.ÒÀ(:)).)’}s“ÿ(ÿ©¬)

Since I don't know Haskell, I figured I'd just port the output of @ChristianSievers' Haskell answer, so make sure to upvote him!!
Input is taken in a similar matter as well (first being the multiplicative constant, and after that the exponents in reverse order). So for example: test case \$5a^4b^3c^2+a^2b^3c^4d^5\$ is given as input-list [[5,0,2,3,4],[1,5,4,3,2]].

Try it online or verify all test cases.
Verify the outputs with OP's validator.

Explanation:

¬                       # Get the first inner list in the (implicit) input-list
 g                      # Get the length of that list
  ©                     # And store it in variable ® (without popping)
i                       # If that length is 1:
 ˜O                     #  Take the flattened sum of the input-list
ë                       # Else:
 ø                      #  Zip/transpose the input-list; swapping rows/columns
  ć                     #  Extract head; pop and push head and remainder
   ',ý                 '#  Join this first list by ","
      ’.Œ¬With(’        #  Push dictionary String ".zipWith("
                D       #  Duplicate it
                 Š      #  Triple swap the items on the stack (a,b,c → c,a,b)
   ’(¬€ÿ*)[ÿ].ÒÀ(‚é.(‚ª.)ÿ^))’
                        #  Push dictionary string "(sumÿ*)[ÿ].flip(map.(product.)ÿ^))",
                        #  where the three ÿ are filled with the values on the stack
   s                    #  Swap to take the remainder again
    ø                   #  Zip/transpose it back
     ',ý               '#  Join each inner-most list by ","
        €…[ÿ]           #  Surround each inner string in []-blocks
             ',ý       '#  Join those by "," again
                …[ÿ]    #  And surround the entire thing by []-blocks again
    s                   #  Swap the two strings on the stack
     …ÿÿ)               #  And fill them in into the string "ÿÿ)"
 ®G      }              #  Now loop ®-1 amount of times:
   "(ÿ.)"               #   And fill in the top string on the stack into string "(ÿ.)"
 „id                    #  Then push string "id"
    ®ÍF              }  #  Loop ®-2 amount of times:
       ’((ÿ.ÒÀ(:)).)’   #   And fill the top string of the stack into dictionary 
                        #   string "((ÿ.flip(:)).)"
 s                      #  Swap the two strings of the stack again
  “ÿ(ÿ©¬)               #  And fill them into the dictionary string "ÿ( pure)"
                        # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to use the dictionary?) to understand why:

  • ’.Œ¬With(’ is ".zipWith("
  • ’(¬€ÿ*)[ÿ].ÒÀ(‚é.(‚ª.)ÿ^))’ is "(sumÿ*)[ÿ].flip(map.(product.)ÿ^))"
  • ’((ÿ.ÒÀ(:)).)’ is "((ÿ.flip(:)).)"
  • “ÿ(ÿ©¬) is "ÿ( pure)"

Unfortunately ÿ doesn't work for inner items in a list and requires an explicit , otherwise ',ý€…[ÿ]',ý…[ÿ] could have been 2F',ý…[ÿ]} instead.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.