[HoTT] two's complement integers

[Michael Shulman <shulman@sandiego.edu>]

Has anyone considered the following HIT definition of the integers?

data ℤ : Type where
  zero : ℤ                              -- 0
  negOne : ℤ                            -- -1
  dbl : ℤ → ℤ                           -- n ↦ 2n
  sucDbl : ℤ → ℤ                        -- n ↦ 2n+1
  dblZero : dbl zero ≡ zero             -- 2·0 = 0
  sucDblNegOne : sucDbl negOne ≡ negOne -- 2·(-1)+1 = -1

The idea is that it's an arbitrary-precision version of little-endian
two's-complement, with sucDbl and dbl representing 1 and 0
respectively, and negOne and zero representing the highest-order sign
bit 1 and 0 respectively.  Thus for instance

sucDbl (dbl (sucDbl (sucDbl zero))) = 01101 = 13
dbl (sucDbl (dbl (dbl negOne))) = 10010 = -14

The two path-constructors enable arbitrary expansion of the precision, e.g.

01101 = 001101 = 0001101 = ...
10010 = 110010 = 1110010 = ...

This seems like a fairly nice definition: it should already be a set
without any truncation, it's binary rather than unary, and the
arithmetic operations can be defined in the usual digit-by-digit way
without splitting into cases by sign.  Mathematically speaking, it
represents integers by their images in the 2-adic integers, with zero
and negOne representing infinite tails of 0s and 1s respectively.  (An
arbitrary 2-adic integer, of course, is just a stream of bits.)

Best,
Mike

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQw4h46DtKATiwUvm%3DL%3DjEGng2XdYGAhKbi7fhis%2By_TPw%40mail.gmail.com.