[Question]
  [
Given two polynomials `f,g` of arbitrary degree over the integers, your program/function should evaluate the first polynomial in the second polynomial. `f(g(x))` (a.k.a. the *composition* `(fog)(x)` of the two polynomials)
### Details
Builtins are allowed. You can assume any reasonable formatting as input/output, but the input and output format should match. E.g. formatting as a string
```
x^2+3x+5
```
or as as list of coefficients:
```
[1,3,5] or alternatively [5,3,1]
```
Furthermore the input polynomials can be assumed to be fully expanded, and the outputs are also expected to be fully expanded.
### Examples
```
A(x) = x^2 + 3x + 5, B(y) = y+1
A(B(y)) = (y+1)^2 + 3(y+1) + 5 = y^2 + 5y + 9
A(x) = x^6 + x^2 + 1, B(y) = y^2 - y
A(B(y))= y^12 - 6y^11 + 15y^10 - 20y^9 + 15y^8 - 6y^7 + y^6 + y^4 - 2 y^3 + y^2 + 1
A(x) = 24x^3 - 144x^2 + 288x - 192, B(y) = y + 2
A(B(y)) = 24y^3
A(x) = 3x^4 - 36x^3 + 138x^2 - 180x + 27, B(y) = 2y + 3
A(B(y)) = 48y^4 - 96y^2
```
  
[Answer]
# Haskell, ~~86~~ 72 bytes
```
u!c=foldr1((.u).zipWith(+).(++[0,0..])).map c
o g=(0:)!((<$>g).(*))!pure
```
Defines a function `o` such that `o g f` computes the composition f ∘ g. Polynomials are represented by a nonempty list of coefficients starting at the constant term.
## Demo
```
*Main> o [1,1] [5,3,1]
[9,5,1]
*Main> o [0,-1,1] [1,0,1,0,0,0,1]
[1,0,1,-2,1,0,1,-6,15,-20,15,-6,1]
*Main> o [2,1] [-192,288,-144,24]
[0,0,0,24]
*Main> o [3,2] [27,-180,138,-36,3]
[0,0,-96,0,48]
```
## How it works
No polynomial-related builtins or libraries. Observe the similar recurrences
f(x) = a + f₁(x)x ⇒ f(x)g(x) = a g(x) + f₁(x)g(x)x,  
f(x) = a + f₁(x)x ⇒ f(g(x)) = a + f₁(g(x))g(x),
for polynomial multiplication and composition, respectively. They both take the form
f(x) = a + f₁(x)x ⇒ W(f)(x) = C(a)(x) + U(W(f₁))(x).
The operator `!` solves a recurrence of this form for W given U and C, using `zipWith(+).(++[0,0..])` for polynomial addition (assuming the second argument is longer—for our purposes, it always will be). Then,
`(0:)` multiplies a polynomial argument by x (by prepending a zero coefficient);  
`(<$>g).(*)` multiplies a scalar argument by the polynomial `g`;  
`(0:)!((<$>g).(*))` multiplies a polynomial argument by the polynomial `g`;  
`pure` lifts a scalar argument to a constant polynomial (singleton list);  
`(0:)!((<$>g).(*))!pure` composes a polynomial argument with the polynomial `g`.
[Answer]
# Mathematica, 17 bytes
```
Expand[#/.x->#2]&
```
Example usage:
```
In[17]:= Expand[#/.x->#2]& [27 - 180x + 138x^2 - 36x^3 + 3x^4, 3 + 2x]
              2       4
Out[17]= -96 x  + 48 x
```
[Answer]
# TI-Basic 68k, 12 bytes
```
a|x=b→f(a,b)
```
The usage is straightforward, e.g. for the first example:
```
f(x^2+3x+5,y+1)
```
Which returns
```
y^2+5y+9
```
[Answer]
# Python 2, 138 ~~156 162~~ bytes
The inputs are expected to be integer lists with smallest powers first.
```
def c(a,b):
 g=lambda p,q:q>[]and q[0]+p*g(p,q[1:]);B=99**len(`a+b`);s=g(g(B,b),a);o=[]
 while s:o+=(s+B/2)%B-B/2,;s=(s-o[-1])/B
 return o
```
Ungolfed:
```
def c(a,b):
 B=sum(map(abs,a+b))**len(a+b)**2
 w=sum(B**i*x for i,x in enumerate(b))
 s=sum(w**i*x for i,x in enumerate(a))
 o=[]
 while s:o+=min(s%B,s%B-B,key=abs),; s=(s-o[-1])/B
 return o
```
In this computation, the polynomial coefficients are seen as digits (which may be negative) of a number in a very large base. After polynomials are in this format, multiplication or addition is a single integer operation. As long as the base is sufficiently large, there won't be any carries that spill over into neighboring digits.
-18 from improving bound on `B` as suggested by @xnor.
[Answer]
# Python + SymPy, ~~59~~ 35 bytes
```
from sympy import*
var('x')
compose
```
*Thanks to @asmeurer for golfing off 24 bytes!*
### Test run
```
>>> from sympy import*
>>> var('x')
x
>>> f = compose
>>> f(x**2 + 3*x + 5, x + 1)
x**2 + 5*x + 9
```
[Answer]
## Sage, 24 bytes
```
lambda A,B:A(B).expand()
```
As of Sage 6.9 (the version that runs on <http://sagecell.sagemath.org>), function calls without explicit argument assignment (`f(2) rather than f(x=2)`) causes an annoying and unhelpful message to be printed to STDERR. Because STDERR can be ignored by default in code golf, this is still valid.
This is very similar to [Dennis's SymPy answer](https://codegolf.stackexchange.com/a/78335/45941) because Sage is a) built on Python, and b) uses [Maxima](http://maxima.sourceforge.net/), a computer algebra system very similar to SymPy in many ways. However, Sage is much more powerful than Python with SymPy, and thus is a different enough language that it merits its own answer.
[Verify all test cases online](http://sagecell.sagemath.org/?z=eJxNjk0KgzAQhfeCdxjoIolNbU2stQUXehDBYgTBn5Bom96-o9m4mXm8-ebN9KOezQL2Z8MAS2yXVhkDBcxaTZRcW_W5TuswEE6-hMEJ7Kq1UdaCJ8OgK4ZmfLcNlLx6lbRisXK6mVrKwiAMtOmnBTrqagFnkJHDeuewtYQdxxk6Hkr4Li7gDoBII1dLNJN0Uxsn8hzj0HkKHygOPF6qUxzKbN_DVJlHPjbJb_sb4sFB7EqyP3mzRek=&lang=sage)
[Answer]
# [PARI/GP](http://pari.math.u-bordeaux.fr/), 19 bytes
```
(a,b)->subst(a,x,b)
```
which lets you do
```
%(x^2+1,x^2+x-1)
```
to get
> 
> %2 = x^4 + 2\*x^3 - x^2 - 2\*x + 2
> 
> 
> 
[Answer]
# MATLAB with Symbolic Toolbox, 28 bytes
```
@(f,g)collect(subs(f,'x',g))
```
This is an anonymous function. To call it assign it to a variable or use `ans`. Inputs are strings with the format (spaces are optional)
```
x^2 + 3*x + 5
```
Example run:
```
>> @(f,g)collect(subs(f,'x',g))
ans = 
    @(f,g)collect(subs(f,'x',g))
>> ans('3*x^4 - 36*x^3 + 138*x^2 - 180*x + 27','2*x + 3')
ans =
48*x^4 - 96*x^2
```
[Answer]
# Python 2, 239 232 223 bytes
```
r=range
e=reduce
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
m=lambda p,q:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in r(k+1))for k in r(len(p+q)-1)]
o=lambda f,g:e(a,[e(m,[[c]]+[g]*k)for k,c in enumerate(f)])
```
A 'proper' implementation that does not abuse bases. Least significant coefficient first.
`a` is polynomial addition, `m` is polynomial multiplication, and `o` is composition.
[Answer]
## JavaScript (ES6), ~~150~~ 103 bytes
```
(f,g)=>f.map(n=>r=p.map((m,i)=>(g.map((n,j)=>p[j+=i]=m*n+(p[j]||0)),m*n+(r[i]||0)),p=[]),r=[],p=[1])&&r
```
Accepts and returns polynomials as an array a = [a0, a1, a2, ...] that represents a0 + a1\*x + a2\*x2 ...
Edit: Saved 47 bytes by switching from recursive to iterative polynomial multiplication, which then allowed me to merge two `map` calls.
Explanation: *r* is the result, which starts at zero, represented by an empty array, and *p* is *g**h*, which starts at one. *p* is multiplied by each *f**h* in turn, and the result accumulated in *r*. *p* is also multiplied by *g* at the same time.
```
(f,g)=>f.map(n=>            Loop through each term of f (n = f[h])
 r=p.map((m,i)=>(           Loop through each term of p (m = p[i])
  g.map((n,j)=>             Loop though each term of g (n = g[j])
   p[j+=i]=m*n+(p[j]||0)),  Accumulate p*g in p
  m*n+(r[i]||0)),           Meanwhile add p[i]*f[h] to r[i]
  p=[]),                    Reset p to 0 each loop to calculate p*g
 r=[],                      Initialise r to 0
 p=[1]                      Initialise p to 1
)&&r                        Return the result
```
[Answer]
# Pyth, ~~51~~ 34 bytes
```
AQsM.t*LVG.usM.t.e+*]0k*LbHN0tG]1Z
```
[Test suite](http://pyth.herokuapp.com/?code=AQsM.t%2aLVG.usM.t.e%2B%2a%5D0k%2aLbHN0tG%5D1Z&test_suite=1&test_suite_input=%5B5%2C3%2C1%5D%2C%5B1%2C1%5D%0A%5B1%2C0%2C1%2C0%2C0%2C0%2C1%5D%2C%5B0%2C-1%2C1%5D%0A%5B-192%2C288%2C-144%2C24%5D%2C%5B2%2C1%5D%0A%5B27%2C-180%2C138%2C-36%2C3%5D%2C%5B3%2C2%5D&debug=0).
[Answer]
# [Ruby 2.4](https://www.ruby-lang.org) + [polynomial](http://adrianomitre.github.io/Polynomial/website/index.html), 41+12 = 53 bytes
Uses flag `-rpolynomial`. Input is two `Polynomial` objects.
If someone outgolfs me in vanilla Ruby (no polynomial external library), I will be very impressed.
```
->a,b{i=-1;a.coefs.map{|c|c*b**i+=1}.sum}
```
[Answer]
# [Maxima](http://maxima.sourceforge.net/), 34 bytes
[Try it online!](https://tio.run/##dYzLCsIwEEV/ZZYzcQSbiBb7KT7KhLoIJGmwFcavj5GuXd3D4XCTaEhSn1okT2OZ4yfPKUgcoyQ/CVxudSO8Cvs7byEub7@s6FlZiKgO5RXyin9f0J5hD11/MAo76Fxv9GGbcacGrinX9sjwQ2uUaKhf)
```
lambda([a,b],expand(subst(b,x,a)))
```
]