polynomial_interpolation.clj

;; Polynomial interpolation in Clojure, written as a fold.
;;
;; This allows you to generate an estimate of the value of some polynomial at x,
;; where you have a sequence of points that the polynomial has to pass through.
;;
;; See [this namespace](https://github.com/sicmutils/sicmutils/blob/main/src/sicmutils/polynomial/interpolate.cljc#L20)
;; for a much longer build-up to these simple functions!

(defn prepare [[x fx]]
  [x x fx fx])

(defn- combine [x]
  (fn [[xl _ _ dl] [_ xr cr _]]
    (let [diff   (- cr dl)
          den    (- xl xr)
          factor (/ diff den)
          c      (* factor (- xl x))
          d      (* factor (- xr x))]
      [xl xr c d])))

(defn present [row]
  (transduce (map (fn [[_ _ c _]] c))
             +
             row))

(defn modified-neville-fold [x]
  (let [f (combine x)]
    (fn
      ([] [])
      ([row] (present row))
      ([prev-row point]
       (reductions f (prepare point) prev-row)))))

(let [fold   (modified-neville-fold 1.5)
      points [[1 1] [2 4] [3 9]]]
      
   ;; compatible with transducers!
  (println "Estimate at 1.5: "
           (transduce identity fold points))

  ;; I wish we had "transductions"... but "reductions" will do!
  (println "cumulative estimates, as points are added in:"
           (->> (reductions fold (fold) points)
                (rest)
                (map fold))))