カテゴリー: Scheme

リストのn番目の要素を削除する

最初の要素は0番目。

(define delete-nth
  (lambda (lis n)
    (let loop ((c 0) (l lis) (r '()))
      (if (null? l)
          (reverse r)
          (if (= c n)
            (loop (+ c 1) (cdr l) r)
            (loop (+ c 1) (cdr l) (cons (car l) r)))))))

(print (iota 10))
(print (delete-nth (iota 10) 3))
(print '(a b c d e f g h i j))
(print (delete-nth '(a b c d e f g h i j) 3))
^o^ > gosh delete-nth.scm
(0 1 2 3 4 5 6 7 8 9)
(0 1 2 4 5 6 7 8 9)
(a b c d e f g h i j)
(a b c e f g h i j)

ちゃんと 3 と d が消えている。

これを拡張して、「n番目」を複数とれるようにしてみよう。

(define delete-nth
  (lambda (lis . ns)
    (let loop ((c 0) (l lis) (r '()))
      (if (null? l)
          (reverse r)
          (if (include? c ns)
              (loop (+ c 1) (cdr l) r)
              (loop (+ c 1) (cdr l) (cons (car l) r)))))))

(define include?
  (lambda (x lis)
  (cond ((null? lis) #f)
        ((= x (car lis)) #t)
        (else (include? x (cdr lis))))))

(print (iota 10))
(print (delete-nth (iota 10) 3 5 7))
(print '(a b c d e f g h i j))
(print (delete-nth '(a b c d e f g h i j) 3 5 7))
^o^ > gosh delete-nth2.scm
(0 1 2 3 4 5 6 7 8 9)
(0 1 2 4 6 8 9)
(a b c d e f g h i j)
(a b c e g i j)

要素がリストに含まれているか否かを判定する述語が見当たらなかったので、include? を自作した。

整数のリストを作る(2)－あるいは省略可能な引数の扱いについて

先週のエントリを見て省略可能な引数を扱う方法を書いてくれた人がいる。

　cf. 省略可能引数 – 主題のない日記

そこでは、R6RS/R7RS で定められている case-lambda と Gauche の拡張である let-optionals* が紹介されている。どちらも省略可能な引数を簡単に扱うためのマクロのようだ。

my-iota を case-lambda を使って書くとこうなる。

(define my-iota
  (case-lambda
    ((count) (my-iota count 0 1))
    ((count start) (my-iota count start 1))
    ((count start step)
      (let loop ((c count)
        (i (+ start (* (- count 1) step)))
        (lis '()))
        (if (= c 0)
            lis
            (loop (- c 1) (- i step) (cons i lis)))))))

(print (my-iota 10))
(print (my-iota 10 2))
(print (my-iota 10 2 2))
(print (my-iota 10 2 -2))

ついでに step に負数を指定すると期待通りに動作しない不具合も直しておいた。
実行例：

^o^ > gosh my-iota4a.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)
(2 0 -2 -4 -6 -8 -10 -12 -14 -16)

一方、let-optionals* を使って書くとこんな感じ：

(define my-iota
  (lambda (count . restargs)
    (let-optionals* restargs
      ((start 0)
       (step 1))
      (let loop ((c count)
        (i (+ start (* (- count 1) step)))
        (lis '()))
        (if (= c 0)
            lis
            (loop (- c 1) (- i step) (cons i lis)))))))

(print (my-iota 10))
(print (my-iota 10 2))
(print (my-iota 10 2 2))
(print (my-iota 10 2 -2))
^o^ > gosh my-iota4b.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)
(2 0 -2 -4 -6 -8 -10 -12 -14 -16)

当然ながら実行結果はどちらも同じだけど、どちらかというと case-lambda のほうが好みだな。引数の数でパターンマッチしてる感じがいい。let-optionals* だと省略可能引数の部分だけ別に書くことになるのでコードの見通しが悪いような気がする。

Gauche のマニュアルだと、case-lambda は http://practical-scheme.net/gauche/man/gauche-refj_24.html の一番下、let-optionals* は http://practical-scheme.net/gauche/man/gauche-refj_58.html の 6.18.4 省略可能引数のパージング にある。

整数のリストを作る

たまには Scheme を。

Scheme で整数のリストを作るには iota 手続きが使える。

^o^ > gosh
gosh> (iota 10)
(0 1 2 3 4 5 6 7 8 9)
gosh> (iota 10 2)
(2 3 4 5 6 7 8 9 10 11)
gosh> (iota 10 2 2)
(2 4 6 8 10 12 14 16 18 20)

これを自前で実装してみよう。
最初に作ったのがこれ。可変長引数なので、引数の数に応じて対応する補助手続きを呼び出している。

(define my-iota
  (lambda (n . args)
    (cond ((null? args) (my-iota-simple n))
          ((= (length args) 1) (my-iota-start n (car args)))
          (else (my-iota-step n (car args) (cadr args))))))

(define my-iota-simple
  (lambda (n)
    (let loop ((start 0) (i (- n 1)) (lis '()))
      (if (< i start)
          lis
          (loop start (- i 1) (cons i lis))))))

(define my-iota-start
  (lambda (n start)
    (let loop ((i (- (+ start n) 1)) (lis '()))
      (if (< i start)
          lis
          (loop (- i 1) (cons i lis))))))

(define my-iota-step
  (lambda (n start step)
    (let loop ((i (+ start (* (- n 1) step))) (lis '()))
      (if (< i start)
          lis
          (loop (- i step) (cons i lis)))))) (print (my-iota 10))

(print (my-iota 10 2))
(print (my-iota 10 2 2))

実行例：

^o^ > gosh my-iota.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)

上の実装では3つの補助手続きを定義しているけど、内容は同じようなものなので1つにまとめることにした。つまり、引数を3つとる補助手続き my-iota-general を定義しておいて、本体手続き my-iota のほうで場合分けをして呼び出す。

(define my-iota
  (lambda (n . args)
    (cond ((null? args) (my-iota-general n 0 1))
          ((= (length args) 1) (my-iota-general n (car args) 1))
          (else (my-iota-general n (car args) (cadr args))))))

(define my-iota-general
  (lambda (n start step)
    (let loop ((i (+ start (* (- n 1) step))) (lis '()))
      (if (< i start)
          lis
          (loop (- i step) (cons i lis))))))

(print (my-iota 10))
(print (my-iota 10 2))
(print (my-iota 10 2 2)) 
^o^ > gosh my-iota2.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)

だいぶシンプルになった。もう一歩進めてみよう。上の my-iota 手続きの中では場合分けをして my-iota-general の引数 start、step を決めているので、let で局所変数にしてしまえば my-iota-general の本体部分を取り込むことができる。

(define my-iota
  (lambda (n . args)
    (let ((start (if (>= (length args) 1) (car args) 0))
          (step (if (>= (length args) 2) (cadr args) 1)))
         (let loop ((i (+ start (* (- n 1) step))) (lis '()))
           (if (< i start)
               lis
               (loop (- i step) (cons i lis)))))))

(print (my-iota 10))
(print (my-iota 10 2))
(print (my-iota 10 2 2)) 
^o^ > gosh my-iota3.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)

めでたく1つの手続きにできた。

文字列を指定した文字数ごとに分割する

今日は Windows マシンから更新。

　cf. ruby 文字列を指定数で分割する – それマグで！

Haskell でやってみた。

module Main where

slices :: Int -> [a] -> [[a]]
slices _ [] = []
slices n xs = h : slices n d
  where
    (h, d) = splitAt n xs

main :: IO ()
main = print $ slices 3 "abcdefghijklmnopqrstuvwxyz"
^o^ > runhaskell stringSlices.hs
["abc","def","ghi","jkl","mno","pqr","stu","vwx","yz"]

Scheme だとこう。

(define slices
  (lambda (lis n)
    (if (< (length lis) n)
      (list lis)
      (cons (take lis n) (slices (drop lis n) n)))))

(define string-slices
  (lambda (str n)
    (map list->string (slices (string->list str) n))))

(print (string-slices "abcdefghijklmnopqrstuvwxyz" 3))
^o^ > gosh string-slices.scm
(abc def ghi jkl mno pqr stu vwx yz)

最後に JavaScript。

function stringSlices(n, str) {
  var l = str.length;
  var result = [];
  for (var i = 0; i < l; i += n) {
    result.push(str.slice(i, i + n));
  }
  return result;
}

console.log(stringSlices(3, "abcdefghijklmnopqrstuvwxyz"));
^o^ > node stringSlices.js
[ 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu', 'vwx', 'yz' ]

これ、もうちょっとスマートにいかないかな。

[追記]

JavaScript 版、Haskell 版や Scheme 版と同じように考えてみた。少しはスマートになったかな。そうでもないか？

function stringSlices(n, str) {
  if (str.length == 0) {
    return [];
  } else {
    var l = stringSlices(n, str.slice(n))
    l.unshift(str.slice(0, n))
    return l
  }
}

console.log(stringSlices(3, "abcdefghijklmnopqrstuvwxyz"));
^o^ > node stringSlices2.js
[ 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu', 'vwx', 'yz' ]

文字列をリストで与えられた長さに区切る

例えば Ruby で書くとこういうやつ。

def split_with(str, lis)
  a = Array.new(lis.size, "A")
  tmpl = a.zip(lis).map{|x, y| x + y.to_s }.join("")
  str.unpack(tmpl)
end

p split_with("abcdefghij", [1, 2, 3, 4])
takatoh@nightschool $ ruby split_with.rb
["a", "bc", "def", "ghij"]

Scheme ではどうだろう。

フツウの再帰版

(define split-with
  (lambda (str lis)
    (let loop ((sl (string->list str)) (l lis))
      (cond
        ((null? l) '())
        (else (cons (list-&gt;string (take sl (car l)))
          (loop (drop sl (car l)) (cdr l))))))))

(print (split-with "abcdefghij" '(1 2 3 4)))

なんの工夫もない。

takatoh@nightschool $ gosh split-with.scm
(a bc def ghij)

末尾再帰版

ちょっと工夫して末尾再帰。

(define split-with
  (lambda (str lis)
    (let loop ((sl (string-&gt;list str)) (l1 lis) (l2 '()))
      (cond
        ((null? l1) (reverse l2))
        (else (loop (drop sl (car l1))
                (cdr l1)
                (cons (list-&gt;string (take sl (car l1))) l2)))))))

(print (split-with "abcdefghij" '(1 2 3 4)))
takatoh@nightschool $ gosh split-with2.scm
(a bc def ghij)

map-accum版

もう少し何かないかと探したら、map-accum があった。

(use gauche.collection)

(define split-with
  (lambda (str lis)
    (let ((f (lambda (n sl) (values (take sl n) (drop sl n)))))
      (receive (l s) (map-accum f (string-&gt;list str) lis)
      (map list->string l)))))

(print (split-with "abcdefghij" '(1 2 3 4)))

これはちょっと説明をしておく。split-with の中で let を使って手続き f を定義している。これは、リストの各要素に適用される手続きで、2つの引数をとって 2つの値を返す。多値ってやつだな。覚えてるぞ。values で2つの値を返せばいい。1つ目は map の様に集められて、もう１つは次の適用の引数になる。で、map-accum 自体も2つの値を返す。1つ目は f の１つ目の返り値を集めたリストで、もう１つは最後の適用の２つ目の返り値だ。値が２つ返ってくるので、receive を使って l と s で受けている。s の方は使ってないけどね。最後に、l は文字のリストのリストになているので、文字列のリストに変換して完了。

takatoh@nightschool $ gosh split-with3.scm
(a bc def ghij)

実行時間の比較

せっかくなので比較してみた。

takatoh@nightschool $ time gosh split-with.scm
(a bc def ghij)

real	0m0.012s
user	0m0.011s
sys	0m0.000s
takatoh@nightschool $ time gosh split-with2.scm
(a bc def ghij)

real	0m0.015s
user	0m0.009s
sys	0m0.005s
takatoh@nightschool $ time gosh split-with3.scm
(a bc def ghij)

real	0m0.023s
user	0m0.023s
sys	0m0.000s

再帰版と末尾再帰版はあんまり変わらないけど、map-accum 版は明らかに遅い。そういうもんか。

不完全文字列

昨日の 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")

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

Max Range Sum

昨日に引き続き 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

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

たぶんあってる。