本を読む

　先週、仲間内で初心者向けRuby on Rails講座ってのを開く手伝いをしました。講座自体はさておき、懇親会のときに講師の人が、「Lispを勉強して、遅延評価で無限リストとかやってみたい」というようなこと（それだけじゃないけど）を言っていました。そこで、基本というか、教科書まんまな説明をしてみます。ほとんど、特定1人対象の内容です

　以下の例はScheme（Gauche）によります。

リストのn番めの要素を取り出す手続き

　まず、回り道ですが、リストのn番めの要素を取り出す手続きnthを定義してみます。FizzBuzz問題が1オリジンなので、ここではnthを1オリジンで定義してみます。Schemeの説明を省略すると、超単純なコードは以下のような感じかなと思います。

(define (nth lst n)
  (if (= n 1)
      (car lst)
      (nth (cdr lst) (- n 1)) ))

　試してみます。

gosh> (nth '(a b c) 1)
a
gosh> (nth '(a b c) 2)
b
gosh> (nth '(a b c) 3)
c

　うまくいっていますね。

forceを使え

　さて、ここにforceという呪文をかませたnth2を定義してみます。

(define (nth2 lst n)
  (if (= n 1)
      (car lst)
      (nth2 (force (cdr lst)) (- n 1)) ))

　再び試してみます。

gosh> (nth2 '(a b c) 1)
a
gosh> (nth2 '(a b c) 2)
b
gosh> (nth2 '(a b c) 3)
c

　まったく同じ結果ですね。

無限にFizzBuzzなリスト

　さて本番。nから順に無限にFizzBuzzなリストを作る手続きfizzbuzz-fromを考えてみます。単純に考えると、以下のようになるかと思います。

(define (fizzbuzz-from n)
  (cons (cond ((zero? (modulo n 15)) "FizzBuzz")
	      ((zero? (modulo n 3)) "Fizz")
	      ((zero? (modulo n 5)) "Buzz")
	      (else n) )
   	(fizzbuzz-from (+ n 1)) ))

　実行します。もちろん無限ループになって、帰ってきません。

gosh> (fizzbuzz-from 1)

遅延してみる

　帰ってこないのでは使いものになりませんね。そこで、再帰呼び出しの部分に「delay」という呪文をかませてみます。

(define (fizzbuzz-from n)
  (cons (cond ((zero? (modulo n 15)) "FizzBuzz")
	      ((zero? (modulo n 3)) "Fizz")
	      ((zero? (modulo n 5)) "Buzz")
	      (else n) )
	(delay (fizzbuzz-from (+ n 1))) ) )

　実行してみます。

gosh> (fizzbuzz-from 1)
(1 . #<promise 0x8160c60>)

　変な値が結果として表示されましたが、とりあえず無限ループにならずに帰ってきました。そこで、返された結果を、変数fizzbuzz-listの値として定義しておきます。

(define fizzbuzz-list (fizzbuzz-from 1))

　これで、無限にFizzBuzzなリストfizzbuzz-listができました。

遅延、カムバ～ック

　では、さきほどのnth2を使って、n番目の値を取り出してみます。

gosh> (nth2 fizzbuzz-list 1)
1
gosh> (nth2 fizzbuzz-list 2)
2
gosh> (nth2 fizzbuzz-list 3)
"Fizz"
gosh> (nth2 fizzbuzz-list 5)
"Buzz"
gosh> (nth2 fizzbuzz-list 30000)
"FizzBuzz"

　めでたしめでたし。