# [racket] Function composition in Racket

On Oct 15, 2012, at 10:44 AM, Justin R. Slepak wrote:
>* Ah, I forgot about for/sum. This version is probably clearer:
*>*
*>* (struct polynomial (coeffs)
*>* #:transparent
*>* #:property prop:procedure
*>* (lambda (poly num)
*>* (for/sum ([x (length (polynomial-coeffs poly))]
*>* [c (polynomial-coeffs poly)])
*>* (* c (expt num x)))))
*
But probably slower, at least for exact numbers. If "expt" were implemented naively as "for i = 1 to num", the total number of multiplications would be quadratic in degree; if it were implemented by repeated squaring, the total number of multiplications would be O(n log(n)); with Horner's algorithm or your "values" approach, it's linear.
Horner's algorithm gives us
(lambda (poly x)
(for/fold ([sum 0])
([c (polynomial-coeffs poly)])
(+ c (* sum x))))
Stephen Bloch
sbloch at adelphi.edu