すごいHaskell本の演習問題を公開しました(5章まで)
最近、会社で「すごいHaskellたのしく学ぼう!
内容としては週1回、1時間かけて本を読み進めつつ、例を実際に動かしたり、分かりづらい部分を自分が補足したり、気になる部分をお互い教え合ったり、といった形で進めています。
前回主催した型システム入門の勉強会はあっという間に参加者が減って頓挫したものの、今回は8回目時点で参加者がほとんど減っておらず、よい感じに続いています。
ところで、すごいHaskell本は説明順序も適切ですし、例も豊富にある良い本なのですが、勉強会を進めて不満に思うことが出てきました。
それは、自分で考えて手を動かすための演習問題が一切ないという点です。
例が豊富にあるとはいえ、プログラミングの醍醐味は「どうやって解くかを考えて、それをプログラムに落としこむ」ところにあると自分は思っています。
また、そうやって問題を解くことで記憶も定着しますし、必要な知識が身についているかの理解度チェックにもなります。
そういうわけで、社内勉強会では章が終わるごとに演習問題を解いて理解を確認してもらう、ということを行っています。(宿題というわけではなく、任意で解きたい人だけ解いてもらうような感じです)
この演習問題、もともとは社内Githubにまとめていたのですが、社外から見れないと不便であることと、特に社外秘の情報というわけでもないことから、Githubに公開することにしました。
現在勉強会が5章までしか進んでいないので、5章分までの公開です。
すごいHaskell本を自習している方や勉強会をしている方、もしくは単にHaskellの問題を解いてみたい方など、ご自由に利用していただければと思います。
なお、問題作成にあたり自分で解けることは確認していますが、記述に間違いがあったり分かりづらい部分があるかもしれません。
そういった場合はメールかTwitterで@kokuyouwind宛てにリプライをいただければと思います。
問題を作るにあたり、なるべく作業的にならないよう、面白い題材を選んだつもりです。
以下では章ごとの問題について、どんな題材をテーマに何を狙って問題を作ったかの解説を書いていきたいと思います。
第1章 はじめの第一歩
第1章は、解説されているのが基本的な演算と、リストやタプルなどの基本的な派生型、そしてリスト内包表記くらいだったため、この時点では複雑な計算は行えません。
そこで第1章の演習問題では、幾何学を題材にすることにしました。
幾何学なら座標点を2-Tupleとして、図形を座標点のリストとして、自然に扱えるだろうという目論見です。
しかしながら、ユークリッド幾何学では当たり前の計算結果しか得られず面白みに欠けます。
また、点間の距離に実数演算が混ざってしまうため、この時点であまり意識させたくない数値型クラスの問題などにハマってしまう可能性があります。
整数演算だけに絞ればそのリスクを抑えられますし、整数だけを扱うほうがリスト内包表記との相性も良いでしょう。
そのあたりを勘案し、あえて馴染みの薄いであろうマンハッタン距離を採用したタクシー幾何学をテーマに据えました。
これなら整数座標点間の距離が必ず整数になるため扱いやすく、また一般的には知らない概念のため面白みもあるでしょう。
問題の構成としては、
- 1問目で距離感数を定義(基本的な関数定義とタプルの利用)
- 2問目で点の集合の作成(リスト内包表記のジェネレータ)
- 3問目で円の作成(リスト内包表記のフィルタ)
といった形で、タプルとリスト、そしてリスト内包表記を使うだけで解きやすいよう配置しました。
3問目を解ければ、マンハッタン距離の円がユークリッド距離での正方形になるという面白い結果が得られるようになっています。
第2章 型を信じろ!
第2章は、解説されていることが主に「型クラスとはどんなものか」であり、しかも自分で定義するのは第7章までお預けのため、勉強会でもちょっともやっとしたまま終わってしまいました。
このため演習問題を出すにしても、何を理解してもらうことを狙うかが微妙で、readやshowの使い方に関する問題を出しても仕方ないだろうと思い、第2章については演習問題を省略することにしました。
今にして思えば、数値型どうしの変換などについては少し問題を出しても良かったかもしれません。
第3章 関数の構文
第3章は基本的な再帰とパターンマッチなどの構文について触れられており、ようやくまともに関数を書けるようになってきます。
第3章の演習問題では、自然とパターンマッチやガードを用いることのできる題材としてフィボナッチ数列を考えましたが、定番すぎるため少し変化させたトリボナッチ数列を大問1に据えました。
大問2では、タプルのパターンマッチを利用してもらうため、2-タプルで表した有理数をテーマに、やや複雑な計算を問題としました。
特に2-3ではgcd関数を使って既約な形を作る必要があるため、ここでletやwhereなどの構文を使ってもらえるだろう、という狙いです。
第4章 Hello再帰!
第4章は再帰がテーマです。
第3章でも軽く再帰を用いる問題を出したのですが、第4章の演習問題ではより複雑な再帰を扱う問題を出しています。
大問1では基本的な再帰関数の問題を出していますが、1-3はリスト末尾まで読まず再帰の途中で打ち切る可能性のある関数、1-4では2つのリストのペアを返す関数を扱います。
大問2では挿入ソートをテーマに、「全体をソートする」という大きな問題から「ソート済みのものに1つの要素を挿入する」という小さな問題に分割する、という方針で問題を解いていきます。
大問3は少しチャレンジングですが、分割数をテーマに漸化式を導き出すよう誘導するヒントを出しています。
これらの問題を通じて、再帰関数を設計する上で必要となる「簡単な例で考える」「パターンを見つける」「小さな問題に分割する」といった定石を体感してもらうことを狙っています。
この辺りはポリアの「いかにして問題をとくか
また、急激に値が大きくなるテトレーションや、簡単な法則なのに一般式が非常に複雑になる分割数など、題材としても面白いと感じてもらえるだろうものを選んでいます。
第5章 高階関数
第5章は大変濃密で、
- 高階関数の定義
- 基本的な高階関数であるmap、filterなどの使い方
- 畳み込みの使い方
- 関数適用演算子と関数合成演算子の使い方
などが解説されています。
個人的には第5章がこの本の1つ目の山場だと考えており、ここで高階関数の扱い方に馴染めるかが今後の章の理解度に影響しそうな気がしています。
そういったことと、ちょうど年末年始を挟んで3週間ほど空いてしまうため、第5章の演習問題は少し多めに作ることにしました。
大問1が基本的な高階関数の定義と使い方で、特に1-1と1-2では値として関数を受け取ることに慣れてもらうことを狙っています。
大問2では畳み込みの操作に慣れてもらうことを狙っていますが、畳み込みでできることは再帰でも書けてしまうため注釈をつけています。
また、単純にsumやproductを問題にしてしまうといちいち「既存の関数を使わず」という注釈が必要になってしまうため、既存の関数を利用しては難しいだろう問題を設定しています。
特に2-2と2-3は少し頭をひねる必要があるものにしており、畳み込みの醍醐味を味わってもらえるのではないかと思います。
大問3では趣向を変えて、適用演算子と合成演算子に慣れてもらうことを目的にポイントフリー変換を出題しました。
パズル的な面白さを味わってもらうことを念頭に、だんだん複雑になるように問題を設定しています。
特に3-5は難解ですが、3-3と3-4を解くことで段階的に材料が揃うように配慮しています。
大問4では、高階関数自体が計算能力を持つことを体感してもらうため、ラムダ計算をテーマに取り上げました。
大問の中でも
- 4.1 チャーチ数
- 4.2チャーチ真理値
- 4-3 ラムダ計算と型付け
とセクションを区切り、演習を通してラムダ計算の考え方を知ってもらえるように構成しています。
なおチャーチ数の中でも前者関数predは非常に難しいため、ほとんど答えになるヒントを付記しています。
正直な所、大問4はテキストの内容を確認するというよりも、テキストの内容を使ってラムダ計算を学ぶことを目的にしています。
ラムダ計算は関数型言語の基盤となる理論のため、知っておくに越したことはないのですが、大学などでないと体系的に学ぶ機会がなく、また理論をなぞるだけでは退屈な気がするため、こうして演習に取り入れるのが一番定着させやすいのではないかと思います。
なお問題の補足にも書いたとおり、Haskellのラムダ式を使って型なしラムダ計算の体系を構築すると型の制約に引っかかってしまうため、第7章でデータ型を扱えるようになってから改めてラムダ計算の項をデータ型を使って表し、それを用いて不動点演算子と再帰を扱う予定です。
まとめ
以上、今回公開した問題を作る上で意図した部分などです。
問題を解く際には知らなくても良いことなのですが、知っておくと理解のヒントになるかもしれませんし、もし同じように問題を作っている人がいたら参考になれば、ということでまとめてみました。
今後、章が進んで問題を追加した際も同様に記事にまとめていこうかと思います。