2 people like it.
Like the snippet!

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

Raw view Test code New version

More information

Link:	http://fssnip.net/7X4
Posted:	5 years ago
Author:	Steve Goguen
Tags:	ast , discriminated union type , domain-specific language , encoding , recursion