Haskell Quiz No.3

難易度: λ

propIsDigit テストをパスするように Digit 型の Arbitrary インスタンスを定義してみましょう。

テストは以下のように実行します。

上記のように OK になれば (たぶん) 正解です!

ヒント: 生成される値をデバッグしたい場合は sample' 関数が便利です。

答えは次回

はじめに

前回の問題と答えは以下の通りです。

問題

難易度: λλ

上記の2つの式の挙動の違いを説明してください。

また、なぜそうなるのか考えてみましょう!

こたえ

ということで foldr は無限リストに対しても停止して値を返しますが、foldl は停止せず、値を返さない。

でした。

Haskell Quiz No.2 の解説

Haskell は遅延評価なので foldr が無限リストを扱えるということは、知っておいて欲しいです。

また実際のアプリケーションではスペースリークの問題があるため foldr < foldl < foldl' の順で好まれるかもしません。(最適化されるから気にしなくても良いという話も聞いたことありますが、詳しくないので良くわかんないです。)

cycle

cycle 関数は base パッケージの GHC.List で定義されています。また Prelude モジュールにも含まれています。

以下は実際の定義です。

この定義を見ればわかるように cycle 関数は空リストを与えると実行時エラーになります。

それ以外の場合では与えられたリストを繰り返して無限リストを作ります。

Prelude モジュールについて

Prelude モジュールは良く使う基本的な関数や型の集まりです。とても良く使うので自動的に import されています。

Prelude で定義されている関数の 定義動作 は全部わかるようにしておきましょう。

これは本当に基礎知識です。(Haskell が苦手だなーと思う人はまずは Prelude で定義されている関数に慣れてください。それだけでも十分楽しめます。)

また、暗記して覚えることは非常に無駄なのでやめましょう。

何年か Haskell を使っていれば自然に覚えますし、感覚的には覚えている関数を書き下すのではなく、関数名 または 関数の動作 から実装を導いている感じです。

Foldable

Foldable 型クラスは base パッケージの Data.Foldable で定義されています。また Prelude モジュールにも含まれています。

昔の foldr はリストに対してのみ適用可能な関数でしたが、比較的最近 Foldable クラスのメソッドになりました。そのため、リスト以外でも利用できます。

Foldable のクラス定義とリストのインスタンス定義はこんな感じです。(実際にはもっと多くのメソッドがあります)

初学者に優しくない世界になりましたね・・・。なかなか定義にたどり着きません。

import 宣言のあたりを見ると import qualified GHC.List as List とあるので List.foldrGHC.List.foldr だとわかります。

GHC.Listbase パッケージの一覧から探しても見つかりません。これはわざと利用者に見えないようにしているためです。

実際に GHC.List は存在しますが {-# OPTIONS_HADDOCK hide #-} プラグマによって隠されているのです。

GHC.List を探してもリストの foldr の定義は見つかりません。どうやら GHC.Base で定義しているようです。

foldr

foldr の実際の定義は以下の通りです。

これではわかりずらいので少し変形してみましょう。

変数名もいつもの感じに変えちゃいましょう。

だいぶ見慣れた形に近づいてきました。

foldr (foldl) はほどよく抽象化されているので、色々な理解があると思いますので、僕がいつも使っている説明をいくつかご紹介します。

ここからの foldr, foldl は全てリストについての話です。

直感的な説明

例えば foldr (+) 0 [1,2,3,4,5] は以下のように考えることができます。

簡単ですね!この考え方をすれば foldr の型を暗記する必要はありません。

foldr f e xs の型はこのように考えれば良いのです。

  • f :: a -> b -> ?。この時 ?ab か迷いそうですが、上の図で考えれば x5 `f` e の結果は x4 `f` の第二引数に再び適用されます。そのため f :: a -> b -> b でなければ型が合いません。
  • f の型がわかれば e の型は自然に b しか有りえません。
  • 当然 xsx1, x2, x3, ・・・ とリストの形式なので [a] しかありえません。
  • foldr の結果の型は最終的に x1 `f` ... となるので f :: a -> b -> b から b です。

以上により foldr :: (a -> b -> b) -> b -> [a] -> b が導かれました。

universal property を使った説明

普遍性 (universal property) の詳しいことは有識者の方に任せるとして

上記のような再帰パターンの関数は全て foldr f e として書けるという性質です。この説明はどちらかと言うと、ベタに再帰で書いた関数を foldr を使った形式に書き直す際の理解の手助けとして有用かと思います。

具体例を見ればすぐにわかります。

sum 関数は foldr (+) 0 と同じです。(この時の e0, f(+) に対応します)

では先程の cycle は普遍性を使って foldr で書けるの?という疑問になりますよね。

先程のパターンと微妙に違うので合わせてみましょう。

また xs' = cycle xs なので以下のように変形できます。

さらに変形します。

ここで、最初のパターンと比較しやすいように cyclemyFunc という名前に変更します。

ついでに ++ の位置も変更しておきます。

どうですか、微妙に違いますよね。

xxs に分解しなければいけないのにどちらも (x:xs) になってしまっています。

ということで foldr を使った cycle の定義を普遍性を使って導出することはできません。

cycle 関数を foldr を使って定義する

普遍性を使った方法では cycle を導出することができませんでした。

けど、本当に foldr を使って定義することはできないのでしょうか? (参考: [Haskell-beginners] folds again – myCycle)

僕はいつもこのような感じで foldr の定義を考えます。acc は蓄積変数 (accumulate variable) の略です。

go の第二引数は常に foldr で畳み込んだ結果として考えることができます。

少し考えると xsxs ++ xs ++ xs ... という形式にできれば良さそうです。

無限リストになるため初期値 e は絶対に評価されません。そのため [] でも xs でも undefined でも好きな値が使えそうです。ここでは何となく xs にしておきます。

次に go 関数ですが xs ++ (xs ++ (xs ++ (...))) となれば良いので、 go x acc = xs ++ acc です。

gocycle の引数 xs を参照している点が通常の使い方と異なる点です。

ここが一番のポイントですが foldr に与えるリストは xs ではありません。

無限リストを生成するために適当な無限リストを与えます。

つまりこのような感じです。

0 `go` (1 `go` (2 `go` (3 `go` ...)))
xs ++ (1 `go` (2 `go` (3 `go` ...)))
xs ++ (xs ++ (2 `go` (3 `go` ...)))
xs ++ (xs ++ (xs ++ (3 `go` ...)))
xs ++ (xs ++ (xs ++ (xs ++ ...)))

これは完全に cycle ですね!

こんな感じで頑張れば foldr を使って cycle を定義することができます。

ただ、本質的には unfoldr を使うべき問題だと思います!(そのうちクイズにします)

遅延評価を追ってみよう!

やっと問題の本題です・・・。

foldr, cycle, (&&) の定義は以下を使います。

それでは実際に遅延評価で簡約していきましょう。

foldr (&&) True (cycle [True, False])
  = { cycle を適用 }
foldr (&&) True ([True, False] ++ cycle [True, False])
  = { foldr を適用 }
True && foldr (&&) True ([False] ++ cycle [True, False])
  = { (&&) を適用 }
foldr (&&) True ([False] ++ cycle [True, False])
  = { fodlr を適用 }
False && foldr (&&) True (cycle [True, False])
  = { (&&) を適用 }
False

つまり、(&&) の定義に秘密があったのです。

(&&) 第一引数が False であれば第二引数を評価することなく False を返します。そのため False && _ = False のような定義になっています。(このような関数を非正格関数 (non-strict function) と言います。定義は f undefined = undefined であれば正格関数 (strict function) です。(&&) は第一引数に関しては正格ですが、第二引数に関しては非正格です)

これが foldr の場合に計算が停止する理由です。

ではなぜ foldl の場合は停止しないのでしょうか?

foldl の場合も同様に簡約してみましょう。

foldl (&&) True (cycle [True, False])
  = { cycle を適用 }
foldl (&&) True ([True, False] ++ cycle [True, False])
  = { foldl を適用 }
foldl (&&) (True && True) ([False] ++ cycle [True, False])
  = { foldl を適用 }
foldl (&&) ((True && True) && False) (cycle [True, False])
  = ...

ということで foldl はリストの最後にたどり着くまで値を返せないのです。

そのため、無限リストを処理しようとすると停止しなくなります。

まとめ

いつも解説が長くなってしまいます・・・。

fold の融合則とかめちゃめちゃ好きなのでいつかまとめたいですね。

また、fold が好きな人には foldl パッケージがオススメです。

以上です。