2 people like it.

# Counting Languages - Converting integers to ASTs and back again

This little snippet shows you how you can create a simple recursive data type and define a pair of functions that maps the set of positive integers to unique instances in the AST and back again.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: ``` ``````module Cantor = let sqrt = float >> System.Math.Sqrt >> int let pair(k1:int, k2:int) = ((k1 + k2) * (k1 + k2 + 1) / 2) + k2 let unpair(z:int) = let w = ((sqrt(8 * z + 1) - 1) / 2) let t = (w * w + w) / 2 let y = z - t let x = w - y (x, y) /// A simple calculator AST type Calc = | Value of int // We'll have integers | Add of Calc * Calc // Addition | Mul of Calc * Calc // Multiplication /// Turns a positive integer into a unique instance of our calculator AST let rec fromInt n = let r = n % 3 let n = n / 3 let (x, y) = Cantor.unpair(n) match r with | 0 -> Value(n) | 1 -> Add((fromInt x), (fromInt y)) | 2 -> Mul((fromInt x), (fromInt y)) /// Turns out calculator AST into a string let rec toString = function | Value(n) -> string(n) | Add(l, r) -> sprintf "(%s + %s)" (toString l) (toString r) | Mul(l, r) -> sprintf "(%s * %s)" (toString l) (toString r) /// Convert a Calc expression into a unique integer let rec toInt = function | Value(n) -> n * 3 | Add(l, r) -> let (x, y) = (toInt l), (toInt r) let n = Cantor.pair(x, y) (n * 3) + 1 | Mul(l, r) -> let (x, y) = (toInt l), (toInt r) let n = Cantor.pair(x, y) (n * 3) + 2 // Let's demonstrate our fromInt and toInt functions are bijective by // enumerating the first million expressions and converting them back // to integers. for i in 0..1000000 do // Let's turn an integer into an expression let c = fromInt i // Then let's turn that expression back into an integer let i2 = toInt c if i <> i2 then // Show any expression that doesn't make the round trip printfn "Exception: %i - %i - %s" i i2 (toString c) ``````
val sqrt : (int -> int)

Full name: Script.Cantor.sqrt
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
namespace System
type Math =
static val PI : float
static val E : float
static member Abs : value:sbyte -> sbyte + 6 overloads
static member Acos : d:float -> float
static member Asin : d:float -> float
static member Atan : d:float -> float
static member Atan2 : y:float * x:float -> float
static member BigMul : a:int * b:int -> int64
static member Ceiling : d:decimal -> decimal + 1 overload
static member Cos : d:float -> float
...

Full name: System.Math
System.Math.Sqrt(d: float) : float
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val pair : k1:int * k2:int -> int

Full name: Script.Cantor.pair
val k1 : int
val k2 : int
val unpair : z:int -> int * int

Full name: Script.Cantor.unpair
val z : int
val w : int
val t : int
val y : int
val x : int
type Calc =
| Value of int
| Add of Calc * Calc
| Mul of Calc * Calc

Full name: Script.Calc

A simple calculator AST
union case Calc.Value: int -> Calc
union case Calc.Add: Calc * Calc -> Calc
union case Calc.Mul: Calc * Calc -> Calc
val fromInt : n:int -> Calc

Full name: Script.fromInt

Turns a positive integer into a unique instance of our calculator AST
val n : int
val r : int
module Cantor

from Script
val toString : _arg1:Calc -> string

Full name: Script.toString

Turns out calculator AST into a string
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string
val l : Calc
val r : Calc
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
val toInt : _arg1:Calc -> int

Full name: Script.toInt

Convert a Calc expression into a unique integer
val i : int32
val c : Calc
val i2 : int
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn