zkFold / zkfold-base

ZkFold's Base library
https://zkfold.io
MIT License
17 stars 7 forks source link

Refactor usage of `Nat`s on type-level #257

Closed TurtlePU closed 1 month ago

TurtlePU commented 2 months ago

Currently, we have a lot of constraints on type-level naturals sprinkled all over the codebase. Some of them seem redundant from common sense, for example:

While we wait for Dependent Haskell which will come any minute, we can do the following:

In cases where the above doesn't work, we can use the trick described here: https://stackoverflow.com/questions/32839389/can-i-get-knownnat-n-to-imply-knownnat-n-3-etc. This allows us to build a library of helpers like:

withAdd :: (KnownNat m, KnownNat n) => (KnownNat (m + n) => r) -> r
withSub :: (KnownNat m, KnownNat n, n <= m) => (KnownNat (m - n) => r) -> r
withMul :: (KnownNat m, KnownNat n) => (KnownNat (m * n) => r) -> r
withDiv :: (KnownNat m, KnownNat n, 1 <= n) => (KnownNat (Div m n) => r) -> r
-- | same for log2, exp etc.

assoc :: ((m + n) + k ~ m + (n + k) => r) -> r
comm :: (m + n ~ n + m => r) -> r
trans :: (m <= n, n <= k) => (m <= k => r) -> r
-- | some more axioms for naturals

And use them to only specify constraints we really need for our dependent functions.