tail call

Python Scheme

うーん、Scheme のコードは末尾再帰になっていないので、普通にスタックを食い尽くす危険性があるように思うのだが、どうなんだろう。Scheme に詳しくないのではずしているかもしれないが。あと、length 使うと遅そうだ。
適当にベンチマーク。

(use srfi-1)

(define (has l n)
  (cond ((zero? n) #t)
        ((pair? l) (has (cdr l) (- n 1)))
        (#t #f)))

(define (bigram1 data)
  (if (< (length data) 2)
      '()
      (cons (list (car data) (cadr data)) (bigram1 (cdr data)))))

(define (bigram2 data)
  (if (not (has data 2))
      '()
      (cons (list (car data) (cdr data)) (bigram2 (cdr data)))))

(define (bigram3 data)
  (letrec ((iter (lambda (data l)
                   (if (has data 2)
                       (iter (cdr data) (cons (list (car data) (cadr data)) l))
                       l))))
    (reverse (iter data '()))))

(define (main args)
  (let ((l (iota 50000)))
    (time (bigram1 l))
    (time (bigram2 l))
    (time (bigram3 l))))

% gosh bigram.scm
;(time (bigram1 l))
; real   7.810
; user   0.000
; sys    7.790
;(time (bigram2 l))
; real   0.225
; user   0.040
; sys    0.190
;(time (bigram3 l))
; real   0.064
; user   0.000
; sys    0.070

あとまぁ、Python ならジェネレータを使うのがいいんじゃないかな。

def bigram(data):
    return (data[i:i+2] for i in xrange(len(data) - 2))

とか。別にリスト内包でもいいと思うけど。
ちなみに、

Pythonのrange関数相当のものがschemeにも標準であるはずだと思うんだけどなあ。

srfi-1 の iota がそうですね。