Look and Say 数列

ちょっと面白いものを見つけた。

　cf. 「Haskell」で「Look and Say 数列」を生成してみた – Zodiacの黙示録

Look and Say 数列とは次のようなものらしい。

1 11 21 1211 111221 ...

ちょっと規則性が見いだせないが、

1. 最初の項は「1」
2. 次の項は直前の項を見る(look)。すると「1」個の「1」。
3. なので「11」と言う(say)。
4. さらに次の項は直前の項を見て、「2」個の「1」。
5. なので「21」と言う。
6. 以下繰り返し

となっている。

リンク先では Haskell でやっているので、Scheme でやってみた。Haskell と違って無限リストは扱えないので、スクリプトの引数で生成する数列の数を指定するようにした。

(use srfi-1)
(use gauche.sequence)

(define main
  (lambda (args)
    (let ((count (string->number (cadr args))))
      (print (look-and-say count)))))

(define look-and-say
  (lambda (count)
    (unfold (lambda (seed) (zero? (car seed)))
            (lambda (seed) (cadr seed))
            (lambda (seed) (list (- (car seed) 1) (las (cadr seed))))
            (list count "1"))))

(define las
  (lambda (s)
    (let ((ls (group-sequence s)))
      (apply string-append
        (append-map (lambda (e)
          (list (write-to-string (length e)) (string (car e))))
            ls)))))

unfold のために srfi-1 を、group-sequence のために gauche.sequence を読み込んでいる。
group-sequence はリストや文字列といった sequence を、同じ値ごとにグループ化する手続き。こんな感じ：

gosh> (group-sequence "aabccdddee")
((#\a #\a) (#\b) (#\c #\c) (#\d #\d #\d) (#\e #\e))

さて、実行してみよう。

takatoh@apostrophe $ gosh look-and-say.scm 8
(1 11 21 1211 111221 312211 13112221 1113213211)

うまくいったようだ。