Possibly Pythonic Tail Call Optimization (TCO/TRE)

Marko Rauhamaa marko at pacujo.net
Mon Jul 13 21:07:31 CEST 2015


Ethan Furman <ethan at stoneleaf.us>:

> I would love to see good functional examples as it is definitely a
> weak spot for me.

Oh, if you want to go functional, you should look at idiomatic Scheme
code:

========================================================================
(define (common-prefix-length bytes-a bytes-b)
  (let loop ((list-a (string->list bytes-a))
             (list-b (string->list bytes-b))
             (common-length 0))
    (cond
     ((null? list-a) common-length)
     ((null? list-b) common-length)
     ((= (car list-a) (car list-b))
      (loop (cdr list-a) (cdr list-b) (+ common-length 8)))
     (else
      (+ common-length
         (vector-ref bit-match
                     (- 8 (integer-length (logxor (car list-a)
                                                  (car list-b))))))))))
========================================================================

Or, translated into (non-idiomatic) Python code:

========================================================================
def common_prefix_length(bytes_a, bytes_b):
    def loop(list_a, list_b, common_length):
        if not list_a:
            return common_length
        if not list_b:
            return common_length
        if list_a[0] == list_b[0]:
            return loop(list_a[1:], list_b[1:], common_length + 8)
        return common_length + \
               bit_match[8 - integer_length(list_a[0] ^ list_b[0])]
    return loop(bytes_a, bytes_b, 0)
========================================================================


Marko


More information about the Python-list mailing list