We define
S = a string of L's and R's
f(S) = fraction corresponding to S
M(S) = ((n m) (n' m')) = a 2x2 matrix that holds the four quantities involved in the ancestral fractions m/n and m'/n'
M(I) = ((1 0) (0 1))
M(SL) = M(S) . ((1 0) (1 1))
M(SR) = M(S) . ((1 1) (0 1))
Therefore, if we define L and R as 2x2 matrices,
L = ((1 0) (1 1))
R = ((1 1) (0 1))
In Scheme:
(define I '((1 0) (0 1)))
(define R '((1 0) (1 1)))
(define L '((1 1) (0 1)))While we're at it let's define a few useful operations.
Since we're representing matrices as lists, we'll need matrix multiplication
(define (mat-mul m1 m2)
(map
(lambda (row)
(apply map (lambda column (apply + (map * row column))) m2))
m1))and conversion from the 2x2 matrix representation to rational number
(define (mat->rat mat)
`(/ ,(+ (caadr mat) (cadadr mat)) ,(+ (caar mat) (cadar mat))))