AtCoderでScheme入門

はじめまして

よこといいます。いろいろやってます。

この記事は最低限の前提知識として、みなさんに以下の3点を仮定します。ただし、3つ目は必ずしも必要ではありません。

• 義務教育修了程度の数学が理解できる(負の数や何の何乗とかがわかる)

• 曲がりなりにもプログラミングというものをやったことがある(変数の概念や整数の"2"と文字列の"2"は別物だということなどを知っている)

• AtCoderという競技プログラミングサイトで、適当な問題に対して好きな言語で何かしらのソースコードを提出し、判定を見る方法を知っている

これを超えた知識は必要に応じてこの記事で説明するつもりです。

さらに、この記事は次のような方に最適化されています。

• C++などのメジャーなプログラミング言語をメインで使っているが、毛色の違う他のプログラミング言語にも手を出すきっかけが欲しい

• みんなが使っているようなプログラミング言語は使いたくないので、そこまでメジャーではないが難しくもないプログラミング言語を探している

• とにかく暇であり、なんでも良いから読み物が欲しい

また、このような方には不向きです。

• 昨今の忙しい現代人

前提知識のハードルをかなり低くしているために、いくらか説明が冗長になっているからです。

この記事の一番にして唯一の目的は、書いている僕自身の知識の表現欲を満足することです。タイトルに騙されてこの記事で勉強しようなんて思わないでください。この記事をいくら読んでもSchemeあるいは関数型言語についての深い理解(ってなんですか)は何一つ得られません。なんといっても僕がほとんど使わないものに対しては、例えそれがSchemeというプログラミング言語を特徴付けるような重要な項目であっても、断りなく説明を飛ばしたりあっさり済ませたりしているくらいです。せいぜいAtCoderでACをもらうくらいで満足しているような人が暇つぶしに書いたユルい記事です。

さて、この記事でいうところのSchemeとは、2020年4月19日現在AtCoderの古い問題のジャッジシステムで採用されている処理系Gauche 0.9.3.3を指します。なお、AtCoderのジャッジシステムのアップデートにより、新しい問題ではより上位のバージョンGauche 0.9.9が利用できます。こちらの新しいバージョンでしか利用できない(と僕が確認した)が便利なライブラリもあるため、後述のリファレンスの後ろの方を調べてみてください。また、Racketなど他のScheme処理系での動作は保証しません。実際Gauche独自の拡張も存在しており、この記事ではそれについても特に断りなく紹介しています(この辺が何を言っているか分からない人は読み飛ばしてください)。

この記事を書くにあたって、以下のリファレンスを大いに参考にしました。みなさんもSchemeに慣れてきたらこのリファレンスを参照して勉強されることを強くお勧めします。

Gauche ユーザーリファレンス

また、以下の記事で紹介されているAtCoderの過去問題を記事中で何問か解いていますが、言語仕様の解説に的を絞った記事のため、問題文の読解や解法に至るまでの考察の道筋は省略しています。そういった内容はリンク先の記事にて十分に分かりやすく解説されています。

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～

もしあなたが先にあげた前提条件を満足しているのに記事中に理解できない箇所があった場合、それはあなたの理解力が足りないのではなく、僕の説明の仕方がまずいか、先の前提条件が緩すぎるかのいずれかです。また、記事中の説明に誤りや誤解を与えかねない箇所もあるかと思います。これらの疑問点や不備の指摘などありましたら、遠慮なくお申し付けください。時間と精神に余裕がある限り対応いたします。

Schemeの基本的な書き方

先ほどちらりと出てきましたが、Schemeは一種の関数型プログラミング言語です。僕は関数型プログラミング言語とは何かについて明確に説明できないため、そのあたりの解説を放棄します。分からなくてもSchemeは書けます。ただ、確かにこの言語はちょっと変わった書き方をします。

(+ 2 3)

これは何でしょう。よく分かりませんね。しかしGaucheはこれを解釈し、実行します。一組の丸括弧の中に、+と2と3が空白区切りで書かれています。+は後に続く数(引数と呼ばれます)を足す「手続き(関数、あるいは命令といっても良いかもしれません)」です。2は数字の$2$です。3も数字の$3$です。つまり、(+ 2 3)全体の意味は「数字の$2$と数字の$3$を足す」ということになります。よって、Gaucheがこれを解釈し実行すると、計算結果の$5$が得られます($5$が返ってくる、という言い方をします)。+が最初に書かれるのが重要なところで、これを(2 + 3)などとやってしまうとダメなわけです。というわけで、Schemeにおいてはあらゆる手続きが以下のような字句構造をとります。

(手続き名 何個かの引数)

いくつかの具体例を無節操に挙げていきます。

(- 7 5)
$7-5$を計算し、計算結果の$2$を返します。

(max -1 2)
$-1,2$のうち大きい方の$2$を返します。

(max -3 3 4)
同じmaxですが、引数が3つになっています($4$が返ります)。このように引数の個数を変えられる手続きもあります。

(print "Hello,World!")
おなじみHello Worldです。printは引数を標準出力に出力(表示)して最後に改行します。

(newline)
標準出力を改行します。このように引数を取らない手続きもあります。

(print (+ 2 3 5))
$2+3+5$の計算結果であるところの$10$が出力されます。Schemeではこのように手続き全体を括弧で括ってその返り値をより外側の別の手続きの引数とすることで、より高度な処理を実現することができます。

問題を解いてみる

ここからは、 AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ に載っているAtCoderの過去問題をいくつか選んで解きながら、Schemeの書き方や言語仕様について見ていきたいと思います。

第1問 ABC086-A Product

空白区切りで与えられる2つの整数の積が偶数なら"Even"、奇数なら"Odd"と出力する問題です。積に関しては、+や-と同じように*という手続きで計算することができます。"Even"や"Odd"の出力もprintを使って(print "Even")などとすればできそうです。では、入力や偶奇の判定はどのようにすればよいでしょうか。

1. 入力(標準入力)

AtCoderで僕が使う入力手続きは以下の3つだけです。

• read

引数を与えずに呼び出す(実行する)ことで、標準入力から数値などを読み取って返します。123や-4.5などのひとまとまりの値を読み込み、その後の空白や改行などは標準入力に残します。

• read-char

引数を与えずに呼び出すことで、標準入力から一文字読み取って文字として返します。こちらは空白や改行もそれぞれ一文字として読み込みます。

• read-line

引数を与えずに呼び出すことで、標準入力から一行まるごと読み取って文字列として返します。

2. 条件分岐

少し早い気もしますが条件分岐の特殊形式を紹介します。真理値について、真は#t、偽は#fと表されます。また、#fだけが偽とみなされ、#f以外の全ての値が真と見なされます。例えば、数値の0やnull文字も真であることに注意してください。余談ですがもちろん文字列の"偽"も真です。

• if

引数を3つ取ります。例を挙げて説明します。

(if (even? 2) "Even" "Odd")

手続きifが呼ばれると、まず1つ目の引数が計算されます。そしてその結果が真の値だったときは、2つ目の引数が計算されその結果が全体の計算結果として返ります。1つ目の引数の計算結果が偽の値だったときは、3つ目の引数が計算されその結果が全体の計算結果として返ります。この例では、1つ目の引数は(even? 2)、2つ目の引数は文字列の"Even"、3つ目の引数は文字列の"Odd"です。まず1つ目の引数についてですが、even?は引数として整数を1つとり、それが偶数だったら#tを、奇数だったら#fを返す手続きです。この例では2は偶数なので#tが返ります。したがって、全体では2つ目の引数の文字列"Even"がそのまま返ります。

• not,and,or

真理値を扱う手続きや特殊形式をここで紹介しておきます。notは引数を1つだけ取り、その真偽を反転して返します。andは引数をいくつか取り、それらが全て真だった場合のみ#tを、そうでなければ#fを返します。orも引数をいくつか取り、それらが全て偽だった場合のみ#fを、そうでなければ#tを返します。

これらを使えば、この問題は解けそうですね。どのような問題だったかおさらいすると、「空白区切りで与えられる2つの整数の積の偶奇を判定し、偶数ならば"Even"、奇数ならば"Odd"と出力する問題」でした。例えばこのように書いて解くことができます。

追記(2020/4/21)　kakiさんから、「Schemeの手続きの評価順序は不定である」とのご指摘を受けました(詳細はR7RS(pdf)の4.1.3節にあります)。したがって、下の解答例の(* (read) (read))は2つの(read)のどちらが先に評価されるか分かりません。* の結果が引数の順序に依存しないために今回は運良くこちらの意図通りの動作をしていますが、本来なら後から紹介するlet*を用いて(let* ((a (read))(b (read))) (* a b))などとすべきところでした。

ABC086-A

(print (if (even? (* (read) (read))) "Even" "Odd" ))

括弧が開いたり閉じたりしていて見にくいですね。一番内側からゆっくり見ていきましょう。一番内側だけを取り出すと、このようになっています。

(* (read) (read))

*は引数の積を計算して返す手続きでした。今回の引数は2つの(read)です。それぞれ標準入力から数値を読み取って返します。つまり、この部分は標準入力から2つの数値を読み取ってその積を計算しているわけです。では、もう一歩外側に出てみましょう。

(even? さっきの積)

偶数判定ですね。さっきの積が偶数なら#tが、奇数なら#fが返ります。もう一歩外に出ます。

(if さっきの真偽 "Even" "Odd")

条件分岐が登場しました。さっきの真偽が真(積が偶数)なら文字列"Even"が、偽(積が奇数)なら文字列"Odd"が返ります。そして一番外側に出ます。

(print さっきの文字列)

これでめでたく積が偶数なら"Even"、奇数なら"Odd"と出力されます。最後にもう一度コードを載せておきます。僕の個人的な趣味で色々変えて短くしておきました。41Byteです。

ABC086-A

(print(if(odd?(*(read)(read)))'Odd'Even))

even?があるならodd?もあり、こちらの方が1Byte短いです。空白は前後がつながって別物にならない限り必要ありません。OddやEvenはもはや文字列ではなく、OddやEvenそれ自身を表すリテラル式というものになっています。コード中の'Oddや'Evenはquoteという特殊形式の短縮表記になっており、短縮せずに書くと(quote Odd)や(quote Even)となります。シングルクォートを閉じる必要がないため、文字列にした場合よりも1Byteずつ短くなります。

3. 変数

次の問題に移る前に、変数の扱いについて説明しておきます。当然ですがSchemeも変数を扱うことができます。値の種類は何でもよく、数値だけでなく文字、文字列、真理値、手続き、後から登場するベクタやツリーマップまであらゆる種類の値を変数に持たせることができます。変数に持たせる値の種類を途中で変えても構いません。また、Awkのように変数の宣言が必要ないプログラミング言語もありますが、Schemeでいきなりaとかbとかを登場させるとエラーになります。変数を使う前に必ず「ここまでの有効範囲でこういう名前の変数をこの値で初期化して使いますよ」と宣言しておく必要があります。変数の有効範囲(コード中において使える範囲)には、「ローカルスコープ」と「グローバルスコープ」の2つの種類があります。

• ローカルスコープ

変数を宣言するための特定の手続きの括弧の中だけでその変数が使えます。

• グローバルスコープ

コード内(厳密にいうとモジュールと呼ばれる区画内)のどこでも使えます。

変数に値を持たせることについて、「(その変数をその値で)束縛する」という言い方をします。この言葉を使って、例えば「ローカルな束縛を作る」という言い方ができます。これは「ローカルスコープの変数を作る」という意味です。また、「ローカルな束縛がない状態」を「トップレベル」と呼びます。それではまずローカルな束縛を作る手続きから見ていきましょう。

• let

ローカルな束縛を作ります。最初の引数でローカルな変数を好きなだけ宣言し、それ以降にその変数を使った手続きを好きなだけ書くことができます。早速例を挙げます。

(let ((a 2) (b 3) (c 4)) (print (+ a b)) (print c))

最初の引数は((a 2) (b 3) (c 4))となっています。それぞれaを2で、bを3で、cを4でローカルに束縛します(順番は必ずしも書いた順とは限りません)。例のように個々の宣言を(変数名 初期値)という形式で書き、それら全体を(1つしか宣言していなくても)括弧で括ります。その後に、いつものように手続きを書いていきます。let全体の返り値ですが、引数の中で一番後ろにある手続きの返り値がそのまま返ります。

• let*

基本的な部分はletと同じです。letとの違いは、let*はローカルな束縛が書かれた順番通りに行われるという点です。そのため、パフォーマンスを気にしない限りはこちらのlet*を使った方がバグが発生しにくくなると思います。このlet*を使って、先ほどの問題はこのように書くこともできます。

(let* ((a (read)) (b (read)) (p (* a b))) (print (if (even? p) "Even" "Odd")))

次に、グローバルな束縛を作る特殊形式を見ていきます。

• define

トップレベル(ローカルな束縛がない環境)に書かれた場合、グローバルなスコープを持った変数を定義します。引数を2つ取り、2つ目の引数の計算結果が1つ目の引数の変数名に束縛されます。例えば(define a (read))とすると、標準入力から読み込んだ値でグローバル変数aが初期化されます。なお、aが既に定義されていた場合は、aの値が(read)の結果で書き換えられます。

変数に値を代入するときはどうすればよいでしょうか。defineし直すという手もありますが、defineは新しい束縛を作るときにだけ使うようにした方がバグを出さないという点で安全です。代入のための記述もちゃんとあります。

• set!

引数を2つとり、2つ目の引数の計算結果で1つ目の引数の変数が束縛され直します。つまり、2つ目の引数の計算結果で1つ目の引数の変数に代入されます。当然ですが、代入される変数にもともと入っていた値は捨てられます。このように、もともとあるデータが破壊的に変更される手続きの名前には「!」が付いています。このset!を使って、変数aの値を$1$増加させる操作を書くことができます。

(set! a (+ a 1))

(+ a 1)の計算結果がaに代入されています。ただ、C++を始めとする多くの言語でa++と簡潔に書けてしまうこの操作をするたびに、いちいち括弧を重ねてこのようなまどろっこしい書き方をしなければならないのでしょうか。そんなことはありません。

• inc!,dec!

引数に数値を持った変数を1つ取り、その値を$1$増加した値に書き換えます。値が書き換わるので、やはり「!」がついています。inc!を使うと先ほどの例は(inc! a)のように簡潔に書けます。また、省略可能な2つ目の引数に何らかの数値を与えると、増分が$1$ではなくその値になります。例えば(inc! a 10)とすればaの値に10が加算されます。dec!はinc!の減算バージョンです。

この辺りで「評価」という言葉を導入することにします。平たく言ってしまえば「プログラムが値を計算すること」です。例えば(+ 2 3)の評価結果は5です。変数aが数値2で束縛されている場合、aの評価結果は2です。これまでの部分で「計算」と呼んできたものは「評価」で言い換えられます。「計算」という言葉を使い続けても良いのですが、単に変数の値を読むだけといった「計算」というには無理がある処理も多く存在するので、これからは「評価」という言葉で統一します。

第2問 ABC-081-A Placing Marbles

$1$か$0$で構成された3文字の文字列が与えられるので、$1$の個数を数えて出力する問題です。文字列を数値として読み込んで、その$2$の$3$乗$=8$通りの値によって適切な値を出力するなどの解法も考えられます。今回は文字列の扱いを紹介したいという都合から、文字列の文字を1文字ずつチェックして$1$なら答えの変数の値を$1$増やし、最後にその値を出力するという方針でいきたいと思います。

4. 文字と文字列

他の多くのプログラミング言語同様、文字列はダブルクォーテーションで括って"yoko"というように書きます。そして文字列を構成する一文字一文字は、「文字」と呼ばれる文字列とは異なる種類のデータです。文字は#\yというように文字の前に#\をつけて書きます。スペースは#\spaceというように、一部の特殊な文字については特別な書き方が存在します。まずは文字についての手続きについて簡単に見ていきます。

• char=?

引数に与えられた文字が全て等しい場合のみ#tを、そうでなければ#fを返します。文字は3つ以上あっても良いです。even?もそうでしたが、真理値を返す手続きの名前には「?」が付くことが多いです。

• char->integer,integer->char

引数に文字を1つだけ受け取り、その文字コードを整数として返します。integer->charはこれと逆の手続きです。例えば、#\0の文字コードは49なので、(char->integer #\0)を評価すると49が、(integer->char 49)を評価すると#\0が返ります。これらのように、何らかのデータ変換を行う手続きの名前には「->」が使われます。

• digit->integer,integer->digit

引数に文字を1つだけ受け取り、その文字が数字であると解釈できるならばその数値を返します。そうでなければ#fが返ります。例えば、(digit->integer #\1)を評価すると数字の1が返ります。こちらも逆変換integer->digitが存在します。

文字についてよく使う手続きはこのくらいです。続いて文字列が絡む手続きを見ていきます。

• string=?

引数に与えられた文字列が全て等しい場合のみ#tを、そうでなければ#fを返します。文字列は3つ以上あっても良いです。

• string-length

引数に文字列を1つだけ取り、その文字数を返します。

• string-size

引数に文字列を1つだけ取り、そのメモリ上の大きさ(バイト数)を返します。AtCoderで扱う文字列はほぼ全て1文字1バイトのASCII文字なので、string-lengthと同じ振る舞いをします。こちらの方が2文字も短いので僕は専らこちらを使っていますが、全角文字を扱うようなときは注意する必要があります。

• x->string

他の種類のデータを文字列に強制的に変換したものを返す手続きです。例えば(x->string 123)は数値の123を文字列の"123"に変換して返します。引数に変数を与えた場合、その変数の内容自体は変更されず、あくまで返り値として変換された文字列が出てくるということに注意します(手続き名に「!」が付いていません)。

• string-ref

引数を2つ取ります。1つ目の引数は文字列($s$とします)、2つ目の引数は整数($i$とします)で、$0$から数えたときの$s$の$i$文字目の文字を返します。$i$は必ず$0$以上$s$の文字数未満の整数でなければなりません。例えば(string-ref "yoko" 2)は#\kを返しますが、(string-ref "yoko" 4)はエラーになります。このように連なったデータ構造のある位置の要素を返す手続きの名前には「ref」が使われます。また、ここから分かるようにSchemeは0-indexedです。

• string-set!

引数を3つ取ります。1つ目と2つ目はstring-refと同様です。3つ目の引数に文字($c$とします)を取り、$s$の$i$文字目を$c$で書き換えます。

• string-append

引数に文字列をいくつか取り、その文字列を現れた順に繋げてできる1つの文字列を返します。例えば、(string-append "tate" "yoko" "naname")は"tateyokonaname"が返ります。

• substing

引数に文字列$s$、整数$begin$、整数$end$を取り、$s$の$begin$文字目から$end$文字目の手前までの部分文字列を返します(0-indexedに注意)。また、$end$文字目は含まないことに気を付けます。例えば、(substring "tateyokonaname" 4 8)は"yoko"を返します。$begin$と$end$の範囲ですが、文字列$s$の文字数を$length$とすると$0 <= begin <= end <= length$かつ$begin < length$を満たしていなければなりません。なお、$begin = end$である場合は空文字列""が返ります。

それでは問題を解いてみましょう。問題をおさらいすると、「$1$か$0$で構成された3文字の文字列が与えられるので、$1$の個数を数えて出力する問題」でした。string-refやchar=?を使えばできそうですね。数えるところは$0$で初期化した変数に対してinc!を使うと良さそうです。今回はcountという名前の変数にしています。

ABC081-A

(define s (read-line))
(define count 0)
(if (char=? (string-ref s 0) #\1) (inc! count))
(if (char=? (string-ref s 1) #\1) (inc! count))
(if (char=? (string-ref s 2) #\1) (inc! count))
(print count)

コードが少し大がかりになってきましたが、長くなっただけで難しいことはやっていないのが分かると思います。手続きifの3つ目の引数が省略されていますが、3つ目の引数は省略可能です。ただし省略した場合は1つ目の引数の評価結果が#fだったときに手続き全体が未定義値を返すので注意する必要があります。未定義値とは、#<undef>と表記される無意味な値で、別にエラーではありません。今回は手続きifの返り値を利用していないため問題ありません。

この問題に正解するコードは、srfi-13と呼ばれる文字列ライブラリを利用すると48Byteで書くことができます。

ABC081-A

(use srfi-13)(print(string-count(read-line)#\1))

string-countという手続きで直接$1$の個数を数えて出力しています。

5. 数値の扱い

次の問題に入る前に、これまで+,-,*,even?くらいしか扱ってこなかった数値に関する手続きについて触れておきます。数値の中にも整数、有理数、実数、複素数の4つの種類があります。このうち整数と有理数は多倍長でメモリの許す限りの精度が扱えるため、オーバーフローを心配する必要がありません。

• zero?

引数に数値を1つだけ取り、それが$0$に等しければ#tを、そうでなければ#fを返します。

• =

引数に数値をいくつか取り、それらが全て等しければ#tを、そうでなければ#fを返します。

• <,<=,>,>=

引数に数値をいくつか取り、隣り合う引数同士でその不等号の関係が全箇所において成り立ったいれば#tを、1箇所でも成り立っていなければ#fを返します。

• max,min

引数に数値をいくつか取り、その中でmaxは最大、minは最小のものを返します。

• +,*

引数に数値をいくつか取り、その和や積を返します。

• -,/

引数に数値をいくつか取り($z1,z2,z3,...$とします)、$z1-z2-z3-...$や$z1/z2/z3/...$を返します。引数が2つの場合は普通の引き算と割り算です。ただし整数同士の割り算で割り切れない場合は、商の切り捨てではなく有理数になります。実数の割り算は実数になります。

• div

/と違って、割り切れない場合に小数部分を切り捨てた商を返します。引数の個数は2つでなければなりません。

• mod

引数に数値を2つ取り、1つ目を2つ目で割った余りを返します。

• expt

引数に数値を2つ取り、1つ目の2つ目乗を返します。実数でも大丈夫です。

• floor,ceiling,truncate

引数に数値を1つだけ取り、floorやceilingはその床関数(それを超えない最大の整数)や天井関数(それを下回らない最小の整数)を返します。truncateは整数部分を返します。すなわち、$0$以上の数に対してはfloor、負の数に対してはceilingと同じ振る舞いをします。

• abs,sqrt

引数に数値を1つだけ取り、絶対値や平方根を返します。

• gcd,lcm

引数に数値をいくつか取り、それらの最大公約数や最小公倍数を返します。

• inexact

引数に数値を1つ取り、整数や有理数を実数に変換します。AtCoderでは例えば正解が1.5のテストケースで3/2と出力すると不正解と見なされるので、この手続きを用いて有理数の3/2を実数の1.5に変換してから出力します。

第3問 ABC081-B Shift only

$N$と$A_1$から$A_N$までの値が与えられるので、$A_1$から$A_N$までの最大公約数が$2$で割り切れる回数を出力します。いちど最大公約数を求めるのは、紹介したばかりのgcdを使いたいためと、繰り返し処理が二重になるのを避けてコードを読み書きする負担を減らすためです。今回の新たな要素は「繰り返し処理」です。早速繰り返し処理について見ていきます。

6. 繰り返し

再帰関数を定義することによって関数型言語らしい繰り返しが書けますが、慣れないうちは考えるのが難しいうえに括弧の重なりが激しくなるので僕はこの書き方はしていません。他の言語と同じくらい手軽に繰り返しを記述できる便利なマクロが用意されているので、それらだけ紹介します。

• dotimes

決められた回数だけ処理を繰り返す、手軽な繰り返し処理です。最初の引数で繰り返す回数や、現在までに繰り返した回数に束縛されるローカルな変数を宣言します。それ以降の引数には、繰り返したい手続きを好きなだけ書き並べることができます。具体例を挙げてみます。

(dotimes (i 10) (print i))

最初の引数の中の1つ目の要素iに現在までに繰り返した回数が束縛されます。これはローカルな束縛であり、あらかじめiをdefineしておく必要はありません。2つ目の要素が繰り返す回数です。この例だときっちり$10$回繰り返します。つまりiには$0,1,2,3,...,8,9$が順に束縛されることになります。したがって、この手続き全体を評価すると$0$から$9$までの整数が順に改行区切りで出力されることになります。

• while

繰り返す回数があらかじめ分かっていないようなときはこちらのマクロを使用します。最初の引数で繰り返しの継続条件($check$とします)を与え、その後に繰り返したい処理($body$とします)を好きなだけ書き並べることができます。まず$check$が評価され、それが真の値を返せば$body$が順に評価されます。その後、再び$check$が評価され、それが真の値を返せばまた$body$が順に評価されます。$check$が真の値を返す限りこれが繰り返され、偽の値を返すとその時点で評価が打ち切られます。最初から$check$が偽の値を返した場合、$body$は一度も評価されないことになります。やはり例を挙げます。

(define n (read))
(while (< n 1000) (set! n (* n 2)))
(print n)

標準入力から整数を読み込んでnに束縛し、それが$1000$を超えるまで2倍し続け、最後にnを出力します。例えばnに$45$を入力で与えた場合、nは$90,180,360,720,...$と$2$倍ずつされていき、$1440$になったところで$1000$を超えたため繰り返しが打ち切られます。そして最後にその$1440$が出力されます。

それでは問題を解いてみましょう。問題をおさらいすると、「$N$と$A_1$から$A_N$までの値が与えられるので、$A_1$から$A_N$までの最大公約数が$2$で割り切れる回数を出力する問題」でした。紹介した2種類の繰り返し処理を使い分けて、このように書くことができます。

ABC081-B

(define n(read))
(define g(read))
(dotimes (i (- n 1)) (set! g (gcd g (read))))
(define count 0)
(while (even? g) (set! g (/ g 2)) (inc! count))
(print count)

最大公約数を格納する変数gについてですが、初期値を$1$や$0$にすると最大公約数が更新できないため、$A_1$の値で初期化しています。そのため前半の繰り返しの回数は$n-1$回としています。後半の繰り返しでは、gが偶数ではなくなるまで$2$で割ってはcountの値を増やし続けています。

この問題も色々するともっと短く書くことができます。85Byteですが、個人的にはもっと短い書き方がある気がしています。

ABC081-B

(use srfi-60)(let1 m 99(print(dotimes(i(read)m)(set! m(min(first-set-bit(read))m)))))

gcdも割り算もしていません。かわりに「$2$進数表記で$1$の位から連続する$0$の個数」の最小値を求めています。(use srfi-60)して使っているfirst-set-bitという手続きがそれです。$10$進数において「$10$で割り切れる回数」は「数字の末尾の$0$の個数」に等しいですね。これと同じように「$2$で割り切れる回数」は$2$進数における「数字の末尾の$0$の個数」に等しいです。first-set-bitは正にそれを求める手続きなのです。let1はローカル変数を1つしか宣言しないletを簡潔に書くためのもので、ここではmを99で初期化しています。dotimesの最初の引数に3つ目の要素がありますが、これを省略せずに書いた場合、ループ終了後にその要素が評価されて返されます。ここではmが評価されてdotimesの返り値となり、printによってただちに出力されます。

第6問 ABC088-B Card Game for Two

飛んで第6問です。第4,5問は新しい項目を解説しなくても解くことができるため飛ばしました。第6問は数列$a$の長さ$N$と各要素$a_1,a_2,a_3,...a_n$が入力で与えられるので、その数列を大きい順に並べ替えて奇数番目の要素の総和と偶数番目の要素の総和の差を出力する問題です。この問題を快適に解くためには、数列の各要素を順番に並べて保持する配列のようなデータ構造が必要になります。Schemeでは「リスト」や「ベクタ」がそれに当てはまります。配列もありますが、srfi-25というライブラリを使う必要があり、これは古い問題では使えません。リストとベクタだと個人的にベクタの方が扱いやすいと感じているので、ベクタだけを紹介します。また、値の並べ替えは「ソート」という操作を行うことで簡単に実現できます。これもその後で紹介します。

7. ベクタ

ベクトルという言葉を聞いたことがあるかもしれません。ベクタもベクトルも発音が違うだけで同じ言葉です。要するに値の陳列です。一次元配列です。矢印みたいな話は忘れます。ベクタそのものは#(1 2 3 4 5)というように括弧の組の前に#をつけて表記します。

• make-vector

引数を2つ取り、1つ目の引数の長さを持ち各要素が2つ目の引数の値で初期化されたベクタを作って返します。C++のstd::vectorと違って長さを後から変更することはできません。

• vector-ref

引数を2つ取ります。1つ目の引数はベクタ($v$とします)、2つ目の引数は整数($i$とします)で、$0$から数えたときの$v$の$i$番目の要素を返します。$i$は必ず$0$以上$v$の長さ未満の整数でなければなりません。

• vector-set!

引数を3つ取ります。1つ目と2つ目はvector-refと同様です。$v$の$i$番目の要素を3つ目の引数で書き換えます。

8. ソート

リストやベクタや文字列などの中身を、小さい順や大きい順に並び替える手続きです。

• sort,sort!

引数にリストやベクタや文字列などを1つとり、それを値の昇順に並べ替える手続きです。sortは元のリストなどを変更せずにソートされた新しいリストなどを返します。sort!は元のリストを直接弄ってその要素の順番を並べ替えます。省略可能な2つ目の引数に比較手続きを与えることで、並べ方を指定することができます。

これらの新機軸を取り入れて、第6問を解いてみましょう。問題をおさらいすると、「数列$a$の長さ$N$と各要素$a_1,a_2,a_3,...a_n$が入力で与えられるので、その数列を大きい順に並べ替えて奇数番目の要素の総和と偶数番目の要素の総和の差を出力する問題」でした。

ABC088-B

(define n (read))
(define a (make-vector n 0))
(dotimes (i n) (vector-set! a i (read)))
(sort! a >)
(define alice 0)
(define bob 0)
(dotimes (i n)
    (if (even? i)
        (inc! alice (vector-ref a i))
        (inc! bob (vector-ref a i))
    )
)
(print (- alice bob))

2行目で早速長さがnのベクタaを作成しています。3行目でそのベクタaに値を1つずつ読み込んでいます。このように、ベクタとdotimesは非常に相性が良いです。4行目でベクタaをソートしています。今回は降順にソートしたいので、2つ目の引数に>を与えます。その後のdotimesですが、iが偶数ならaliceに、奇数ならbobに得点を加算しています。iが$0$から束縛されることからターンの判定はeven?になることに注意します。やはりdotimesとベクタの相性は良いですね。

第7問 ABC085-B Kagami Mochi

数列$d$の長さ$N$と各要素が入力で与えられるので、異なる値の種類数を出力する問題です。ベクタに値を1つずつ読み取ってはその値が既に現れているかチェックしたり、逆に値ごとにそれが登場した回数を、値をインデックスとするベクタに記録して最後に1回以上出現した値の個数を数えたりといった方法が考えられます。しかしここでは、キーと呼ばれる標識が常にソートされた状態で要素を管理し、そのキーの重複を防ぐことができる「ツリーマップ」というデータ構造を紹介し、これを利用して解きます。体感ですがツリーマップの手続きはベクタなどと比べて処理が重いようで、使用するときは実行時間制限にある程度気を配る必要があります(もともとSchemeはそんなに遅い言語ではありません)。説明もちょっと重くなりますが、実は項目を立てて説明するような大きな内容はこれが最後です。よって紹介する問題もこれが最後になります。

9. ツリーマップ

ツリーマップはキーと値の「ペア」を保持するデータ構造です。ただ保持するだけではなく、キーの値によって同じものは省かれかつ常にソートされた状態で保持されます。そのため、キーが存在するかをチェックしたり、キーが最大/最小である要素を取り出したりといった、ベクタなどでは繰り返し処理でいちいち全ての要素を見て回らないとできないような操作を素早く行うことができます。この性質を利用して、工夫次第で様々な場面で使うことができます。

• make-tree-map

空のツリーマップを生成して返す手続きです。2つの引数を取り、1つ目の引数はキーを同一視する比較手続き、2つ目の引数はキーの順序を与える比較手続きです。例えば、整数をキーとするツリーマップなら(make-tree-map = <)、文字列をキーとするツリーマップなら(make-tree-map string=? stinrg<?)となります。

• tree-map-put!

引数を3つ取り($tm,key,val$とします)、ツリーマップ$tm$にキー$key$と値$val$のペアを挿入します。キーが既に存在していた場合、その値が新たな値で書き換えられます。

• tree-map-delete!

引数を2つ取り($tm,key$とします)、ツリーマップ$tm$からキー$key$を持つ要素を削除します。削除に成功すれば#tが、該当する要素が見つからなければ#fが返ります。

• tree-map-exists?

引数を2つ取り($tm,key$とします)、ツリーマップ$tm$にキー$key$を持つ要素が存在するか判定します。存在すれば#tが、存在しなければ#fが返ります。

• tree-map-get

引数を2つ取り($tm,key$とします)、ツリーマップ$tm$のキー$key$を持つ要素の対応する値を返します。キーが見つからなければ、省略可能な3つ目の引数が与えられていればそれが返り、省略されていなければエラーになります。余談ですが要素を挿入するときに(tree-map-put! tm key (+ (tree-map-get tm key 0) 1))としておけば、キーに対応する値はそのキーが挿入された回数となります。そしてその回数は(tree-map-get tm key 0)とすることで取り出すことができます。

• tree-map-num-entries

引数にツリーマップを1つだけ取り、その要素の個数を返します。

• tree-map-min,tree-map-max

引数にツリーマップを1つだけ取り、その最大あるいは最小のキーのキーと値のペアを返します。

• tree-map-pop-min!,tree-map-pop-max!

引数にツリーマップを1つだけ取り、その最大あるいは最小のキーのキーと値のペアが返すと同時にその要素を削除します。

• car,cdr

ペアの片方を取り出す手続きです。それぞれ引数にペアを1つだけ取ります。ツリーマップから取り出した要素に対して適用した場合、carがキーを、cdrが値を返します。

それではこのツリーマップを使って第7問を解いてみましょう。問題をおさらいしておくと、「数列$d$の長さ$N$と各要素が入力で与えられるので、異なる値の種類数を出力する問題」でした。

ABC085-B

(define n (read))
(define tm (make-tree-map = <))
(dotimes (i n) (tree-map-put! tm (read) 0))
(print (tree-map-num-entries tm))

最終問題のわりにかなりあっさりしています。2行目で整数をキーに持つ空のツリーマップtmを作成しています。3行目のdotimesで、毎回読み込んだ数列$d$の要素をキーとして、ツリーマップtmに挿入しています。この時点でキーすなわち数列$d$の要素の重複は取り除かれます。今回は値は使用しないので、適当に0としました。最後にツリーマップtmの要素の個数を出力します。

10. おまけ

ここでは、新たな項目を立てて説明するほどのことでもないが知っておくと便利な内容や、説明を簡素にするためにあえて飛ばしてきた内容を補足していきます。わざわざ紹介しているのは重要でよく使うからであり、おまけといいながらおまけではありません。この辺りまで押さえておけば、AtCoder Beginner ContestのA問題やB問題はほぼ全て解けるようになります。最近のやたら易しくなったC問題も無理なく解けます。僕の考察力が追い付いていないだけで、当然もっと上位の問題も解けるはずです。なお、冒頭でも述べたようにこの記事で紹介しているGaucheの仕様はほんの一部でしかありません。この記事の話が大体わかったら、ぜひリファレンスを当たってみてください。新たな発見や学びが必ずあります。

• when,unless

ifの片方だけを取り出したものです。最初の引数の評価結果がwhenなら真の値だった場合、unlessなら偽の値だった場合にその後に書き並べた手続きが評価されます。

• begin

引数に手続きを好きなだけ書き並べることができます。これらの手続きは1度ずつ順に実行され、最後に評価された手続きの返り値がそのまま返ります。ifで分岐したときに行いたい手続きが複数あるときは、このbeginでそれらを括ってやることで複数の手続きを1つの引数として与えることができます。

• exit

これが評価されるとただちにプログラムが終了します。whenと組み合わせて(when (コーナーケース) (print "No") (exit))という形でよく使います。

• display

引数を1つ取ってそれを標準出力に出力します。printと違って改行されないので、まだ改行したくないときはこちらを使います。なお、printは複数の引数を並べることができ、そうした場合引数を全て繋げて出力し最後に一度だけ改行されます。

• lambda,^

手続きを生成して返す特殊形式があります。それがこのlambdaです。^はその短縮表記です。1つ目の引数に生成する手続きの引数の一覧を、2つ目の引数に生成する手続きを記述します。例えば(^(x y) (* x y))とすると、2つの数値を引数に取ってその積を返す手続きを生成して返します。引数が1つしかない場合は、(^x (* x x))というようにもっと簡潔に書けます。

• define-inline

新しい手続きやvector-refのように使用頻度が高い割に名前が長い手続きの別名をトップレベルで定義するときは、defineではなくdefine-inlineを使うとよいです。define-inlineで手続きを定義した場合、コンパイルの時点でその手続きが出現する箇所が定義内容で置き換えられ、手続き呼び出しの時間ロスを防ぐことができます。よく使う手続きをどんどん登録していくとコーディングが快適になります。

• use

(use srfi-ライブラリ番号)とプログラムの最初に記述することで、そのライブラリの中の手続きなどが使えるようになります。どんなライブラリがあるかは、リファレンスを読んで頑張って探します。なお、古いバージョンだと使えないライブラリもあるので、AtCoderで提出する前にそのコンテストの「コードテスト」で一度動かしてみるとよいです。

• []

Gaucheでは現在のところ角括弧[]の組は丸括弧の組と同一視されています。したがって、これらを使い分けることでコードを読みやすくすることができるかも知れません。例えば、letなどの変数宣言のように「中身の一番左に来るものが手続きの名前でない場合は角括弧を使う」というルールを自分の中で決めておくと、(let* ([a 1][b 2][c 3])...)や(define-inline % (^[a b] (mod a b)))というように書くことになります。

• $

手続きの括弧が何重にも重なったときに便利な記法です。F,Gを手続きとすると、(F a b (G (H ...)))を($ F a b $ G $ H ...)というように一重の括弧で済ませることができます。

• ;

セミコロン;から行末まではコメントとして扱われます。コメントはプログラムと関係ないので好きなことを書けます。自己表現を楽しみましょう。

おわりに

ここまで読んでくださってありがとうございます。みなさんはSchemeという言語に対してどのような感想を持ったでしょうか。僕は「決して短くは書けないが、必要なことだけをシンプルに記述できるプログラミング言語」だと感じています。お察しの通り、僕はScheme以外の関数型プログラミング言語を書いたことがなく、Schemeに触れるまでは関数型プログラミング言語に対して「関数がいっぱい出てくる、よく分からないもの」くらいのイメージしか持っていませんでした(今も似たようなものですが)。しかしSchemeに触れてみたことで関数型プログラミング言語にもそこはかとなく興味が湧いてきたので、色々と手を出してみようかなと思っています。関数型に限らず、みなさんのおすすめのプログラミング言語があったら教えてください。

追記

記事の更新履歴などをここに追記します。()内は更新日と指摘してくださった方です。自分で気づいた誤字修正などは省略しています。

• 手続きではなく特殊形式やマクロであるものも手続きと紹介してしまっていたので修正しました。(2020/4/21, kakiさん)

• 第1問の解答例コードに欠陥があったため当該箇所に赤文字でその旨記しました。コード自体は偶然問題なく動作するものになっているので修正していませんが、修正箇所とその方法を追記してあります。(2020/4/21, kakiさん)