2
$\begingroup$

For example, could the polynomial:

$f(x) = x^2 + 3x$

Be written without $x$, using only the exponential, addition and multiplication functions, and high-order functions such as composition and partial application?

  • 0
    @RahulNarain as I'm reading: that's some weird syntax but seems to be what I'm looking for.2012-11-18
  • 0
    Sorry, my comment was actually not accurate, so I've deleted it.2012-11-18
  • 0
    What you just want is "Take a number, add $3$ to it and multply it by itself?" So you want "mult(sum(x,3),x)"? I mean, how would you "avoid" $x$ if you're considering indeterminate values?2012-11-18
  • 0
    This may be of interest: http://www.haskell.org/haskellwiki/Pointfree2012-11-18

2 Answers 2

1

If you allow taking the diagonal product of functions (I'm not sure what it is called, or if it even has a standard name, but I mean for $f,g$ taking $f\times g:x\mapsto (f(x),g(x))$), then you could write $$f=(+)\circ \left((\cdot)\circ(\textrm{id}\times \textrm{id})\times 3\textrm{id}\right)$$ With $\textrm{id}$ the identity function and $3\textrm{id}$ the multiplication by three. If you would rather use constant functions instead of scalar multiplication function, you can replace the latter with $(\cdot)\circ (3\times \textrm{id})$.

Similarly you could express any polynomial. Without this, I doubt it can be done.

0

Since $p(x) = x$ is just the identity function $\iota$, one can rewrite any polynomial function $q$:

$\displaystyle\qquad q(x) = a_nx^n + \dotsb + a_0 = \bigl(a_n \iota^n + \dotsb + a_0\bigr)(x)$.

In particular for your function: $f = \iota^2 + 3 \iota$.

  • 0
    Eh, thanks, but that's not what I mean. I want a way to express that equation using only the functions sum(x,y), exp(x,y), mul(x,y) and compose(x,y), partial(x,y) and other high order functions. For example, 2*2+2 could be rewritten as sum(partial(mul,2)(2),2).2012-11-18
  • 0
    Not that this doesn't answer the question, but it's not what I meant.2012-11-18