~jojo/Carth

ref: 55fb4f948f1f3797078b584dc60b4f7dd68b37ed Carth/std/iter.carth -rw-r--r-- 3.2 KiB
55fb4f94JoJo Check `cast` in Infer instead of Gen 5 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
(import macros)
(import maybe)

;; TODO: Iter could include a lazy length field. By default, it's a lazy computation
;;       counting the number of nodes in the list, but if you know the length ahead of
;;       time, like when creating an iterator for an array, the iterator could be
;;       constructed with a constructor function that initializes the length to a non-lazy
;;       constant.
(data (Iter a)
  (Iter (Fun Unit (Maybe [a (Iter a)]))))

(define iter/nil
  (Iter (fun (_) None)))

(define (iter/once x)
  (iter/cons x iter/nil))

(define (iter/cons x xs)
  (Iter (fun (_) (Some [x xs]))))

(define (iter/chain xs ys)
  (Iter (fun (_) (maybe (next ys)
                        (fun ([x xs'])
                          (Some [x (iter/chain xs' ys)]))
                        (next xs)))))

(define (next (Iter it)) (it Unit))
(define next! (<o unwrap! next))

(define: (iter/nth n)
    (forall (a) (Fun Nat (Iter a) (Maybe a)))
  (apps <o (maybe/map car) next (skip n)))

(define: (xrange a b) (Fun Int Int (Iter Int))
  (take (- b a)       (range-from a)))
(define: (range  a b) (Fun Int Int (Iter Int))
  (take (inc (- b a)) (range-from a)))

(define (range-from a)
  (Iter (fun (_) (Some [a (range-from (inc a))]))))

(define (take n xs)
  (Iter (if (> n 0)
            (fun (_) (maybe/map (map-cadr (take (- n 1))) (next xs)))
          (fun (_) None))))

(define: (skip n xs)
    (forall (a) (Fun Nat (Iter a) (Iter a)))
  (if (= n (cast 0))
      xs
    (match (next xs)
      (case None iter/nil)
      (case (Some [_ xs]) (skip (dec n) xs)))))

(define (skip-while pred xs)
  (letrec ((skip-while' (fun (xs)
                          (match (next xs)
                            (case (Some [x xs'])
                                  (if (pred x)
                                      (skip-while' xs')
                                    (Some [x xs'])))
                            (case None None)))))
    (Iter (fun (_) (skip-while' xs)))))

(define (take-while pred xs)
  (Iter (fun (Unit) (maybe/bind (fun ([x xs'])
                                  (if (pred x)
                                      (Some [x (take-while pred xs')])
                                    None))
                                (next xs)))))

(define (for xs f) (foldl (const f) Unit xs))

(define (map f xs)
  (Iter (fun (_) (maybe/map (map-two f (map f)) (next xs)))))

(define (filter pred xs)
  (Iter (fun (_) (maybe/map (map-cadr (filter pred))
                            (next (skip-while (<o not pred) xs))))))

(define: (foldl f acc xs)
    (forall (acc x) (Fun (Fun acc x acc) acc (Iter x) acc))
  (define (foldl' [acc xs])
    (match (next xs)
      (case (Some [x xs'])
            (foldl' [(f acc x) xs']))
      (case None
            acc)))
  (foldl' [acc xs]))

(define (reverse xs)
  (define (rev xs a)
    (maybe a (fun ([x xs']) (rev xs' (iter/cons x a))) (next xs)))
  (rev xs iter/nil))

(define: (count xs)
    (forall (a) (Fun (Iter a) Nat))
  (foldl (<o const inc) (cast 0) xs))

(define enumerate (zip (range-from (: (cast 0) Nat))))

(define (zip xs ys)
  (Iter (fun (_) (maybe/map2 (fun ([x xs'] [y ys'])
                               [[x y] (zip xs' ys')])
                             (next xs) (next ys)))))