Peano and Church Numerals in Functional Programming

This repository demonstrates how to represent natural numbers in functional programming using Peano numerals and Church numerals. The code is implemented in both Haskell and OCaml, showcasing different approaches to modeling natural numbers, along with basic operations on these representations.

Key Concepts

1. Peano Numerals

Peano numerals are a way of representing natural numbers using a recursive data structure. Each natural number is represented as either:

• O (zero)
• S n (the successor of a natural number n)

For example:

• O represents 0
• S O represents 1
• S (S O) represents 2
• and so on...

2. Church Numerals

Church numerals are another way of representing natural numbers using functional abstractions. A Church numeral is a higher-order function that represents a number as a function that applies a given function n times to an argument.

For example:

• 0 is represented by a function that applies its argument 0 times.
• 1 is a function that applies its argument 1 time.
• 2 applies the argument twice, and so on...

3. Scott Numerals

Scott numerals represent natural numbers as case-analysis functions: Each number is a higher-order function that chooses between:

• A "zero" case (a), or
• A "successor" case (Scott -> a).

This mimics pattern matching in a purely functional way. Scott is a function that takes:

• A value for the zero case (a).
• A continuation for the successor case (Scott -> a).

The runScott unwrapper lets us apply the function.

The runScott unwrapper lets us apply the function.

Feature	Peano Numerals	Church Numerals	Scott Numerals
Representation	O, S Peano (data type)	λf.λx. f (f ... x) (functions)	λz.λs. s (s ... z) (case analysis)
Pattern Matching	Direct (case expressions)	Iterated function application	Explicit zero/successor branches
Recursion	Structural recursion	Iteration (fold)	Case-based recursion
Efficiency	Slow (unary)	Moderate (composable)	Moderate (similar to Church)

Haskell Section

Key Features

• Peano Numerals: A simple algebraic data type to represent natural numbers.
• Church Numerals: Church encoding for natural numbers using higher-order functions.
• Basic Operations: Functions for addition, multiplication, and exponentiation on both Peano and Church numerals.

Installation

To use this library, you need to have GHC (Glasgow Haskell Compiler) installed. You can install it from Haskell's official website.

ghc --make Main.hs
./Main