2007-12-29

[メモ]再帰を使うとn-gramはすっきり書ける

例として、bigramを生成する関数。

再帰を使わないバージョン(Python)

def bigram(data):
if len(data) < 2:
return
prev = data[0]
for x in data[1:]:
yield [prev, x]
prev = x

再帰を使ったバージョン(Scheme)
(define (bigram data)
(if (< (length data) 2)
'()
(cons (list (car data) (cadr data)) (bigram (cdr data)))))


Pythonだと再帰の深さの制限があるので、このような書き方はできませんが。
補: 念のためやってみた。
def bigram2(data):
if len(data) < 2:
return []
return [[data[0], data[1]],] + bigram2(data[1:])

↑Pythonでこう書ければいいんだけど、すぐに"maximum recursion depth exceeded"になるよ。

補: 実際にschemeでエラーにならないことも確認。
(define (bigram data)
(if (< (length data) 2)
'()
(cons (list (car data) (cadr data)) (bigram (cdr data)))))

(define (range x)
(let loop ((ini 0))
(if (= ini x)
'()
(cons ini (loop (+ ini 1))))))

(print (bigram (range 10000)))


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