Hi!

I recently got engaged in a thread on comp.lang.functional about ML and

Lisp. I posted some simple but efficient OCaml code that is difficult to

translate into Lisp:

let rec ( +: ) f g = match f, g with

| `Q n,`

Q m -> `Q (n +/ m) |`

Q (Int 0), e | e, `Q (Int 0) -> e | f,`

Add(g, h) -> f +: g +: h

| f, g -> `Add(f, g)

let rec ( *: ) f g = match f, g with

| `Q n,`

Q m -> `Q (n */ m) |`

Q (Int 0), e | e, `Q (Int 0) ->`

Q (Int 0)

| `Q (Int 1), e | e,`

Q (Int 1) -> e

| f, `Mul(g, h) -> f *: g *: h | f, g ->`

Mul(f, g)

let rec simplify = function

| `Q _ |`

Var _ as e -> e

| `Add(f, g) -> simplify f +: simplify g |`

Mul(f, g) -> simplify f *: simplify g;;

This code does some simple rearrangements of symbolic expressions to

simplify them, e.g. 2+1*x+0 -> 2+x. It works with arbitrary-precision

rational arithmetic.

Does Ruby have pattern matching? If so, what does the above look like in

Ruby? If not, how else can you express this elegantly in Ruby?

Lisp doesn’t have pattern matching but Pascal Constanza wrote quite an

elegant solution in Lisp using dynamic method dispatch:

(defstruct add x y)

(defstruct mul x y)

(defgeneric simplify-add (x y)

(:method ((x number) (y number)) (+ x y))

(:method ((x (eql 0)) y) y)

(:method (x (y (eql 0))) x)

(:method (x (y add))

(simplify-add (simplify-add x (add-x y)) (add-y y)))

(:method (x y) (make-add :x x :y y)))

(defgeneric simplify-mul (x y)

(:method ((x number) (y number)) (* x y))

(:method ((x (eql 0)) y) 0)

(:method (x (y (eql 0))) 0)

(:method ((x (eql 1)) y) y)

(:method (x (y (eql 1))) x)

(:method (x (y mul))

(simplify-mul (simplify-mul x (mul-x y)) (mul-y y)))

(:method (x y) (make-mul :x x :y y)))

(defgeneric simplify (exp)

(:method (exp) exp)

(:method ((exp add))

(simplify-add (simplify (add-x exp)) (simplify (add-y exp))))

(:method ((exp mul))

(simplify-mul (simplify (mul-x exp)) (simplify (mul-y exp)))))

This has the advantage that Lisp optimises the above so that it is only

10x

slower than the OCaml. Unlike the OCaml, it can be extended and

automatically reoptimised at run-time.