WHAT'S NEW
CONTENTS
お気楽 Haskell プログラミング入門
CONTENTS
●初級編
- 2021/01/07 Haskell の基礎知識
使ってみよう、整数と実数、算術演算子、文字と文字列、比較演算子、論理演算子、条件分岐、変数、タプル (tuple)、リスト (list)、関数、局所変数と大域変数、型と型クラス、問題
- 2021/01/07 再帰定義
再帰定義の基本、再帰定義のポイント、フィボナッチ関数、ユークリッドの互除法、組み合わせの数、累乗の計算、累乗の高速化、let 式による局所変数の定義、レイアウト、where 節による局所変数の定義、再帰定義によるリスト操作、多相型関数、リストの連結、リストの反転、リストの探索、問題
- 2021/01/07 パターンマッチングとガード
定数と変数はパターンになる、ガード (guard)、リストのパターン、case 式、挿入ソート、クイックソート、クイックソートの弱点、問題
- 2021/01/07 高階関数
関数を引数にとる関数、ラムダ式、カリー化関数、リストの生成、セクション、問題
- 2021/01/10 高階関数 (2)
マッピング、フィルター、畳み込み、畳み込みの使用例、リスト内包表記、問題
- 2021/01/10 レキシカルスコープとクロージャ
レキシカルスコープ、レキシカルスコープと局所関数、クロージャ、連想リスト、関数適用演算子 $、関数の合成、問題
- 2021/01/11 遅延評価
Haskell の遅延評価、たらいまわし関数、末尾再帰、フィボナッチ関数の高速化、末尾再帰と正格評価
- 2021/01/11 遅延ストリーム
整数列の生成、フィボナッチ数列の生成、遅延ストリームの連結、高階関数、組 (pair) を生成する遅延ストリーム、集合演算、ハミングの問題、素数列の生成、エラトステネスの篩
- 2021/01/17 データ型の定義
data 宣言、型式の指定、パターンマッチング、型変数の使い方、再帰的なデータ型、連想リスト、レコードの定義、レコードの生成、レコードのパターンマッチング、多相的なレコード、インスタンスの設定、型クラス Eq の場合、型クラス Ord の場合、問題
- 2021/01/17 モジュール
モジュールの使い方、モジュールの作り方、スタックとは？、スタックの実装、キューとは？、キューの実装、問題
- 2021/01/17 簡単な入出力
標準入出力、do 構文、do の中で let を使う、関数 main、I/O アクションとマップ関数
- 2021/01/17 二分探索木
木構造、二分木、二分木の実装、データの探索、最小値と最大値、データの挿入、データの削除、最小値と最大値の削除、データ削除のプログラム、二分木の巡回、二分木の畳み込み
- 2021/01/17 マージソート
リストのマージ、マージソートの実装、実行例、別解
- 2021/01/17 二分探索木 (2)
連想配列とは？、データ型の定義、データの挿入、データの探索、データの削除、データの変換、畳み込み、実行例１、Tree を使って TreeMap を実装する、type 宣言、データの探索、ファンクタ、実行例２、Tree, TreeMap の欠点、Data.Set の使い方、Data.Map の使い方
●中級編
- 2021/01/17 Functor
Functor とは？、自分で Functor を定義する、Either、Either も Functor になる、連想リストも Functor になる、関数も Functor になる、Functor の規則、Functor による関数の部分適用
- 2021/01/17 Applicative
Applicative とは？、<*> を複数回使用する、<$> と <*> の組み合わせ、ZipList、newtype、自分で Applicative を定義する、関数も Applicative になる、ZipList の定義、liftA2、Applicative の規則
- 2021/01/24 モノイド (Monoid)
モノイドとは？、型クラス Monoid の定義、リストのモノイド、加法と乗法のモノイド、真偽値のモノイド、Maybe のモノイド、型クラス Foldable、二分木の畳み込み
- 2021/01/24 整数の論理演算とビット操作
Data.Bits の関数、ビットが 1 の位置を求める、組み合わせの生成 (2)、プログラムの作成、組み合わせに番号をつける方法、組み合わせを番号に変換、番号を組み合わせに変換、ちょっと便利なビット操作、ビットが 1 の個数を求める
- 2021/01/24 モナド (1)
モナドとは？、演算子 >>= で関数を連結する、自分でモナドを定義する、モナドと do 構文、guard と MonadPlus、順列の生成、経路の探索、リストモナドと非決定性計算、論理パズル、データ型の定義、補助関数の作成、論理パズルの解法、モナドとパターンマッチング、リストモナドと reads
- 2021/01/24 モナド (2)
関数呼び出しの履歴を取る、Writer モナドの使い方、自分で Writer モナドを作る、関数もモナドになる、Reader モナド、自分で Reader モナドを作る、State モナド、get と put、自分で State モナドを作る、便利なモナディック関数、liftM、ap、join、filterM、foldM、モナドの規則
- 2021/01/31 ファイル入出力
標準入出力、ファイルのオープンとクローズ、ファイルの表示、ファイルの書き込み、withFile、コマンドライン引数の取得
- 2021/01/31 二分木と Lisp のリスト
Lisp のリスト、リストの表記法、二分木の表示、二分木の生成、二分木の比較、二分木の探索、二分木のマッピング、二分木の畳み込み、二分木の置換、二分木の高さ
- 2022/12/14 数で遊ぼう
多角数、ピタゴラス数、原始ピタゴラス数を求める、ピタゴラス数を求める、平方根、平方根の整数部を求める、めのこ平方、順列の番号付け、番号を順列に変換
●応用編
- 2021/08/08 ByteString
bytestring の種類、pack と unpack、遅延 bytestring と正格 bytestring、基本的な操作関数、bytestring によるファイル入出力、ファイルのコピー
- 2021/08/08 配列
配列の生成、配列の参照と更新、配列の操作関数、二分探索、IOArray の基本的な操作、IOArray の操作関数、エラトステネスの篩
- 2021/08/08 動的計画法
組み合わせの数、動的計画法による高速化、リストを使う方法、整数の分割、動的計画法による高速化、リストを使う方法、ナップザック問題、プログラムの作成、実行結果
- 2021/08/08 部分和問題
ナイーブな方法、深さ優先探索＋枝刈り、動的計画法による高速化、Data.Set を使う方法
- 2021/08/08 書き換え可能な変数
IORef の使い方、配列によるスタックの実装、プログラムの作成、実行例、配列によるキューの実装、プログラムの作成、実行例
- 2021/08/08 ヒープ
配列によるヒープの実装、ヒープの構築 (1)、ヒープの再構築、ヒープの構築 (2)、優先度つき待ち行列、実行例
- 2021/08/08 ヒープ (2)
Leftist Heap とは？、Leftist Heap のマージ、プログラムの作成、実行例、Skew Heap とは？、Skew Heap のマージ、プログラムの作成、実行例、リストのソート、クイックソートの改良、クイックソートの改良 (2)
- 2021/08/08 配列のソート (1)
boxed と unboxed の違い、ソートの安定性、テストプログラム、バブルソート、バブルソートの改良、選択ソート、単純挿入ソート、シェルソート、コムソート
- 2021/08/08 配列のソート (2)
クイックソート、クイックソートの改良、ヒープソート、マージソート、マージソートの改良
- 2021/08/08 乱数
乱数とは？、擬似乱数の性質、乱数生成器、乱数の取得、大域乱数生成器から乱数を取得する、モンテカルロ法、乱数とクイックソート、線形合同法、線形合同法の欠点
- 2021/08/08 選択アルゴリズム
n 個のデータから k 番目に小さい値を求める、クイックセレクト、プログラムの作成、実行結果
- 2021/11/20 複素数
Haskell の数、無限大、負のゼロ、非数、Haskell の複素数、複素数の四則演算
- 2021/11/20 複素関数
指数関数、対数関数、三角関数、双曲線関数、平方根、逆三角関数、逆双曲線関数
●電卓プログラム編
- 2021/07/18 電卓プログラムの作成
プログラミング言語処理系の基本的な構造、文法の表現、式の構文、字句解析、構文解析、構文木の評価、式の入力と評価、実行例
- 2021/07/18 電卓プログラムの作成 (2)
変数の文法、組み込み関数の文法、変数と組み込み関数の定義、字句解析、構文解析、構文木の評価、式の入力と評価、実行例
- 2021/07/25 モナド変換子
モナド変換子とは？、モナド変換子 MabeT、Functor の定義、lift 関数、MonadPlus の定義、MaybeT の簡単な例題、ExceptT と MoandError、ExceptT の Functor, lift, MonadPlus、ExceptT の簡単な例題、Identity モナド
- 2021/07/25 モナド変換子 (2)
WriterT の使い方、WriterT の定義、WriterT の Functor、WriterT の lift 関数と MonadPlus、WriterT の簡単な例題、
ReaderT の使い方、ReaderT の定義、ReaderT の Functor、ReaderT の lift 関数と MonadPlus、ReaderT の簡単な例題、
StateT の使い方、StateT の定義、StateT の Functor、StateT の lift 関数と MonadPlus、StateT の簡単な例題
- 2021/07/25 電卓プログラムの作成 (3)
State モナドと Either モナドを合成する、データ型の定義、組み込み関数の修正、Calc の操作関数、因子の処理、項と式１の処理、式の処理、構文木の評価、式の入力と評価、簡単な実行例
- 2021/07/25 電卓プログラムの作成 (4)
モナディック・パーサ、パーサのデータ型、基本的なパーサ、選択、繰り返し、整数とマッチするパーサ、数式の計算、エラー処理の追加
●micro Scheme 編
- 2021/08/01 Haskell で作る micro Scheme
Scheme の S 式とは？、クォート (quote)、条件分岐、ラムダ式、可変個引数、最小の Scheme、S 式のデータ型、ドットリスト、S 式の表示、S 式の読み込み
- 2021/08/01 Haskell で作る micro Scheme (2)
関数の定義、S 式の評価、関数適用、等値の判定、シンタックス形式、リストの操作、REPL の作成、簡単な実行例、レキシカルスコープとクロージャの動作、再帰定義とリスト操作
- 2021/08/01 Haskell で作る micro Scheme (3)
Haskell のハッシュ表、環境の修正、S 式の評価、set! の実装、算術演算、比較演算、簡単な実行例、末尾再帰最適化、正格性フラグ
- 2021/08/01 Haskell で作る micro Scheme (4)
伝統的なマクロ、バッククォート、マクロとコンパイラの関係、マクロの定義、記号の変換処理、マクロの評価、高階関数 apply の作成、エラーの送出、ファイルの読み込み、簡単な実行例
- 2021/08/01 Haskell で作る micro Scheme (5)
バッククォートの動作、バッククォートの処理、簡単な実行例、ライブラリの作成、制御構造の実装、let と let*、and と or、letrec、begin、cond、case、do
- 2021/08/01 継続渡しスタイル
継続とは？、継続渡しスタイル (CPS) とは？、継続のデータ型、継続の連鎖、再帰呼び出しと継続渡しスタイル、二重再帰と継続渡しスタイル、CPS の便利な使い方、ツリーマッチング、遅延リストを使わない方法、継続モナド、callCC、大域脱出、再帰呼び出しからの脱出、モナド変換子 ContT、callCC と lift
- 2021/08/01 Haskell で作る micro Scheme (6)
継続の使い方、継続を表すデータ型の定義、S 式の評価の修正、シンタックス形式の修正、関数適用の修正、REPL の修正、簡単な実行例、大域脱出、繰り返しからの脱出、再帰呼び出しからの脱出、イテレータの生成
- 2021/08/01 Haskell で作る micro Scheme (7)
非決定性とは？、amb の動作、ライブラリ (lib.scm) の更新、関数版 amb の作成、解をすべて求める、論理パズル、マクロ版 amb の作成、地図の配色問題
●パズルの解法
- 2021/01/24 順列と組み合わせ
順列の生成、要素の選択 (select)、プログラムの作成、select を使わない方法、リストから n 個の要素を選ぶ場合、組み合わせの生成、問題
- 2021/01/24 パズルの解法 (1)
覆面算、8 クイーン、プログラムの作成、実行結果、8 クイーンの高速化、マスターマインド、推測アルゴリズム、プログラムの作成、何回で当たるか
- 2021/01/24 パズルの解法 (2)
小町算、プログラムの作成、数字の連結、演算子の挿入、式の計算、実行結果、大町算、プログラムの作成、実行結果
- 2021/01/24 経路の探索
グラフの表現方法、深さ優先探索の動作、プログラムの作成、再帰呼び出しによる実装、幅優先探索、経路の管理、プログラムの作成
- 2021/01/24 経路の探索 (2)
反復深化、反復深化のプログラム、探索の一般化
- 2021/01/24 パズルの解法 (3)
水差し問題、プログラムの作成、実行結果、数字の並べ替え、プログラムの作成、実行結果、嫉妬深い夫の問題、プログラムの作成、リストの集合演算、ボートに乗る組み合わせ、新しい局面の生成、幅優先探索による解法、実行結果
- 2021/01/31 パズルの解法 (4)
スライドパズル (8 パズル) の説明、プログラムの作成、データ型の定義、新しい局面の生成、幅優先探索による解法、実行結果、Data.IntMap を使う、最長手数の求め方、双方向探索による高速化
- 2021/01/31 パズルの解法 (5)
ペグ・ソリテア、Hoppers、跳び先表とペグの移動、新しい盤面の生成、移動手順の表示、反復深化による Hoppers の解法、実行結果、反復深化による 8 パズルの解法、実行結果、下限値枝刈り法、下限値枝刈り法のプログラム、実行結果
- 2021/01/31 パズルの解法 (6)
ナンプレとは？、単純なバックトラックによる解法、実行例、データ構造を工夫する、盤面とフラグの定義、フラグの操作、バックトラックによる解法、実行例 (2)、確定サーチ、おける数字がひとつしかないマスを探す、縦横枠で置くことができる数字を探す、実行例 (3)
●線形代数編
はじめに
Haskell は「遅延評価」を採用した純粋な関数型プログラミング言語です。一般に、副作用のない関数型言語を「純関数型言語」といいます。ML 系の言語 (Standard ML や OCaml) も関数型言語ですが、変数の破壊的代入や入出力処理などの副作用を許しているため、純関数型言語とはいえません。Haskell の場合、副作用がある処理は「IO モナド (IO Monad)」によって分離 (隔離) されているので、それ以外の処理は数学の関数 (数式) のようにプログラミングすることができます。
M.Hiroi は Haskell でプログラミングするのは初めてです。Haskell の特徴である「遅延評価」と「モナド」を使いこなすことができるように、簡単なプログラムを作りながら Haskell を勉強していきたいと思っております。まあ、初心者が作るプログラムなので、Haskell らしい綺麗なプログラムは書けないと思います。間違いやお気づきの点がありましたらご指摘いただけると助かります。たいしたことはできませんが、よろしければお付き合いくださいませ。
●ダウンロード
Haskell には複数の処理系がありますが、本ページでは GHC (Glasgow Haskell Compiler) を使うことにします。GHC は次のサイトからダウンロードできます。Windows 用のバイナリが用意されているので、簡単にインストールすることができます。
このほかにも Haskell をインストールする方法はいくつかありますが、ここでは Haskell のビルドツール Stack を使う方法を紹介しましょう。
Unix 系 OS の場合、本家 Web サイトに記載されているように、curl または wget を使って簡単にインストールすることができます。Windows 10 の場合、インストーラーが用意されているので、下記 Web サイトからダウンロードして実行するだけです。
あとはシェルで次のコマンドを実行すると GHC がインストールされます。
$ stack setup
GHC のインストールにはけっこう時間がかかるので注意してください。M.Hiroi は Ubunts 18.04 (WSL) にインストールしました。次のコマンドで Stack と GHC のバージョンを表示することができます。
$ stack --version
Version 2.5.1, Git revision d6ab861544918185236cf826cb2028abb266d6d5 x86_64 hpack-0.33.0
$ stack ghc -- --version
The Glorious Glasgow Haskell Compilation System, version 8.8.4
Stack 経由で GHC を起動する場合、GHC に渡すオプションは -- の後ろに記述してください。-- の前に記述したオプションは Stack に渡されます。
●プログラムの実行
GHC はコンパイラ (ghc) とインタプリタ (ghci) があります。また、Haskell をスクリプト言語のように実行するためのコマンド runghc も用意されています。たとえば、シェルで ghci を起動すると、メッセージとプロンプト Prelude> が表示されます。Stack を使ってインストールした場合、プロジェクトを作らずに ghci を起動するときは stack exec ghci と入力してください。この状態で Haskell のプログラムを入力して簡単に実行することができます。終了する場合はコマンド :quit (または :q) か CTRL-D を入力してください。
$ stack exec ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/ :? for help
Prelude> 1 + 2 * 3
7
Prelude> :q
Leaving GHCi.
$
Stack でプロジェクトを作成し、そこで ghci を起動するときは stack ghci とします。そのプロジェクトの設定ファイルに合わせた ghci が起動されます。プロジェクトを作らない場合でも stack ghci で起動できますが、最初に注意書き (Note) が表示されます。
●簡単なベンチマーク
GHC はプログラムをネイティブコードにコンパイルするので、バイトコードにコンパイルする処理系よりもプログラムを高速に実行することができます。その実行速度ですが、たらいまわし関数を使って調べてみました。
リスト : たらいまわし関数 (Haskell)
module Main (main) where
import Data.Time
tak :: Int -> Int -> Int -> Int
tak x y z =
if x <= y then z
else tak (tak (x - 1) y z) (tak (y - 1) z x) (tak (z - 1) x y)
-- 時間計測
main :: IO ()
main = do
x <- getCurrentTime
print (tak 22 11 0)
y <- getCurrentTime
print (diffUTCTime y x)
ファイル名を tak.hs とすると、シェル上で次のように入力すると実行ファイルを生成することができます。
$ ghc -O tak.hs
-O は最適化を指定するオプションです。Stack 経由で GHC を起動する場合は次のように入力します。
$ stack exec ghc -- -O tak.hs
exec を省略して stack ghc としてもコンパイルすることができます。
それでは実行結果を示します。tak 22 11 0 を計算しました。使用した GHC のバージョンは ver 8.8.4 です。
表 : tak 22 11 0 の結果
| 処理系 | 秒 |
|---|
| Python (ver 3.6.9) | 69.6 |
| Lua (ver 5.3.3) | 37.2 |
| Ruby (ver 2.5.1p57) | 25.4 |
| Gauche (ver 0.9.9) | 25.3 |
| ocamlc (ver 4.05.0) | 10.8 |
| SBCL (ver 1.4.5) | 6.38 |
| LuaJIT (var 2.1.0-β) | 4.02 |
| SML/NJ (ver 110.98) | 2.66 |
| Julia (ver 1.3.0) | 2.02 |
| GHC (ver 8.8.4) | 1.96 |
| SBCL (最適化) | 1.57 |
| GCC -O2 (ver 7.4.0) | 1.23 |
| ocamlopt (ver 4.05.0) | 0.97 |
- 実行環境 : Ubunts 18.04 (Windows Subsystem for Linux), Intel Core i5-6200U 2.30GHz
GHC は SML/NJ や SBCL よりも速い結果になりましたが、GCC や OCaml にはかないませんでした。それでも、GCC にせまる速度をたたき出しているのですから、GHC は優れたコンパイラ (処理系) だと思います。
なお、たらいまわし関数には tak のほかにも tarai という関数があります。
リスト : たらいまわし関数 (2)
tarai :: Int -> Int -> Int -> Int
tarai x y z =
if x <= y then y
else tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y)
関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、John Macarthy 先生によって作成されたそうです。
実をいうと、関数 tarai は「遅延評価」を行う処理系では高速に実行できることが知られています。実際に Haskell で tarai を実行すると、他の処理系とは比較にならないほど高速になります。興味のある方は試してみてください。
- Miran Lipovaca (著), 田中英行, 村主崇之 (共訳),『すごい Haskell たのしく学ぼう！』, オーム社, 2012
- Miran Lipovaca, 『Learn You a Haskell for Great Good!』(英語)
- Paul Hudak, John Peterson and Joseph Fasel (著), 山下伸夫 (訳), 『やさしい Haskell 入門 (バージョン98)』
- Sampou.Org
- 日本Haskellユーザーグループ - Haskell-jp
権利・免責事項など
Haskell Programming (お気楽 Haskell プログラミング入門を含む本ページ) の著作権は筆者「広井誠 (Makoto Hiroi)」が保持します。無断使用や無断転載は禁止いたします。Haskell Programming で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。
ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi)」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。
Copyright (C) 2013-2021 Makoto Hiroi
All rights reserved.