Essentially, I think the best is the one using closures. In fact, while writing the python version, I also wrote a scheme version.
Although scheme is mostly a functional language, I will use the very same example to move towards a more imperative style. In Python I made my code "more functional"; the experiment is now making the code "more imperative" in scheme.
I show here the python code as an immediate reference:
@apply
def int2roman():
weights = { 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
90 : 'XC', 50 : 'L', 40 : 'XL', 10 : 'X',
9 : 'IX', 5 : 'V', 4 : 'IV', 1 : 'I'}
sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)
def int2roman(n):
thousands, n = divmod(n, 1000)
roman_digits = ['M', ] * thousands
for m, s in sorted_weights_tuples:
while n >= m:
roman_digits.append(s)
n -= m
return ''.join(roman_digits)
return int2roman
I wrote two helper functions: the first one essentially is equivalent to the inner while loop in Python, the other one to the for loop.
(define simplify-by-weight
(lambda (weight ch n digits)
(letrec ([sbw
(lambda (n digits)
(cond ((< n weight) (cons n digits))
(else
(sbw (- n weight) (cons ch digits)))))])
(sbw n digits))))
(define simplify-all
(lambda (weights n digits)
(cond
((null? weights) digits)
(else
(let* ([ret (simplify-by-weight (caar weights) (cadar weights) n digits)]
[n (car ret)]
[digits (cdr ret)])
(simplify-all (cdr weights) n digits))))))
The idea to make the code more imperative looking or more imperative tout court comes from the idea that 4 lines in Python became 18 lines in scheme. This is not a "python vs. scheme". The solution I proposed in Python is, in my opinion, far more easier to read and undertand because it's so much shorter and the scheme version is cluttered with iteration details/function calls where it should have been much easier. New versions will be proposed. In the meantime, here it is the main function:
(define integer->roman-a
(let ([weights (sort '((1 "I") (4 "IV") (5 "V") (9 "IX") (10 "X")
(40 "XL") (50 "L") (90 "XC") (100 "C")
(400 "CD") (500 "D") (900 "CM"))
>
#:key car)])
(lambda (n)
(let-values ([(thousands n) (quotient/remainder n 1000)])
(foldl string-append ""
(simplify-all weights n(build-list thousands (lambda (_) "M")))))))
)
Apparently this is not a closure. However, remember that in scheme let is essentially syntactical sugar over a lambda form. In fact, we could have been made the closure more apparent writing the function this way: (define integer->roman-b
((lambda (weights)
(lambda (n)
(let-values ([(thousands n) (quotient/remainder n 1000)])
(foldl string-append ""
(simplify-all weights n(build-list thousands (lambda (_) "M")))))))
(sort '((1 "I") (4 "IV") (5 "V") (9 "IX") (10 "X")
(40 "XL") (50 "L") (90 "XC") (100 "C")
(400 "CD") (500 "D") (900 "CM"))
>
#:key car)))
I have to confess that I like the foldl/string-append thing more than the python append/join.
This is, of course, just a matter of taste. I could have made the code simpler pushing the while logic in an iterator and then simply using list comprehensions. However, I believe the design would have been far more complicated.
In order to simplify the code of the first two functions, I will:
- use more special forms (or different variants of special forms)
- try to eliminate the functions as independent units
- if necessary, use more forms provided by racket (most of them can be added to any scheme with macros)
(define simplify-by-weight
(lambda (weight ch n digits)
(let loop ([n n] [digits digits])
(cond ((< n weight) (cons n digits))
(else
(loop (- n weight) (cons ch digits)))))))
It is simple enough to be removed:
(define simplify-all
(lambda (weights n digits)
(cond
((null? weights) digits)
(else
(let* ([weight (caar weights)]
[ch (cadar weights)]
[ret (let loop ([n n] [digits digits])
(cond ((< n weight) (cons n digits))
(else
(loop (- n weight) (cons ch digits)))))]
[n (car ret)]
[digits (cdr ret)])
(simplify-all (cdr weights) n digits))))))
In fact, with let-values and values code could be simplified a lot.
Essentially here the problem is that we have two nested loops
and they loop on two different things and the value of n is logically modified.
Here we are simply using named lets to express loops:
(define simplify-all
(lambda (weights n digits)
(let next-weight ([n n]
[digits digits]
[weight-pair (car weights)]
[weights (cdr weights)])
(let ([weight (car weight-pair)]
[ch (cadr weight-pair)])
(let simplify-again ([n n] [digits digits])
(cond
((< n weight)
(cond
((null? weights) digits)
(else (next-weight n digits (car weights) (cdr weights)))))
(else
(simplify-again (- n weight) (cons ch digits)))))))))
Now the tentative is using the destructive state change:
(define simplify-all-e
(lambda (weights n digits)
(for-each
(lambda (weight-pair)
(let ([weight (car weight-pair)]
[ch (cadr weight-pair)])
(let simplify-again ()
(cond
((< n weight) null)
(else
(set! n (- n weight))
(set! digits (cons ch digits))
(simplify-again))))))
weights)
digits))
The above code can be improved using the for special form and unless (which we should already have used): (define simplify-all
(lambda (weights n digits)
(for ([weight-pair weights])
(let ([weight (car weight-pair)]
[ch (cadr weight-pair)])
(let simplify-again ()
(unless (< n weight)
(set! n (- n weight))
(set! digits (cons ch digits))
(simplify-again)))))
digits))
We are still longer than the four python lines, but we are no longer more complicated. In fact, considering scheme macros, we can define a while/until pair of special forms which simplify the code greatly:
(define simplify-all-g
(lambda (weights n digits)
(for ([weight-pair weights])
(let ([weight (car weight-pair)]
[ch (cadr weight-pair)])
(until (< n weight)
(set! n (- n weight))
(set! digits (cons ch digits)))))
digits)) Some performance measures here.
No comments:
Post a Comment