Scheme - 標準部品化力、オブジェクトおよび状態(ストリーム(ストリームパラダイムの開発(対の無限のストリーム(要素を交互にとる(interleave)))))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力、オブジェクトおよび状態)、3.5(ストリーム)、3.5.3(ストリームパラダイムの開発)、対の無限のストリーム、問題 3.66.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 3.66.

    1     2     3     4     5
1 (1,1) (1,2) (1,3) (1,4) (1,5)
2       (2,2) (2,3) (2,4) (2,5)
3             (3,3) (3,4) (3,5)
4                   (4,4) (4,5)
5                         (5,6)

(i, j)の前に、近似的に何個の対がくるか考える。

• i = 1 場合、0, 1, 3, 5, 7, … となり、(2^1 * j - 2^1) - 1個 (j > 1)
• i = 2 の場合、2, 4, 8, 12, 16, …となり、(2^2 * j - 2^2) - 1個 (j > 1)
• …
• i = 99 の場合、(2^99 * j - 2^99) - 1個 (j > 1)
• i = 100 の場合、(2^100 * j - 2^100) - 1個(j > 1)

よって、対(1, 100)の前には197個、対(99, 100)の前には(2^99 * 99 - 2^99) - 1個、対(100, 100)の前には(2^100 * 100 - 2^100) - 1個の対が来る。

コード(BBEdit, Emacs)

sample66.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

(load "./stream.scm")

(define (enumerate-interval low high)
  (if (> low high)
      '()
      (cons low
            (enumerate-interval (+ low 1)
                                high))))

(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2
                               (stream-cdr s1)))))

(define (pairs s t)
  (cons-stream
   (list (stream-car s)
         (stream-car t))
   (interleave
    (stream-map (lambda (x)
                  (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s)
           (stream-cdr t)))))

(define s (pairs integers integers))

(print (stream-ref s 197))
;; 以下は、メモリ不足で実行できず
;; (print (stream-ref s (- (* (expt 2 99) 98) 1)))
;; (print (stream-ref s (- (* (expt 2 100) 99) 1)))
(print (stream-ref s 196))
(print (stream-ref s 198))

(for-each (lambda (n)
            (print (stream-ref s n)))
          (enumerate-interval 0 100))

入出力結果(Terminal(gosh), REPL(Read, Eval, Print, Loop))

$ ./sample66.scm
(1 100)
(2 51)
(4 16)
(1 1)
(1 2)
(2 2)
(1 3)
(2 3)
(1 4)
(3 3)
(1 5)
(2 4)
(1 6)
(3 4)
(1 7)
(2 5)
(1 8)
(4 4)
(1 9)
(2 6)
(1 10)
(3 5)
(1 11)
(2 7)
(1 12)
(4 5)
(1 13)
(2 8)
(1 14)
(3 6)
(1 15)
(2 9)
(1 16)
(5 5)
(1 17)
(2 10)
(1 18)
(3 7)
(1 19)
(2 11)
(1 20)
(4 6)
(1 21)
(2 12)
(1 22)
(3 8)
(1 23)
(2 13)
(1 24)
(5 6)
(1 25)
(2 14)
(1 26)
(3 9)
(1 27)
(2 15)
(1 28)
(4 7)
(1 29)
(2 16)
(1 30)
(3 10)
(1 31)
(2 17)
(1 32)
(6 6)
(1 33)
(2 18)
(1 34)
(3 11)
(1 35)
(2 19)
(1 36)
(4 8)
(1 37)
(2 20)
(1 38)
(3 12)
(1 39)
(2 21)
(1 40)
(5 7)
(1 41)
(2 22)
(1 42)
(3 13)
(1 43)
(2 23)
(1 44)
(4 9)
(1 45)
(2 24)
(1 46)
(3 14)
(1 47)
(2 25)
(1 48)
(6 7)
(1 49)
(2 26)
(1 50)
(3 15)
(1 51)
(2 27)
$