Z_n in Haskell

oleg@pobox.com oleg@pobox.com
Thu, 28 Mar 2002 20:28:28 -0800 (PST)


The Z_n problem doesn't seem to be different from the problem of 
arrays or bitvectors of a statically-checkable size. 
If you prefer a decimal specification of the modulus, you may find the
following articles relevant. 

Implementation of fixed-precision decimal types:

        Main> BV D1 0
        Bitvector of width 1 and value 0
        Main> BV (D1,D2) 123
        Bitvector of width 12 and value 123
        Main> BV (D5,D7,D9) 31415
        Bitvector of width 579 and value 31415

It appears that modulus in the Z_n problem plays the same role as the
bitvector width in the bitvector problem.
An attempt to perform an operation on bitvectors of different sizes results
in a compiler error:

        Main> (BV (D1,D0) 10) `b_and` (BV (D1,D1) 7)
        ERROR - Type error in application
        *** Expression     : b_and (BV (D1,D0) 10) (BV (D1,D1) 7)
        *** Term           : BV (D1,D0) 10
        *** Type           : BitVector (D1,D0)
        *** Does not match : BitVector (D1,D1)

http://groups.google.com/groups?selm=7eb8ac3e.0202201753.473a5cb2%40posting.google.com

Arbitrary precision decimal types, e.g.:

        Main> BV (D1 $ D2 $ D3 $ D4 $ D5 $ D6 $ D7 $ D8 $ D9 $ D0 $ D9 $ D8 $
D7 $ D6 $ D5 $ D4 $ D3 $ D2 $ D1 $ Dim) 1234567879
        Bitvector of width 1234567890987654321 and value 1234567879 

which are slightly more general and less convenient, are described in:

http://groups.google.com/groups?selm=7eb8ac3e.0202230221.62d98db8%40posting.google.com

Both implementations work in any Haskell-98 system. Multi-parameter
classes, existential types or other extensions are not needed.