gistfile1.txt

data Nat = Zero | Succ Nat | Twice Nat Nat deriving (Eq, Ord, Read, Show)

half :: Nat -> Nat
half Zero = Zero
half (Succ n) = half n
half (Twice _ n) = n

-- pred
p :: Nat -> Nat
p Zero = Zero
p (Succ n) = n
p (Twice n _) = n

-- succ
s :: Nat -> Nat
s (Succ n) = twice (s (half n))
s n = Succ n

twice :: Nat -> Nat
twice Zero = Zero
twice n = Twice (s (twice (p n))) n

-- fromInteger
fi :: Integer -> Nat
fi 0 = Zero
fi n = case n `quotRem` 2 of
	(q, r) -> (if r == 0 then id else s) (twice (fi q))