Recursive list

Recursive list

Way, way back we looked at a function to estimate the value of the sin function utilizing its representation as a Taylor polynomial about x = 0. When one looks closely at that Taylor polynomial, one can observe a pattern in the coefficients involving the infinite sequence 0, 1, 0, -1, 0, 1, 0, -1, .... My buddy Marcelo in his formulation of that Taylor polynomial wrote this function that for a given n produces the first n values of this sequence as a list:

let rec sin_coeff n =
  match n with
  | 0 -> []
  | 1 -> [0.]
  | 2 -> [0.; 1.]
  | 3 -> [0.; 1.; 0. ]
  | _  -> 0. :: 1. :: 0. :: -1. :: sin_coeff (n-4)

He mused to me on the day that "surely there is a more elegant way to produce this list?". Oh, by golly Marcelo there certainly is!

let rec sin_coeff = 0 :: 1 :: 0 :: -1 :: sin_coeff

This little construction builds the list value sin_coeff recursively (that is, in terms of itself). Now, of course it's not impossible to define structures like this in C or C++ but good luck matching the brevity and elegance afforded to us in OCaml for this sort of thing! We still need a little function of course that can pull off this endless list a list containing just the first n elements. The ubiquitous take function will do for this purpose and I show it here just for completeness.

let rec list_take k l =
  if k <= 0 then []
  else
    match l with
    | [] -> []
    | (x :: xs)  -> x :: (list_take (k-1) xs)

Taylor Polynomials

I find this little calculation a pleasing, succinct reminder of some the (many) things I like about functional programming. It concerns a formulation of the trigonometric sin function as the first few terms of its Taylor polynomial about x = 0:
The "definition" above can be minimally and naturally "coded up" from "first principles" (I mean, using nothing more than elementary arithmetic operations) as simply as this!:

 let rec power  = 
  fun u -> fun i ->
    if i < 0 then 1.0 / (power u (-i))
    else if i = 0 then 1.0 else u * (power u (i-1))

let rec fac = fun n -> if n = 0 then 1 else n * fac (n-1)
let pow = fun i -> fun u -> power u (2 * i + 1)
let coef = fun i -> (power (-1) i)/(fac (2 * i + 1))

let rec taylor = 
  fun i -> fun n -> fun u ->
    if i = n then (coef i) * (pow i u)
    else ((coef i) * (pow i u)) + (taylor (i + 1) n u)
  
let x = 0.78539816339744830961566084581988 (*pi/4*) in 

taylor 0 3 x 

We expect 0.70710678118654752440084436210485. I can get 0.70710646957517809, with the above which is correct to 6 decimal places. I came across this little example in Kluge's "Abstract Computing Machines" by the way, a title I'm happy to recommend to those who share my interest in symbolic computation!