Integers from scratch in Haskell

Question

Inspired by this article about natural numbers from first principles in swift I implemented integers from scratch in Haskell.

Besides obviously being extremely inefficient, is this code idiomatic Haskell?

import Data.List
import GHC.Real
data Z = Pred Z | Zero | Succ Z
toNat = toEnum :: Int -> Z
fromNat = fromEnum :: Z -> Int 
toInteger' :: Z -> Integer
toInteger' Zero = 0
toInteger' (Succ n) = toInteger' n + 1
toInteger' (Pred n) = toInteger' n - 1
instance Show Z where
 show = ((++) "Nat: ") . show . toInteger'
data SimpleNat = MinusOne | One deriving (Eq, Ord, Show)
toList :: Z -> [SimpleNat]
toList Zero = []
toList (Succ n) = One : toList n
toList (Pred n) = MinusOne : toList n
fromList :: [SimpleNat] -> Z
fromList [] = Zero
fromList (One:xs) = Succ (fromList xs)
fromList (MinusOne:xs) = Pred (fromList xs)
normaliseList :: [SimpleNat] -> [SimpleNat]
normaliseList xs = normaliseSorted $ sort xs
 where normaliseSorted xs = map fst filtered
 filtered = filter (uncurry (==)) $ zip xs (reverse xs)
normalise :: Z -> Z
normalise = fromList . normaliseList . toList
instance Enum Z where
 succ (Pred n) = n
 succ n = Succ n
 pred (Succ n) = n
 pred n = Pred n
 toEnum n | n < 0 = Pred $ toEnum (n+1)
 | n > 0 = Succ $ toEnum (n-1)
 | otherwise = Zero
 fromEnum Zero = 0
 fromEnum (Succ n) = fromEnum n + 1
 fromEnum (Pred n) = fromEnum n - 1
instance Num Z where
 Zero + n = n
 n + Zero = n
 (Succ n) + m = Succ (n + m)
 (Pred n) + m = Pred (n + m)
 abs n = abs' $ normalise n
 where abs' (Pred n) = Succ (abs' n)
 abs' n = n
 signum n = signum' $ normalise n
 where signum' Zero = Zero
 signum' (Succ n) = Succ Zero
 signum' (Pred n) = Pred Zero
 negate n = negate' $ normalise n
 where negate' Zero = Zero
 negate' (Succ n) = Pred (negate' n)
 negate' (Pred n) = Succ (negate' n)
 fromInteger n | n < 0 = Pred $ fromInteger (n+1)
 | n > 0 = Succ $ fromInteger (n-1)
 | otherwise = Zero
 Zero * _ = Zero
 _ * Zero = Zero
 (Succ n) * m = n*m + m
 (Pred n) * m = n*m - m
instance Eq Z where
 n == m = normalise n `eq` normalise m
 where Zero `eq` Zero = True
 (Succ n) `eq` (Succ m) = n `eq` m
 (Pred n) `eq` (Pred m) = n `eq` m
 _ `eq` _ = False
instance Ord Z where
 a `compare` b = normalise a `comp` normalise b
 where Zero `comp` Zero = EQ
 Zero `comp` (Succ _) = LT
 Zero `comp` (Pred _) = GT
 (Succ _) `comp` Zero = GT
 (Succ _) `comp` (Pred _) = GT
 (Pred _) `comp` Zero = LT
 (Pred _) `comp` (Succ _) = LT
 (Succ n) `comp` (Succ m) = n `comp` m
 (Pred n) `comp` (Pred m) = n `comp` m
instance Real Z where
 toRational n = toInteger' n % 1
instance Integral Z where
 toInteger = toInteger'
 quotRem _ Zero = error "divide by zero"
 quotRem Zero _ = (Zero, Zero)
 quotRem n d | n == d = (Succ Zero,0)
 | n < d = (Zero, n)
 | otherwise = (Succ (fst foo), snd foo)
 where foo = (n-d) `quotRem` d

Answer 1

This is some good looking code, there are just a few things that throw me. The first is that you're defining the integers but occasionally referring to them as "Nat"s. The natural numbers are non-negative integers, don't confuse the two.

toNat = toEnum :: Int -> Z
fromNat = fromEnum :: Z -> Int

This is a strange construction, give the type signature before the definition of the function and GHC will figure out which version of toEnum and fromEnum to use. Anything else is unusual and unnecessary.

Your Show instance should really just punt to the instance for Integers. Again, naturals numbers aren't integers so your "Nat: " tag is incorrect, it doesn't really add anything, and it makes writing a Read instance more difficult. Also there's no need to section infix functions by writing them prefix style. Thus:

instance Show Z where
 show = show . toInteger
instance Read Z where
 read = fromInteger . read

Your normalization function is more complex than it needs to be, but consider what having to normalize says about the representation you picked. Here's one version that doesn't change anything about your data types.

normalise = fromList . uncurry tailOfLonger . partition isOne . toList
 where 
 isOne :: SimpleNat -> Bool
 isOne One = True
 isOne _ = False
 tailOfLonger :: [a] -> [a] -> [a]
 tailOfLonger [] ys = ys
 tailOfLonger xs [] = xs
 tailOfLonger (_:xs) (_:ys) = tailOfLonger xs ys

You have some unnecessary pattern match cases, such as n + Zero = n in the Num instance declaration. There's nothing wrong operationally with that case of course, but it's superfluous and the beauty of the inductive construction of the integers encourages me at least to be ruthless with flensing redundant code.

---

Here is an alternate construction that could obviate the need for all of the expensive normalization your version incurs. Writing the Num instance is pretty fun.

data Nat = Zero | Succ Nat
data Z = Negative Nat | NonNegative Nat

• David K: I think the alternate construction at the end is parallel to the way a mathematician might define integers. That is, one generates the non-negative integers (natural numbers) using Succ, then one assumes additive inverses. Pred is not required when generating numbers in this way.
• Sebastian: I started with implementing Natural numbers and later extended to Integers, I forgot to rename the functions. I'll try to implement the alternate construction, I thought of that before, but wasn't sure if it would actually complicate things.
• bisserlis: You have to take some care around zeros, but I was able to write a fairly elegant version. Fair warning, spoilers. ;-)

Answer 2

Why have toNat and fromNat in the first place?

Your SimpleNat is really the sign of an integral number (without zero). So, I think, Sign or even Unit would be a more appropriate identifier.

There is no need to define toInteger' up front and then later define the toInteger of the Integral class as toInteger = toInteger'. You can put the definition right into the class instance for Integral and not define toInteger' at all. The order of definitions in a Haskell module is completely irrelevant (to the compiler) — with one exception involving Template Haskell. I'm saying this mostly because you asked whether the code is idiomatic, and in my experience, it takes a bit of getting used to that declarations including data types and classes can be in any order and mutually dependent.

Also, Haskell programmers tend to line up their = in multiple one line equations belonging to the same function — like @bisserlis did in their answer.