[Agda] Nat -iso- Bin

Arseniy Alekseyev arseniy.alekseyev at gmail.com
Tue Oct 29 21:16:27 CET 2013


FWIW, there is my proof of bijection together with proofs of
equivalence for addition and multiplication:
https://github.com/Rotsor/BinDivMod
See modules Data.Bin.{Bijection, Addition, Multiplication}
Too bloated, I guess, but that's what I've got.

Cheers!

On 29 October 2013 20:00, Sergei Meshveliani <mechvel at botik.ru> wrote:
> On Tue, 2013-10-29 at 23:21 +0400, Sergei Meshveliani wrote:
>> Correction:  ``{m : ℕ} → ''
>> is not needed here.
>>
>> Also there is a question about availability of  fromℕ ∘ toℕ ≗ id,
>> fromDigits ∘ toDs ≗ id.
>>
>>
>> On Tue, 2013-10-29 at 22:51 +0400, Sergei Meshveliani wrote:
>> > Please, has  lib-0.7  something for the isomorphism  ℕ <-> Bin ?
>> >
>> > For example, I need
>> >
>> >   toDigits-suc-eq : {m : ℕ} →
>> >                     let toDs : ℕ → Bin⁺
>> >                         toDs = proj₁ ∘ toDigits 2
>> >                     in
>> >                     toDs ∘ suc ≗ (addCarryToBitList 1b ∘ toDs)
>> >
>> > Probably,      fromℕ ∘ suc ≗ Bin.suc ∘ fromℕ
>> > will also do.
>> >
>> > I think of proving  toDigits-suc-eq,  but this needs looking into a
>> > non-trivial definition of  toDigits.
>> >
>
> I hope now that
>
>   bs → fromDigits (addCarryToBitList 1b bs) \equiv (suc (fromDigits bs))
>
> is not difficult to prove -- because  fromDigits  is simpler than
> toDigits.
> I hope that then, the proof part  pr  in  toDigits m  will help with the
> proof for  toDigits-suc-eq.
>
> On the other hand, something needs to be in Standard library that easily
> gives the  suc (or _+_) isomorphism for  Nat <--> Bin, Bin⁺.
> Am I missing something?
>
> Regards,
>
> ------
> Sergei
>
>
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda


More information about the Agda mailing list