6/27/2017

Peano goes Maybe

Just for the fun of it, let's represent Nats as Maybies in Haskell.

import Prelude hiding (succ)
-- A strange representation of Nats
newtype Nat = Nat { getNat :: Maybe Nat }
-- Peano zero
zero :: Nat
zero = Nat Nothing
-- Peano successor
succ :: Nat -> Nat
succ = Nat . Just
-- Primitive recursion for addition
add :: Nat -> Nat -> Nat
add x = maybe x (succ . add x) . getNat
-- Convert primitive Int into strange Nat
fromInt :: Int -> Nat
fromInt 0 = Nat Nothing
fromInt x = succ (fromInt (x-1))
-- Convert strange Nat into primitive Int
toInt :: Nat -> Int
toInt = maybe 0 ((+1) . toInt) . getNat
-- Let's test
main = print $ toInt (add (fromInt 20) (fromInt 22))

I wrote this code in response to a student question, whether and, if so, how one could code recursive functions on maybies. This inspired me towards the exam question as to how the above code compares to more straightforward code which would uses an algebraic datatype with Zero and Succ constructors instead of maybies.

No comments:

Post a Comment