www

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs | README

find.mlish (2426B)

      1 #lang s-exp "../../mlish.rkt"
      2 (require "../rackunit-typechecking.rkt")
      3 
      4 (define-type (List X)
      5   Nil
      6   (Cons X (List X)))
      7 
      8 (define-type (Option X)
      9   None
     10   (Some X))
     11 
     12 (define (find [lst : (List X)] [pred : (→ X Bool)] → (Option X))
     13   (match lst with
     14    [Nil -> None]
     15    [Cons fst rst ->
     16          (cond [(pred fst) (Some fst)]
     17                [else (find rst pred)])]))
     18 
     19 (check-type
     20  (find (Cons 1 (Cons 2 (Cons 3 Nil))) (λ ([x : Int]) (<= 2 x)))
     21  : (Option Int)
     22  -> (Some 2))
     23 
     24 (check-type
     25  (find (Cons 1 (Cons 0 (Cons -1 Nil))) (λ ([x : Int]) (<= 2 x)))
     26  : (Option Int)
     27  -> None)
     28 
     29 ;; args inferred in order, L-to-R, currently no backtracking
     30 (check-type
     31  (find Nil (λ ([x : Int]) (<= 2 x)))
     32  : (Option Int)
     33  -> None)
     34 
     35 ;; reversing arg order leads to successful inference
     36 (define (find2 [pred : (→ X Bool)] [lst : (List X)] → (Option X))
     37   (match lst with
     38    [Nil -> None]
     39    [Cons fst rst ->
     40          (cond [(pred fst) (Some fst)]
     41                [else (find2 pred rst)])]))
     42 
     43 (check-type
     44  (find2 (λ ([x : Int]) (<= 2 x)) Nil)
     45  : (Option Int)
     46  -> None)
     47 
     48 (define (find-min/max [lst : (List X)] [<? : (→ Y Y Bool)] [extract-key : (→ X Y)]
     49                       → (Option (× X X)))
     50   (match lst with
     51    [Nil -> None]
     52    [Cons x1 rst ->
     53          (let ([y1 (extract-key x1)])
     54            (Some (find-min/max-accum rst <? extract-key x1 y1 x1 y1)))]))
     55 
     56 (define (find-min/max-accum [lst : (List X)] [<? : (→ Y Y Bool)] [extract-key : (→ X Y)]
     57                             [x-min : X] [y-min : Y] [x-max : X] [y-max : Y]
     58                             → (× X X))
     59   (match lst with
     60    [Nil -> (tup x-min x-max)]
     61    [Cons x2 rst ->
     62          (let ([y2 (extract-key x2)])
     63            (cond [(<? y2 y-min)
     64                   (find-min/max-accum rst <? extract-key x2 y2 x-max y-max)]
     65                  [(<? y-max y2)
     66                   (find-min/max-accum rst <? extract-key x-min y-min x2 y2)]
     67                  [else
     68                   (find-min/max-accum rst <? extract-key x-min y-min x-max y-max)]))]))
     69 
     70 (check-type
     71  (find-min/max (Nil {Int})
     72                (λ ([x : Int] [y : Int])
     73                  (< x y))
     74                (λ ([x : Int])
     75                  x))
     76  : (Option (× Int Int))
     77  -> None)
     78 
     79 (check-type
     80  (find-min/max (Cons 1 (Cons 2 (Cons 3 Nil)))
     81                (λ ([x : Int] [y : Int])
     82                  (< x y))
     83                (λ ([x : Int])
     84                  x))
     85  : (Option (× Int Int))
     86  -> (Some (tup 1 3)))
     87