本を読む

読書やコンピュータなどに関するメモ

FizzBuzzとGaucheで学ぶ遅延評価の基礎の基礎

 先週、仲間内で初心者向け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"

 めでたしめでたし。

コメント

コメントの投稿

管理者にだけ表示を許可する

トラックバック

http://emasaka.blog65.fc2.com/tb.php/392-6d37929c

 | HOME | 

Categories

Recent Entries

Recent Comments

Recent Trackbacks

Appendix

emasaka

emasaka

フリーター。
連絡先はこのへん

Monthly


FC2Ad