[Agda] Raw natural numbers

Ulf Norell ulfn at chalmers.se
Thu Oct 21 11:48:49 CEST 2010


On Thu, Oct 21, 2010 at 12:22 AM, Alan Jeffrey <ajeffrey at bell-labs.com>wrote:

> Hi everyone,
>
> I did some simple bindings for raw natural numbers:
>
>  http://github.com/agda/agda-system-io/tree/master/src/Data/Natural
>
> The interesting thing is that we can almost optimize away many of the uses
> of unary numbers -- in particular to get constants such as #1000000 to be
> represented in native form rather than unary.
>
> The idea would be to add a rule to Haskell's rewrite engine:
>
> {-# RULES "int2nat2int" forall x .
>  MAlonzo.Data.Nat.mazNatToInteger (MAlonzo.Data.Nat.mazIntegerToNat x)
>    = x #-}
>
> This almost works.  The two things stopping it are:
>
> a) There isn't an FFI binding for Nat (grr) which means the compiler
> inserts some unsafeCoerce operations which then stop rewrites from firing.
>
> b) The definitions of mazNatToInteger and mazIntegerToNat define a local
> variable, which isn't in scope for rewriting.
>

I removed the unnecessary coercion of integer literals, so now you get

  Unsafe.Coerce.unsafeCoerce (mazIntegerToNat ((10) :: Integer))

instead of

  Unsafe.Coerce.unsafeCoerce (mazIntegerToNat (Unsafe.Coerce.unsafeCoerce
((10) :: Integer)))

when using natural number literals. I also changed the implementation of
mazNatToInteger/IntegerToNat to

mazNatToInteger
  = \ x -> case x of { C2 -> 0 :: Integer; C3 x -> 1 + (mazNatToInteger
(Unsafe.Coerce.unsafeCoerce x)) }
mazIntegerToNat
  = \ x -> if x <= (0 :: Integer) then C2 else C3
(Unsafe.Coerce.unsafeCoerce (mazIntegerToNat (x - 1)))

(where C2 and C3 are the constructor names for zero and suc). Hopefully this
will help a little.

/ Ulf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20101021/ad2f77ae/attachment.html


More information about the Agda mailing list