Haskell Quiz No.2

難易度: λλ

foldr (&&) True $ cycle [True, False]
foldl (&&) True $ cycle [True, False]

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

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

答えは次回

はじめに

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

問題

module Foo where

data Foo1 = Foo1 Int
data Foo2 = Foo2 !Int
newtype Foo3 = Foo3 Int

x1 = case Foo1 undefined of
     Foo1 _ -> 1

x2 = case Foo2 undefined of
     Foo2 _ -> 1

x3 = case Foo3 undefined of
     Foo3 _ -> 1

y1 = case undefined of
     Foo1 _ -> 1

y2 = case undefined of
     Foo2 _ -> 1

y3 = case undefined of
     Foo3 _ -> 1

int :: Int
int = undefined

yInt = case int of
       _ -> 1

以下の値はそれぞれ何になるでしょう?

x1   = ???
x2   = ???
x3   = ???
y1   = ???
y2   = ???
y3   = ???
yInt = ???

答え

GHC のバージョン 8.0.2, 8.2.2, 8.4.1 で確認しました。

x1   = 1
x2   = undefined
x3   = 1
y1   = undefined
y2   = undefined
y3   = 1
yInt = 1

どうですか?自信を持って全部回答できた人は少ないのではないでしょうか。

ちなみに、この知識を披露するタイミングは・・・ほぼ無いでしょうね・・・。

よくある Haskell 雑学のうちの1つです。こういう内容はチームメンバーの誰かが理解していれば良いので、最初のうちはわからなくても大丈夫です。わかる人に解説してもらいましょう。

どうでも良い話

Haskell Quiz は Haskell と言いつつ GHC の話だったりする場合もありますが、実用上それが問題になることは無いので気にしないことにします。

Haskell は言語仕様で GHC が処理系だというのは、ただの雑学です。このことを知ってると、割とHaskellに詳しそうだな思ってもらえますよ!(ついでに GGlasgow の略でイギリスにある大学なんだよってことも伝えてあげると、バイトの学生とかは へー って顔をしてくれるのでオススメです!)

Haskell Quiz No.1 の解説

x1

data Foo1 = Foo1 Int

x1 = case Foo1 undefined of
  Foo1 _ -> 1

Foo1 はよくあるデータ定義です。

気にしておくべき点は以下の2つです。

  • Foo1 IntInt はまだ評価されていないサンクという状態です。
  • undefined は実際に評価された時にエラーとなります。(逆に、最後まで評価されなければエラーにならない)

Foo1 型の値で、例えば Foo1 (1+1)1+1 はまだ必要になっていないので、評価されていないサンクです。(つまり Foo1 2 ではありません)

本当かなぁ?と思う人は実際に以下のコードを実行すれば、何となくわかってもらえると思います。(sum [1..100000000000000] は評価された時にとても時間がかかる処理です)

ghci> Foo1 (sum [1..100000000000000])
Foo1 ^CInterrupted.

ghci> case Foo1 (sum [1..100000000000000]) of Foo1 i -> i
^CInterrupted.

ghci> case Foo1 (sum [1..100000000000000]) of Foo1 _ -> 0
0

ということで以下のコードは caseFoo1 とのパターンマッチは行われますが、 undefined は評価されない (する必要がない) ため 1 が返ってくることになります。

data Foo1 = Foo1 Int

x1 = case Foo1 undefined of
     Foo1 _ -> 1
x1 = 1

Haskell のアプリケーションがスペースリークしてしまう原因は、主にこのデータ構造のサンクが原因になっている場合が多いようです。

x2

data Foo2 = Foo2 !Int

x2 = case Foo2 undefined of
     Foo2 _ -> 1

このコードには見慣れない ! という記号が出てきました。

ここで抑えておくポイントは1つだけです。

  • ! はサンクを潰してくれる (評価する) マークです。つまり、値が使われない場合でも評価されるということです。(計算が無駄になる場合も当然ある)

以下の結果から、Foo2 の値を作る時には、必ず先に sum [1..100000000000000] が計算されていることがわかります。

ghci> Foo2 (sum [1..100000000000000])
^CInterrupted.

ghci> case Foo2 (sum [1..100000000000000]) of Foo2 i -> i
^CInterrupted.

ghci> case Foo2 (sum [1..100000000000000]) of Foo2 _ -> 0
^CInterrupted.

そのため、今回の結果は undefined になります。

data Foo2 = Foo2 !Int

x2 = case Foo2 undefined of
     Foo2 _ -> 1
x2 = undefined

専門家は undefined のことを bottom () というテクニカルタームで呼ぶこともありますが、普通の人は 停止しない計算エラー という意味だと思えば十分です。(たぶん)

x3

newtype Foo3 = Foo3 Int

x3 = case Foo3 undefined of
     Foo3 _ -> 1

ここで抑えておくポイントは2つです。

  • newtype のデータコンストラクタは型チェックが終わったら剥がされる
  • そのため newtype は実行時に余分なコストが発生しない

つまり、雰囲気はこんな感じです。

newtype Nat = Nat Int

-- 型チェック前
x = Nat 1

-- 型チェック後
x = 1

Haskell の学習でわけわかんないポイントの1つに type, newtype, data の違いがあると思います。(少なくとも僕は最初全然わかりませんでした)

僕と同じように学習で困っている人は、以下の表で考えれば理解の手助けになるかもしれません。

型 (type) 値 (value) 具体例
type X X type FilePath = String
newtype O X newtype Nat = Nat Int
data O O data Bool = True | False

X は既存の型や値を再利用する、O は型や値を新しく作るという意味です。

  • type は型も値も既存のものを再利用します。
  • newtype は型は新しく作りますが、値は既存のものを再利用します。
  • data は型も値も新しく作ります。

ということで、このように変形できます。

newtype Foo3 = Foo3 Int

-- 定義
x3 = case Foo3 undefined of
     Foo3 _ -> 1

-- newtype なので
x3 = case undefined of _ -> 1

-- 1 を返すために undefined を評価する必要が無いため
x3 = 1

y1

data Foo1 = Foo1 Int

y1 = case undefined of
     Foo1 _ -> 1

この場合は case 式で Foo1 _ のパターンマッチを行う際に undefined の評価をしなければならないため y1undefined になります。

y1 = undefined

y2

data Foo2 = Foo2 !Int

y2 = case undefined of
     Foo2 _ -> 1

この場合も y1 と同じケースです。やはり Foo1 のパターンマッチが発生するため undefined です。

y2 = undefined

y3

newtype Foo3 = Foo3 Int

y3 = case undefined of
     Foo3 _ -> 1

この結果が一番おもしろい気がしますが、これは 1 を返します。

今までの話から Foo3 は実行時には存在しないコンストラクタです。すなわち実行時にはこのような形式になります。

y3 = case undefined of
     _ -> 1

これは x3 の場合と同じですね。

y3 = 1

yInt

int :: Int
int = undefined

yInt = case int of
       _ -> 1

ここまで来たらこれはもう簡単ですよね!

yInt = 1

まとめ

解説がとても長くなってしまいました・・・。間違ってたらご報告ください。

以上です。