Instances For
@[reducible]
Original semantics from the paper. It uses recursion and it's inefficient.
Use loop instead (see theorem about equivalence).
Equations
- Synth.loop' f (Int.ofNat 0) b = b
- Synth.loop' f (Int.ofNat n.succ) b = f (Synth.loop' f (↑n) b) (↑n + 1)
- Synth.loop' f (Int.negSucc a_2) b = b
Instances For
@[reducible]
Efficient implementation of loop.
See proof of equivalence to the original in GenSeq.Proofs.
Equations
- Synth.loop f (Int.ofNat m) b = List.foldl f b (List.map (fun (x : Nat) => ↑x) (List.range' 1 m))
- Synth.loop f (Int.negSucc a) b = b
Instances For
@[reducible]
Equations
- Synth.loop2 f g (Int.ofNat 0) b c = b
- Synth.loop2 f g (Int.ofNat n.succ) b c = Synth.loop2 f g (↑n) (f b c) (g b c)
- Synth.loop2 f g (Int.negSucc a_2) b c = b
Instances For
@[reducible]
Equations
- Synth.loop2' f g (Int.ofNat 0) b = b
- Synth.loop2' f g (Int.ofNat n.succ) b = Synth.loop2' f g ↑n (f b, g b)
- Synth.loop2' f g (Int.negSucc a_2) b = b
Instances For
@[reducible]
Equations
- Synth.comprN f (Int.negSucc a_2) = 0
- Synth.comprN f (Int.ofNat 0) = (List.find? (fun (x : Int) => decide (f x ≤ 0)) (List.map (fun (x : Nat) => ↑x) (List.range Synth.N))).getD ↑Synth.N
- Synth.comprN f (Int.ofNat n.succ) = ↑((List.find? (fun (i : Nat) => decide (Synth.comprN f ↑n < ↑i ∧ f ↑i ≤ 0)) (List.range Synth.N)).getD Synth.N)
Instances For
@[reducible]
def
Synth.comprP
(f : Int → Int)
(b : Int → Nat)
(hb : ∀ (n : Nat), n < b ↑n ∧ f ↑(b ↑n) ≤ 0)
(a : Int)
:
Equations
- One or more equations did not get rendered due to their size.
- Synth.comprP f b hb (Int.negSucc a_2) = 0
- Synth.comprP f b hb (Int.ofNat 0) = (List.find? (fun (x : Int) => decide (f x ≤ 0)) (List.map (fun (x : Nat) => ↑x) (List.range (b 0)))).getD ↑(b 0)