[Agda] Defining large numbers without recursion,
with short programs
effectfully
effectfully at gmail.com
Wed Mar 11 01:49:10 CET 2015
Neat trick. BTW, you can avoid these giant implicit arguments by
wrapping the N into a record (my emacs doesn't want to display 𝟘 𝟙
𝟚 𝟛 properly):
{-# OPTIONS --no-pattern-matching #-}
U = Set
data ℕ : U where
zero : ℕ
succ : ℕ → ℕ
record N X : U where
constructor #
field el : (X → X) → (X → X)
open N
b0 b1 b2 b3 : {X : U} → N X
b0 = # λ s z → z
b1 = # λ s z → s z
b2 = # λ s z → s(s z)
b3 = # λ s z → s(s(s z))
suc : {X : U} → N X → N X
suc n = # λ s z → s (el n s z)
add : {X : U} → N X → N X → N X
add m n = # λ s z → el m s (el n s z)
N-rec : {X : U} → (X → X) → X → (N X → X)
N-rec s z m = el m s z
mul : {X : U} → N X → N(N X) → N X
mul m = N-rec (add m) b0
exp : {X : U} → N(N X) → N(N X) → N X
exp n = N-rec (λ m → mul m n) b1
decode : N ℕ → ℕ
decode = N-rec succ zero
large : ℕ
large = decode
(exp b2
(exp b2
(exp b2
(exp b2
(exp b2
(exp b2
(exp b2
(exp b2
(exp {?} b2
b2)))))))))
Then Agda infers
N (N (N (N (N (N (N (N ℕ)))))))
in the hole above.
More information about the Agda
mailing list