月: 2015年3月

昨日の make-byte-string の項で出てきた #*”aaaaa” というのは不完全文字列（incomplete string）というものらしい。#*”…” というのが不完全文字列のリテラルね。

文字列について – Gauche – A Scheme Implementation から引用すると、

不完全文字列

全てのバイト列が可変長エンコーディングとして正しく解釈できるわけではない。 定義されていないコードポイントを指している場合はまだ可変長文字列として扱えるが、 そのエンコーディングではどうにも解釈しようの無いバイトシーケンスというのが 外部から入って来る可能性がある。

Gaucheではこのような文字列をincomplete stringと呼び、そのようにマークされる。 文字列操作系の関数は、incomplete stringを可能な限りあたかも1バイト固定長文字列のように扱う。 incomplete stringとcomplete stringが接合された場合、 結果はincomplete stringになる。

要するに、文字として解釈できない可能性のある文字列（バイト列）を不完全文字列と呼ぶようだ。

文字列が不完全文字列かどうかは string-incomplete? で判断できる。

gosh> (string-incomplete? "abc")
#f
gosh> (string-incomplete? #*"abc")
#t

フツウの文字列 “abc” では #f が、不完全文字列 #*”abc” では #t が返ってきた。なるほど。

「外部から入って来る」というのは、例えばコマンドライン引数なんかだろうか。

(define main
  (lambda (args)
    (print (string-incomplete? (cadr args)))))

takatoh@nightschool $ gosh string-incomplete.scm foo
#f

あれ、#f が返ってきた。てことは不完全文字列じゃないってことだ。
ファイルから入力した場合はどうだろう？

(define main
  (lambda (args)
    (print (string-incomplete? (call-with-input-file (cadr args) port->string)))))

takatoh@nightschool $ gosh string-incomplete2.scm input.txt
#f

これも #f だ。
どういう時に不完全文字列になるんだろう？

コメントで string という手続きを教えてもらった。

　cf. 6.12 文字列 – Gauche ユーザリファレンス

gosh> (string #\a)
"a"

これを使えば、昨日の string->string-list はこう書ける。

gosh> (define string->string-list
  (lambda (s)
    (map string (string->list s))))
string->string-list
gosh> (string->string-list "abc")
("a" "b" "c")

うーん、上のページは目を通したはずなんだけど見落としてたよ。文字列を「変換する」方法ばかり探してたからかもしれない。文字列の構築子の項にちゃんと載ってた。

せっかくなので、文字列を作る方法について少しまとめておこう。

string char …

上でも書いたように、文字から文字列を作る。引数の文字は１つじゃなくてもいい。

gosh> (string #\a #\b #\c)
"abc"

make-string k :optional char

長さ k の文字列を返す。char が与えられればそれで内容を満たすってあるけど、なかったらどうなるんだ？

gosh> (make-string 5 #\x)
"xxxxx"
gosh> (make-string 5)
"     "

なるほど、スペースが使われるのね。

make-byte-string k :optional byte

make-string に似てるけど、オプショナルな引数 byte は文字じゃなくて整数。

gosh> (make-byte-string 5)
#*"\0\0\0\0\0"
gosh> (make-byte-string 5 97)
#*"aaaaa"

んむ、なんか見たことのない表現が出てきた。

x->stirng obj

文字列への強制型変換手続き。簡単に言うと obj を表示するときの文字列に変換される、ってことでいいのかな。

gosh> (x->string "abc")
"abc"
gosh> (x->string 123)
"123"
gosh> (x->string 'foo)
"foo"
gosh> (x->string '(1 2 3))
"(1 2 3)"

[追記]

コメントでは gauche.collection モジュールの map を使う方法も教えてもらったので、それも書いておこう。標準ライブラリの map はリストしか受け付けないけど、gauche.collection モジュールの map は文字列を含むコレクションにを受け付ける。なので、string->list を省略できる。

gosh> (use gauche.collection)
#<undef>
gosh> (define string->string-list
  (lambda (s)
    (map string s)))
string->string-list
gosh> (string->string-list "abc")
("a" "b" "c")

文字のリストにするのには string->list が使える。

gosh> (string->list "abc")
(#\a #\b #\c)

でも今日欲しいのは文字のリストじゃなくて、文字列（長さ１）のリストだ。例えば Ruby ではこう書ける。

2.1.1 :001 > "abc".split(//)
 => ["a", "b", "c"]

空（？）の正規表現で分割すると１文字ずつの配列になる。Ruby じゃ定番だね。

で、Scheme。string-split が正規表現も受け付けてくれるというので、上と同じように試したらダメだった。

gosh> (string-split "abc" #//)
*** ERROR: string-split: splitter must not match a null string: #//
Stack Trace:
_______________________________________
  0  (error "string-split: splitter must not match a null string:" spli ...
        At line 58 of "/usr/share/gauche-0.9/0.9.3.3/lib/gauche/stringutil.scm"
  1  scanner

結局こういうのふうに書いてみたけど、なんかスマートじゃない。

gosh> (define string->string-list
  (lambda (s)
    (map (lambda (c) (list->string (list c))) (string->list s))))
string->string-list
gosh> (string->string-list "abc")
("a" "b" "c")

文字から長さ１の文字列へ変換する手続きが見当たらないんだよな。需要がないのかな。

昨日に引き続き CodeEval から。

　cf. Max Range Sum – CodeEval

(define slices
  (lambda (lis n)
    (let loop ((l1 lis) (l2 '()))
      (if (< (length l1) n)
          (reverse l2)
          (loop (cdr l1)
            (cons (take l1 n) l2))))))

(define sum
  (lambda (lis)
    (apply + lis)))

(define solv
  (lambda (str)
    (let* ((s (string-split str ";"))
           (n (string->number (car s)))
           (lis (map string->number (string-split (cadr s) " "))))
      (apply max (cons 0 (map sum (slices lis n)))))))

(define print-solv
  (lambda (str)
    (print (solv str))))

(define main
  (lambda (args)
    (with-input-from-file (cadr args)
      (lambda ()
        (port-for-each print-solv read-line)))))

takatoh@nightschool $ cat input.txt
5;7 -3 -10 4 2 8 -2 4 -5 -2
6;-4 3 -10 5 3 -7 -3 7 -6 3
3;-7 0 -45 34 -24 7
takatoh@nightschool $ gosh max_range_sum.scm input.txt
16
0
17

Details って意味がわかんないんだけど、CodeEval のこれ。

　cf. Details – CodeEval

Scheme でやってみた。

(define dots
  (lambda (lis)
    (let loop ((l lis) (d 0))
      (cond
        ((char=? (car l) #\Y) d)
        ((char=? (car l) #\.) (loop (cdr l) (+ d 1)))
        (else (loop (cdr l) 0))))))

(define solv
  (lambda (str)
    (apply min (map dots (map string->list (string-split str ","))))))

(define print-solv
  (lambda (str)
    (print (solv str))))

(define main
  (lambda (args)
    (with-input-from-file (cadr args)
      (lambda ()
        (port-for-each print-solv read-line)))))

基本的には CodeEval に提出した Python 版と同じ。

takatoh@nightschool $ cat input.txt
XX.YY,XXX.Y,X..YY,XX..Y
XXX.YYYY,X...Y..Y,XX..YYYY,X.....YY,XX....YY
XX...YY,X....YY,XX..YYY,X..YYYY
XXYY,X..Y,XX.Y
takatoh@nightschool $ gosh details.scm input.txt
1
1
2
0

たぶんあってる。

昨日、継続渡しの練習で partition という手続きを書いた。
同じ名前の手続きが SRFI-1 ライブラリに定義されている。けど、ちょっと動作が違う。

gosh> (use srfi-1)
#<undef>
gosh> (partition odd? '(1 2 3 4 5))
(1 3 5)
(2 4)

(1 3 5) と (2 4) がひとつのリストに入っているんじゃなくて、２行にわたって表示されている。実は、SRFI-1 の partition は２つの値を返している。partition のように２つ（あるいはそれ以上）の値を返すことを「多値」というらしい。

　cf. Scheme:多値

多値を返すには values を使う。

gosh> (values 'foo 'bar 'baz)
foo
bar
baz

一方、多値を受け取るには receive が使える。

gosh> (receive (odds evens) (partition odd? '(1 2 3 4 5))
  (print odds))
(1 3 5)
#<undef>

odds と evens が返される多値に束縛される変数だ。必要がないからといって、数を合わせないとダメらしい。

gosh> (receive (odds) (partition odd? '(1 2 3 4 5))
  (print odds))
*** ERROR: received more values than expected
Stack Trace:
_______________________________________

ふーん、なんとなくわかった（ような気がする）けど、ちょっとピンとこないな。

リストを、述語 p を適用した結果が真になるものと偽になるものに分ける partition を継続渡しスタイルで書いてみた。

(define partition
  (lambda (p lis co)
    (cond
      ((null? lis)
        (co '() '()))
      ((p (car lis))
        (partition p (cdr lis) (lambda (l r) (co (cons (car lis) l) r))))
      (else
        (partition p (cdr lis) (lambda (l r) (co l (cons (car lis) r))))))))

(print (partition odd? '(1 2 3 4 5) list))

takatoh@nightschool $ gosh partition.scm
((1 3 5) (2 4))

まずはフツウの再帰で書いたもの。

(define myfilter
  (lambda (proc lis)
    (cond
      ((null? lis) '())
      ((proc (car lis)) (cons (car lis) (myfilter proc (cdr lis))))
      (else (myfilter proc (cdr lis))))))

(print (myfilter odd? '(1 2 3 4 5)))

takatoh@nightschool $ gosh myfilter.scm
(1 3 5)

で、こっちが末尾再帰で書いたもの。

(define myfilter-tail
  (lambda (proc lis)
    (letrec ((iter (lambda (l1 l2)
      (cond
        ((null? l1) (reverse l2))
        ((proc (car l1)) (iter (cdr l1) (cons (car l1) l2)))
        (else (iter (cdr l1) l2))))))
          (iter lis '()))))

(print (myfilter-tail odd? '(1 2 3 4 5)))

内部で iter という局所関数を定義して、それを呼び出している。

takatoh@nightschool $ gosh myfilter-tail.scm
(1 3 5)

リストの要素を、隣り合った同じ要素ごとにまとめる。

(define group
  (lambda (lis)
    (let loop ((l1 (cdr lis)) (l2 (list (car lis))) (l3 '()))
      (cond
        ((null? l1) (reverse (cons l2 l3)))
        ((eq? (car l1) (car l2)) (loop (cdr l1) (cons (car l1) l2) l3))
        (else (loop (cdr l1) (list (car l1)) (cons l2 l3)))))))

(print (group '(1 1 2 2 3 3 3)))
(print (group '(a a b b b c c)))

takatoh@nightschool $ gosh group.scm
((1 1) (2 2) (3 3 3))
((a a) (b b b) (c c))

「同じ要素」を得るための proc を渡せるようにしたもの。

(define group-by
  (lambda (proc lis)
    (let loop ((l1 (cdr lis)) (l2 (list (car lis))) (l3 '()))
      (cond
        ((null? l1) (reverse (cons (reverse l2) l3)))
        ((eq? (proc (car l1)) (proc (car l2))) (loop (cdr l1) (cons (car l1) l2) l3))
        (else (loop (cdr l1) (list (car l1)) (cons (reverse l2) l3)))))))

(for-each print (group-by car '((1 1) (1 2) (2 3) (2 4) (2 5))))

ひとつのリストにしてしまうと見難いので for-each でグループごとに出力してみた。

takatoh@nightschool $ gosh group-by.scm
((1 1) (1 2))
((2 3) (2 4) (2 5))

[追記]

gauche.sequence モジュールの group-sequence を使うとおなじことが出来る。

gosh> (use gauche.sequence)
#<undef>
gosh> (group-sequence '(1 1 2 2 3 3 3))
((1 1) (2 2) (3 3 3))
gosh> (group-sequence '(a a b b b c c))
((a a) (b b b) (c c))
gosh> (for-each print (group-sequence '((1 1) (1 2) (2 3) (2 4) (2 5)) :key car))
((1 1) (1 2))
((2 3) (2 4) (2 5))
#<undef>