In article
<<0ca99e02-7b97-46e5-a56e-346d6b070de1@[EMAIL PROTECTED]
>>,
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.
So your cplmsi function has a start position, an initial value, and a
sequence of linear functions over some intervals. We can take that
definition and just use it as a datatype, and a small amount of algebra
will tell you how to invert it.
As an aside, this code isn't quite as efficient as it could be, since
you could store the pieces as a binary tree of intervals and
interpolate the value. But it's good enough for Usenet. :)
type piece = {slope: float;
run: float}
type fn = {init: float; (* Initial y-value *)
start: float; (* Starting x-value *)
pieces: piece list}
let invert_piece p = {slope = 1.0 /. p.slope;
run = p.run *. p.slope}
let invert fn = {init = fn.start;
start = fn.init;
pieces = List.map invert_piece fn.pieces}
let eval fn x =
let rec loop pieces xleft total =
match pieces with
| [] -> failwith "Argument after end of range"
| p :: ps when xleft <= p.run -> total +. (p.slope *. xleft)
| p :: ps -> loop ps (xleft -. p.run) (total +. (p.slope *. p.run))
in
if x >= fn.start then
loop fn.pieces (x -. fn.start) fn.init
else
failwith "Argument before start range"
--
Neel R. Krishnaswami
neelk@[EMAIL PROTECTED]
|
