Vesa Karvonen <vesa.karvonen@[EMAIL PROTECTED]
> wrote:
> David B. Benson <dbenson@[EMAIL PROTECTED]
> wrote:
> > Consider a continuous, piecewise linear, monotonically
> > strictly increasing (cplmsi) function on a real closed interval.
> > Clearly this determines a bijection.
> > The task is to determine a data structure for the cplmsi
> > function so that both functiion values and inverse function
> > values can be 'quickly' determined, using only functional
> > language constructs. No imperative features allowed.
> Assuming that the function is constructed once and evaluated many many
> times, I'd probably just use an ordered (immutable) vector of {x, y}
> coordinates and either binary search, interpolation search [1], or a
> functional adaptation of the "hunt" algorithm (intended for repeated
> evaluation) described in [2]. The same ordered vector works for both
the
> forward and inverse functions.
Below is a simple version in SML using just a basic binary search. It
should be given a sorted vector of at least 2 points. This mainly just
demonstrates that a single vector works for both the forward and inverse
functions.
-Vesa Karvonen
fun cplmsi points = let
val lo = 0
val hi = Vector.length points - 1
fun sub i = Vector.sub (points, i)
fun eval getX getY x = let
fun binary lo hi =
if hi - lo < 2
then lo
else case lo + Int.quot (hi - lo, 2) (* Avoid overflow! *)
of mid => if x < getX (sub mid)
then binary lo mid
else binary mid hi
val i = if getX (sub lo) <= x andalso x <= getX (sub hi)
then binary lo hi
else raise Domain (* x is NaN or not in the domain! *)
val p0 = sub i
val p1 = sub (i+1)
val dx = getX p1 - getX p0
val dy = getY p1 - getY p0
in
getY p0 + dy / dx * (x - getX p0)
end
in
if Vector.length points < 2 then raise Fail "less than 2 points" else
()
; ignore (Vector.foldl
(fn (n, p) =>
if #x n <= #x p orelse #y n <= #y p
then raise Fail "not strictly increasing"
else n)
{x = Real.negInf, y = Real.negInf}
points)
; {forward = eval #x #y, inverse = eval #y #x}
end
|
