commit 2e259163aad22fa953eb95bf3dab4456477be614 parent f4979c9e5892e19c74d5a55d2a24f3e1114503a6 Author: AlexKnauth <alexander@knauth.org> Date: Thu, 10 Mar 2016 16:35:57 -0500 add find-min/max Diffstat:
| M | tapl/tests/mlish/find.mlish | | | 40 | ++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 40 insertions(+), 0 deletions(-)
diff --git a/tapl/tests/mlish/find.mlish b/tapl/tests/mlish/find.mlish @@ -31,3 +31,43 @@ : (Option Int) -> (None {Int})) +(define (find-min/max [lst : (List X)] [<? : (→ Y Y Bool)] [extract-key : (→ X Y)] + → (Option (× X X))) + (match lst with + [Nil -> None] + [Cons x1 rst -> + (let ([y1 (extract-key x1)]) + (Some (find-min/max-accum rst <? extract-key x1 y1 x1 y1)))])) + +(define (find-min/max-accum [lst : (List X)] [<? : (→ Y Y Bool)] [extract-key : (→ X Y)] + [x-min : X] [y-min : Y] [x-max : X] [y-max : Y] + → (× X X)) + (match lst with + [Nil -> (tup x-min x-max)] + [Cons x2 rst -> + (let ([y2 (extract-key x2)]) + (cond [(<? y2 y-min) + (find-min/max-accum rst <? extract-key x2 y2 x-max y-max)] + [(<? y-max y2) + (find-min/max-accum rst <? extract-key x-min y-min x2 y2)] + [else + (find-min/max-accum rst <? extract-key x-min y-min x-max y-max)]))])) + +(check-type + (find-min/max (Nil {Int}) + (λ ([x : Int] [y : Int]) + (< x y)) + (λ ([x : Int]) + x)) + : (Option (× Int Int)) + -> (None {Int})) + +(check-type + (find-min/max (Cons 1 (Cons 2 (Cons 3 Nil))) + (λ ([x : Int] [y : Int]) + (< x y)) + (λ ([x : Int]) + x)) + : (Option (× Int Int)) + -> (Some (tup 1 3))) +