[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