Haskell の sequence 関数 - foldr をイメージして

「Haskell の mapM_ – foldr と (>>) を意識して」のつづき

1. mapM_ 関数を理解するには、sequence 関数の理解が不可欠

前回は、

mapM_ 関数

の動作について見た。しかし、どうも感覚的に全然身に付いていない。

mapM_ を使おうとすると、

「あれ？一体これ何してるんだっけ」

と考え込んでしまう。返り値に関心のある mapM にしても同じ。

多分、この関数のベースとなっている

• sequence 関数

をちゃんと理解してないために、頭の中にイメージを描けないと思う。 (+_+)

Prelude には、

sequence :: Monad m => [m a] -> m [a]

   Evaluate each action in the sequence from left to right, and collect the results.

型を見れば、わかるように、sequence 関数は、Monad が関わってくる。

ところで、モナドな計算について理解しようとすると、途端に具体的なものが、遠のき霧の中に隠されてしまう感覚を抱く。詳細なことを、一々考えないで済むのが抽象化のメリット。しかし、モナドに関しては、詳細を考えないで済ませることができない。共通の構造として存在するものを理解し、抽出する方法を学ばなけれど、いつまで経ってもブラックボックスをいじっているという感覚から抜け出せない。

 

2. モナドのイメージ

「モナドとは何か」について様々な説明がされる。

例えば、

モナドは値およびその値を使う計算の並びという観点からいえば、計算を構造化 する方法です。

(All About Monads のIntroduction より)

これをはじめて読んだとき、何が言いたいのかサッパリわからなかった。

しかし、今理解している範囲で「モナドのイメージってどんな感じ？」と言われたら、やはり Monad クラスの (>>=) の説明を元に想像している。

Sequentially compose two actions, passing any value produced by the first as an argument to the second.

(Prelude より)

「アクション」と言われるとわかりずらいので、「計算」 と置き換えて読んでいる。つまり、

二つの計算をつなげるとき、先行する計算の結果を、後続の計算の引数とする。

頭の中のイメージは、

(>>=) による計算のつなげ方にはバリエーションがある。値を含む「包み」の種類によって計算の仕方が異なる。

例えば、以下のように、Maybe, [ ], State s の型コンストラクタが「包み」で、それぞれの型コンストラクタに応じて計算の方法が定義される。

Prelude の Moand の説明では、

it is best to think of a monad as an abstract datatype of actions.

モナドを、アクションの抽象データ型の一種だと考えておけばよいと。

モナドと言われた場合、このような大雑把なイメージを頭に浮かべている。イメージが浮かぶから、ある程度わかった気になるれる。数学嫌いの文系人間なのでこの程度の想像で「まぁよし」と。

 

3. foldr の動作イメージ

モナドな計算のイメージはできているとして、mapM 関数に話を戻す。この関数をイメージできない原因となっている sequence 関数。

Source を見ると以下のように定義されている。

sequence       :: Monad m => [m a] -> m [a] 
sequence ms = foldr k (return []) ms
            where
              k m m' = do { x <- m; xs <- m'; return (x:xs) }

これを見て、すぐに理解できるほど、foldr 関数に馴染んでないので、もう一度ここから考え直し。 (+_+)

ところで、foldr をイメージをするとき一番参考になったのは下図だった。

Fold (higher-order function) - Wikipedia, the free encyclopedia via kwout

リストの要素間に、関数を適用していく様子がイメージしやすい。

これを元に、具体的な場合に当てはめて考える。

 

リストの要素がモナドでない場合の foldr 関数の動作イメージ

まずは、リストの要素がモナドではない場合の概念的なイメージから。

例として次の場合。

foldr (+) 0 [1,2,3,4]

最初に、foldr の計算のためにツリーをイメージ。その後、対象であるリストの要素を木の左の葉に割り当てる。加えて、foldr の第 2 引数である 0 を木の一番下の右の葉へ。

次に、二項演算子 (+) を一番下の二つの葉に適用して 4 という結果を生成。これを木のルートの方へ繰り返し最終的な結果を得る。

 

sequence 関数における foldr の動作イメージ

sequence 関数の定義を再掲。

sequence       :: Monad m => [m a] -> m [a] 
sequence ms = foldr k (return []) ms
            where
              k m m' = do { x <- m; xs <- m'; return (x:xs) }

foldr が使われている行を見ると、k が二項演算子で、第 2 引数に、「空リストがモナドで包まれたもの」が与えられているのがわかる。これを先ほどと同じようにイメージする。

要素がモナドであるリストを、木の左の葉に割り当てる。次に、一番下の右の葉に、「モナドで包まれた空リスト」を置く。

次に 二項演算子 k を一番下の葉に適用。

関数 k の定義で、do 式を使わないなら、

括弧を明示的に付けるなら、

こうすると、関数が内側へ内側へとネストしつつ、 (>>=) で第 1 引数の計算の結果を第 2 引数の計算へと受渡している感じがつかみやすい。

最後の return に注目すると、左の葉のモナドな計算から結果を取り出し、それを右の葉のモナドな計算の結果から取り出したリストの先頭へ (:) を使って追加し、最後に return でまたモナドに包んで返しているのがわかる。

結局、大雑把に言って、sequence 関数は与えられたモナドのリストの個々の中身を取り出し、リストに追加したら、そのリストをまたモナドで包んで返すことを繰り返す。

 

4. 具体的な型で sequecne 関数を試す

Maybe  a

一番わかりやすい例は Maybe a 型のリストに sequence 関数を適用したとき。

*Main> sequence [Just 1, Just 2, Just 3, Just 4]
Just [1,2,3,4]

各々のJust で包まれた数値がリストにまとめられ、再び Just で包まれている。

 

[a]

リストの場合は、

*Main> sequence [[1,2],[3,4,5]]
[[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]

むむむ…(@_@; 複雑な結果になった。

先ほどの foldr のイメージを思い出しながら考えると、最初の計算は以下のようになる。

*Main> [3,4,5] >>= \x -> return [] >>= \xs -> return (x:xs)
[[3],[4],[5]]

次に、上記の結果を元にして、

*Main> [1,2] >>= \x -> [[3],[4],[5]] >>= \xs -> return (x:xs)
[[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]

 

 

State s a

State モナドの場合は、「初期値と増分を持つカウンター」を対象にして考える。

以下の next 関数はカウンターの値を増分だけ増やす関数。返される値のタプルの第 1 要素は next により値を更新する前の値であるとして定義。これを State モナドで包んでリストにし、それに対して sequence 関数を適用する。

import Control.Monad.State

data Counter = Counter { val, step :: Int } deriving Show

next :: Counter -> (Int, Counter)
next (Counter v s) = (v, Counter (v+s) s)

main = let s = sequence [State next, State next, State next]
       in print $ runState s $ Counter 0 1

結果は、

([0,1,2],Counter {val = 3, step = 1})

State モナドの場合、State s a 型なので、State s が包みで a が計算をつなげると次に渡される結果。よって、タプルの第 1 要素がリストに集められ、第 2 要素は State モナドがつなげられるごとに背後で カウンタの状態が更新されていく。

うーん、やはり sequence 関数の動作のイメージができても、個々のモナドの (>>=) による計算のつなぎ方もイメージできてないと難しいなぁ。。

 

関連記事

• Haskell の mapM_ – foldr と (>>) を意識して

Haskell の mapM_ – foldr と (>>) を意識して

1. mapM_ 関数は、どのように定義されているのか？

Haskell の print 関数で文字列を連続して出力させたい場合、次のように書く。

main = do print "hoge"
          print "piyo"
          print "fuga"

これを短かく書きたいなら、

main = mapM_ print ["hoge", "piyo", "fuga"]

最初、意味もわからず mapM_ の動作を覚えようとした。 ^^;

なぜこのように書けるのだろう？

 

2. map, fold 系の復習から

まずは map, fold 系の復習から。

map 関数は「各要素へ指定された関数 f を適用」する。

リストの要素を 2 倍するなら、

*Main> map (*2) [0..5]
[0,2,4,6,8,10]

これに対して、fold 系 の関数は大雑把なイメージとして、「各要素の間に二項演算子 f を挟んだ後全体の計算をする」。

リストの要素を足し合わせるには、

*Main> foldr (+) 0 [0..5]
15

リストの要素を 2 倍して、足し合わせるなら、関数合成を利用して、

*Main> foldr ((+).(*2)) 0 [0..5]
30

( cf. Haskell で関数合成 (2) )

 

3. map と foldr を使って、do 式を置き換える

最初の print 関数を 3 つ並べた例に戻る。

do 式 を使っていたので、これを Monad の (>>) で置き換えると、

main = print "hoge" >> print "piyo" >> print "fuga"

ところで、以下のリストに map 関数を適用した場合、

… map print ["hoge", "piyo", "fuga"]

次のリストが生成される。

[print “hoge”, print “piyo”, print “fuga”]

このリストの要素の間に二項演算子 (>>) を挿入すれば先ほどの形になる。

よって、foldr を使えば、

main = foldr1 (>>) $ map print ["hoge", "piyo", "fuga"]

と書ける。

 

4. sequence_ と mapM_ 関数

以下のリストの型は [IO ()] 。

[print “hoge”, print “piyo”, print “fuga”]

IO はモナドの一種。

()

は、モナドな計算をつなげたときに、「前の計算の結果が、続く計算に必要ない」ことを示すために使われる印である「ユニット」。

 

sequence

1. モナドな計算のリストを評価し、
2. 結果を一つのリストにまとめ、
3. モナドで包む関数

は sequence 。

sequence :: Monad m => [m a] -> m [a]

( cf. Haskell におけるモナドのサポート の直列化関数 )

返される値に関心がない場合は、末尾にアンダーバー付きの関数。

sequence_ :: Monad m => [m a] -> m ()

これを用いて、上記 foldr1 関数を使った定義を、次のように書換えることができる。

main = sequence_ $ map print ["hoge", "piyo", "fuga"]

1. 文字列のリストの各要素を print 関数で IO モナドで包み、
2. 各モナドな計算を評価し、
3. 結果を必要としない。

 

mapM

この sequence と map を使って定義してある関数が mapM 。

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

定義 を見ると、

mapM_ f as      =  sequence_ (map f as)

1. map 関数に、モナドで包む関数を渡し、
2. リストの各要素に適用した後、
3. sequence 関数で、一つにまとめモナドで包んでいる

返される値に関心がない場合は、

mapM_ :: Monad m => (a -> m b) -> [a] -> m ()

よって、最終的には、

main = mapM_ print ["hoge", "piyo", "fuga"]

と書ける。あ～、ややこしい。。 (+_+)

 

5. State モナドの場合も同様に考える

上記は、IO モナドにおける mapM_ の適用例だった。今度は、同じモナドの仲間である、State モナドで考えてみる。

毎度おなじみの Person 型を以下のように定義。

data Person = Person { name :: String
                     , age  :: Int
                     } deriving Show

次に、Person 型の値のリストを保持する Group 型を定義。

data Group = Group [Person] deriving Show

Group 型の値に Person 型の値を追加する addPerson 関数を定義する。

addPerson0              :: Person -> Group -> Group
addPerson0 p (Group ps) = Group (ps++[p])

この関数を State モナド で包みたい。型が s –> (a, s) となるように調整する。

addPerson              :: Person -> Group -> ((), Group)
addPerson p (Group ps) = ((), Group (ps++[p]))

( cf. Haskell の State モナド (1) - 状態を模倣する )

State モナドを使うためには、State モジュールをインポートすることが必要。

import Control.Monad.State

addPerson 関数を使い、あるグループの値に 「太郎、次郎、花子」 を追加する関数 addPs0 を定義してみる。

addPs0 = do State $ addPerson $ Person "Tarou"  10
            State $ addPerson $ Person "Jirou"  20
            State $ addPerson $ Person "Hanako" 30

人が空っぽのグループ型の値を予め定義しておき、

g = Group []

addPs0 関数を試してみる。State モナドに包まれた関数を取り出すのは、runState なので、

*Main> runState addPs0 g
((),Group [Person {name = "Tarou", age = 10},Person {name = "Jirou", age = 20},Person {name = "Hanako", age = 30}])

(cf. jutememo's gist: 333569 — Gist )

 

mapM_ 関数へ

addPs0 関数の中身が不恰好なので、共通部分を抽出する。

1. 「名前と年齢」のタプルを与えたら、
2. Person 型の値を生成し、
3. その値を addPerson 関数に与え、
4. State モナドで包む

addPs’ 関数を定義。

addPs' (n,a) = State $ addPerson $ Person n a

関数の型を確認すると、

addPs' :: (String, Int) -> State Group ()

先ほどの print 関数の型と比較すると、

print :: (Show a) => a -> IO ()

包むモナドの種類が違うけれど、どちらも mapM_ の第1引数に与えることができる型。

mapM_ :: (Monad m) => (a -> m b) -> [a] -> m ()

addPs' を用いると、先ほどの定義が少しすっきりする。

addPs0 = do addPs' ("Tarou",10)
            addPs' ("Jirou",20)
            addPs' ("Hanko",30)

do 式を使わないなら、

addPs0 = addPs' ("Tarou",10) >> addPs' ("Jirou",20) >> addPs' ("Hanko",30)

先ほどと同じく foldr で置き換えるなら、

addPs0 = foldr1 (>>) $ map addPs' [("Tarou",10), ("Jirou",20), ("Hanko",30)]

sequence 関数を使うと、

addPs0 = sequence $ map addPs' [("Tarou",10), ("Jirou",20), ("Hanko",30)]

先ほどの print 関数を、mapM_ に渡したのを思い出し、addPs1 関数を定義。

addPs1 = mapM_ addPs' [("Tarou",10), ("Jirou",20), ("Hanko",30)]

これですっきりした。 ^^  しかし、いきなりこれ見たら、さっぱりわがんね。。 (+_+)

試しに使ってみる。State モナドの計算の結果のうち、状態の変化のみに関心があるので、今度は runState ではなく execState を使う。

*Main> execState addPs1 g
Group [Person {name = "Tarou", age = 10},Person {name = "Jirou", age = 20},Person {name = "Hanko", age = 30}]

( cf. jutememo's gist: 333569 — Gist )

 

ファイルからデータを読み込む

上記では、Person 型の値をハードコードしていた。これを、ファイルからデータを読み込むように変更してみる。

ファイルには次のようにデータが書かれていたとする。

"Tarou",10
"Jirou",20
"Hanko",30

文字列から代数的データ型に変換するには read 関数を使えばよい。

• cf. Haskell の read 関数で文字列から代数的データ型へ変換

方法は、文字列から一度タプルにして読み込み、Person 型へと変換する。

文字列 → タプル → Person 型

文字列からタプルへと変換する関数は、

toTuple    :: String -> (String, Int)
toTuple cs = read line where line = '(' : cs ++ ")"

これを使うと、

main = do cs <- getContents
          print $ (execState $ mapM_ addPs' $ map toTuple $ lines cs) g

( cf. jutememo's gist: 333569 — Gist )

しかし、今はまだこれ見直しても何が書いてるかすぐにわからないなぁ。。 (@_@;

 

参考サイト

• Haskell におけるモナドのサポート

Haskell の返り値の型を指定する関数 - maxBound, minBound, (=~), return

1. 返り値が多相な関数は、返り値の型を指定する

Haskell には、返り値が多相な関数がある。

例えば、Prelude に定義されている Bounded のクラスメソッド。

class  Bounded a  where
    minBound, maxBound :: a

「型変数 a は、Bounded クラスのインスタンスである」という制約が、表現されている。

(cf. Haskell の数値 – Int は型で Num は型クラス)

GHCi で確認する。返り値の型を指定しないで、関数を呼び出すと、

*Main> maxBound

:1:0:
    Ambiguous type variable `a' in the constraint:
      `Bounded a' arising from a use of `maxBound' at :1:0-7
    Probable fix: add a type signature that fixes these type variable(s)

「曖昧な型だ」と警告がでる。

Bounded クラスのインスタンスを、maxBound の返り値の型として指定すると、

*Main> maxBound :: Int
2147483647
*Main> maxBound :: Bool
True
*Main> maxBound :: Char
'\1114111'
*Main> maxBound :: Ordering
GT

それぞれの型の maxBound の値を返してくれる。

 

2. 文脈から型推論できると、型の指定は省略できる

read 関数も同じく、返り値の型が多相となっている。

(cf. Haskell で、繰り返しのある数値を生成する関数を定義 – read, cycle 関数を使って)

read :: Read a => String –> a

先ほどと同じように、返り値の型を指定しないと、

*Main> read "100"

:1:0:
    Ambiguous type variable `a' in the constraint:
      `Read a' arising from a use of `read' at :1:0-9
    Probable fix: add a type signature that fixes these type variable(s)

「曖昧な型だ」と警告が出る。

返り値の型として、Read クラスのインスタンスを指定すると、値を返してくれる。

*Main> read "100" :: Int
100
*Main> (read :: String -> Int) "100"
100
*Main> read "True" :: Bool
True
*Main> read "EQ" :: Ordering
EQ

重要なのは、次のように、適用するときの文脈があると、型を指定しなくてもいい。コンパイラが型を推論してくれる。

*Main> read "100" + 1
101
*Main> read "True" && True
True
*Main> read "True" && False
False

 

3. バラエティに富んだ返り値の型の例

正規表現の (=~) も同様に、返り値の型を指定する必要がある。

(cf. Haskell で正規表現 (2) =~)

関数の型を見ると、以下のように表現されている。

(=~) :: (RegexMaker Regex CompOption ExecOption source, RegexContext Regex source1 target) => source1 -> source –> target

相変わらず、これどうやって読むかわからない。 ^^; それは横に置いておき、この関数も、返り値の型を指定しないとエラーが表示される。

*Main>:m Text.Regex.Posix
Prelude Text.Regex.Posix> "hoge" =~ "ho"

:1:0:
    No instance for (Text.Regex.Base.RegexLike.RegexContext
                       Regex [Char] target)
      arising from a use of `=~' at :1:0-13
    Possible fix:
      add an instance declaration for
      (Text.Regex.Base.RegexLike.RegexContext Regex [Char] target)
    In the expression: "hoge" =~ "ho"
    In the definition of `it': it = "hoge" =~ "ho"

返り値の型を指定すると、型に応じた結果を返してくれる。

Prelude Text.Regex.Posix> "hoge" =~ "ho" :: Bool
True
Prelude Text.Regex.Posix> filter (=~ "ho") ["hoge","piyo","fuga","hogehoge"]
["hoge","hogehoge"]
Prelude Text.Regex.Posix> "hoge" =~ "ho" :: (String,String,String,[String])
("","ho","ge",[])
Prelude Text.Regex.Base> :m Text.Regex.Base Text.Regex.Posix
Prelude Text.Regex.Base Text.Regex.Posix> "hoge" =~ "ho" :: (MatchOffset,MatchLength)
(0,2)

同じ値に、同じ演算子（関数）を適用しているにも関わらず、型の指定を変えると、異なる値が返ってくる。

 

Java との比較

上記の (=~) 演算子の動作を初めて見たとき、

「 なぜ同じ関数名で、しかも、引数も同じなのに、異なる型の値が得られるのだろう」

と思った。

例えば Java の場合、「Java言語規定 クラス」を見ると、

メソッドの シグネチャ(signature) は，メソッドの名前並びにメソッドに対する形式仮引数の個数及び型で構成する。クラスは，同じシグネチャをもつ二つのメソッドを宣言してはならない。

つまり、以下のように、「引数が同じで、返り値の型が異なる hoge メソッド」を 2 以上定義することはできない。

public class Hoge {
    void hoge(){}
    int hoge(){ return 1;}
    String hoge() { return "hoge";}
}

だから、上記の Haskell の関数の使い方を見て

「なんでそんなことができるのだろう？」

と感じた。

 

4. 返り値は型変数だけれど、引数を持つ関数との比較

Prelude を見ると、length 関数のように、返り値に特定の型が指定されている関数もあれば、

length :: [a] -> Int

返り値として、型変数が使われている関数もある。

例えば

map :: (a -> b) -> [a] -> [b]

sequence :: Monad m => [m a] -> m [a]

上記の maxBoound, read, (=~) 関数のように、返り値の型を指定してみる。

Prelude> let map' =  \f xs -> map f xs :: [String]
Prelude> :t map'
map' :: (a -> String) -> [a] -> [String]
Prelude> let sequence' = \xs -> sequence xs :: Maybe [Int]
Prelude> :t sequence'
sequence' :: [Maybe Int] -> Maybe [Int]

型の指定はできるが、このように定義した map’, sequence’ の使い途って、何かあるのかな？

 

引数による型の絞り込み

返り値の型を指定しなくてはいけない、上記 3 つの関数を並べてみる。

maxBound :: a

read :: Read a => String –> a

(=~) :: (RegexMaker Regex CompOption ExecOption source, RegexContext Regex source1 target) => source1 -> source –> target

これらの関数と比較すると、map, sequence などの関数は、引数を指定すると返り値の型が絞り込まれることがわかる。

例えば、map 関数の第1引数に関数を指定すると、

Prelude> :t map (++ "hoge")
map (++ "hoge") :: [[Char]] -> [[Char]]
Prelude> :t map (* 2)
map (* 2) :: (Num a) => [a] -> [a]

sequence 関数の第1引数にリストを指定すると、

Prelude> :t sequence [Just 1, Just 2]
sequence [Just 1, Just 2] :: (Num t) => Maybe [t]
Prelude> :t sequence [[1,2,3],[10,20,30]]
sequence [[1,2,3],[10,20,30]] :: (Num t) => [[t]]

これに対して、

「返り値の型を指定する必要のある関数」

は、引数からその返り値の型を推測できない。よって、型を直接指定するか、もしくは型を推測できるための文脈が必要になる。

 

5. 返り値の型を指定する必要のある関数を定義してみる

「返り値の型を指定する必要のある関数」に慣れるため、適当な例を考えてみる。

例えば、次のような状況。

ペットショップに「犬」や「猫」がいる。飼われる前は「名前」がない。主人が名前を付けることによってペットとなる。

 

型の定義

まずは、「犬」「猫」の型を作成。

data Dog = Dog | PetDog String deriving Show

data Cat = Cat | PetCat String deriving Show

• 接頭辞 `Pet’ が付いているデータコンストラクタを使って、作成される値がペットであることを表わし、フィールドに名前を持つ。
• `Pet’ が接頭辞が付いてない方を「飼われていない犬・猫」を表すとする。

 

返り値の型を指定する必要がある関数

「犬」「猫」共に、「名前を付けることができる」とする。両方に共通の Animal クラスを作成し、動物に名前を付ける name 関数を作成した。

class Animal a where
    name :: String -> a

この name 関数が、返り値の型を指定する必要がある関数。見てわかるように引数は String だけであり、これだけでは返り値である Animal クラスのインスタンスを推測することができない。

次に、Dog, Cat 型を Animal クラスのインスタンスとし、クラスメソッド name を実装する。

instance Animal Dog where
    name cs = PetDog cs

instance Animal Cat where
    name cs = PetCat cs

「名前」を引数として与えると、データコンストラクタ PetDog, PetCat を使って値を生成する。

 

試してみる

早速、name 関数を使ってみる。

main = do
  print $ (name "Tama" :: Cat)            -- PetCat "Tama"
  print $ (name :: String -> Cat) "Tama"  -- PetCat "Tama"
  print $ (name "Pochi" :: Dog)           -- PetDog "Pochi"

 

関数に制約を付ける

次に、Animal クラスのメソッドではない、同様の機能を持った makePet 関数を作りたいとする。この場合、関数に制約を付ける。

makePet :: Animal a => String -> a
makePet cs = name cs

これも引数が String だけなので、引数からだけでは返り値の型を推測することができない。

  print $ (makePet "Pochi" :: Dog)         -- PetDog "Pochi"

上記と同様な関数で、例えば引数に Animal クラスのインスタンスの値を与える関数を作成するなら、

makePet2 :: Animal a => a -> String -> a
makePet2 _ cs = name cs

与えた引数によって返り値の型が決まる。

  print $ makePet2 Cat "Tama"              -- PetCat "Tama"

 

全体のソースコード

class Animal a where
    name :: String -> a

data Dog = Dog | PetDog String deriving Show
instance Animal Dog where
    name cs = PetDog cs

data Cat = Cat | PetCat String deriving Show
instance Animal Cat where
    name cs = PetCat cs

makePet :: Animal a => String -> a
makePet cs = name cs

makePet2 :: Animal a => a -> String -> a
makePet2 _ cs = name cs

main = do
  print $ (name "Tama" :: Cat)
  print $ (name :: String -> Cat) "Tama"
  print $ (name "Pochi" :: Dog)

  print $ (makePet "Pochi" :: Dog)
  print $ makePet2 Cat "Tama"

 

6. Monad クラスの return メソッド

ここまで書いて、やっと気がついたことがある。

Monad の説明を読んでいて、最初に違和感を感じた return 関数。この関数が使われているのを見る度に、

何か重要なことを自分が理解していない

と感じていた。しかし、それが何なのか自覚できず。 (+_+)

return の型宣言を見ると、

return :: a -> m a

この関数も、引数を与えただけでは、

返り値は、Monad クラスのインスタンスで包む

というところまでしか決まらない。

例えば、

*Main> :t return 1
return 1 :: (Monad m, Num t) => m t
*Main> :t return "hoge"
return "hoge" :: (Monad m) => m [Char]

具体的にどのモナドで包むのか決めるには、型を指定する必要がある。

*Main> return 1 :: Maybe Int
Just 1
*Main> return "hoge" :: Maybe String
Just "hoge"
*Main> return 1 :: [Int]
[1]
*Main> return "hoge" :: [String]
["hoge"]

 

型推論される例

Monad クラスのメソッド (>>=) は

(>>=) :: forall a b. m a -> (a -> m b) -> m b

第 2 引数で具体的な型を指定すれば、第1引数で包むモナドも決まる。

*Main> return 1 >>= Just
Just 1
*Main> return "hoge" >>= Just
Just "hoge"
*Main> return 1 >>= print
1
*Main> return "hoge" >>= putStrLn
hoge

関数を定義したときも同様に、

test :: a -> Maybe a
test = return

test2 :: a -> [a]
test2 = return

main = do
  print $ test 100       -- Just 100
  print $ test "hoge"    -- Just "hoge"

  print $ test2 100      -- [100]
  print $ test2 "hoge"   -- ["hoge"]

return をはじめ見たとき、何でこれで上手く動作するのかわからなかったけれど、型が指定されていたのが理由だったということ。

前回見た sequence 関数だと、

sequence :: Monad m => [m a] -> m [a] 
sequence = foldr mcons (return [])
             where mcons p q = p >>= \x -> q >>= \y -> return (x:y)

これを値に適用した時の型を見れば、

*Main> :t sequence [Just 1, Just 2, Just 3]
sequence [Just 1, Just 2, Just 3] :: (Num t) => Maybe [t]

こちらは、引数で与えたモナドによって返り値の型が決まり、 return で包むモナドがわかるということかな。

Haskell の Maybe 型に馴染む (2)

「Haskell の Maybe 型に馴染む」 の続き。

「モナドのすべて」を読みはじめてはいるのだけど、わからないところだらけ…。 (@_@;) 今日は、Haskell におけるモナドのサポート を読んでいたら、sequence 関数の定義でつまづいた。

sequence :: Monad m => [m a] -> m [a] 
sequence = foldr mcons (return [])
             where mcons p q = p >>= \x -> q >>= \y -> return (x:y)

foldr の第1引数に与えられた mcons 関数のこの定義。どうやって読めばいいののだろうか… (+_+)

 

カリー化

まずは無名関数の基本から。引数に数値を与えると + 1 した値を返す無名関数を定義。それを適当な値に適用するなら、

main = do
  print $ (\x -> x + 1) 1

次に、二つの与えられた引数を足し合わせる関数を作成。適当な値に適用するなら、

  print $ (\x y -> x + y) 1 2

 

ところで、カリー化と関数の部分適用 によると、

Haskellでは2つの引数を持つ関数は、1つの引数をとり「ひとつの引数をとる関数」を返す関数と同義である。このように、関数を返すことで全ての関数をひとつの引数の関数として表現することをカリー化という。

この辺り、「あ～、そういうものか」とよく考えずなあなあにしていた。 ^^; (cf. カリー化 – Wikipedia)

先ほどの無名関数を上記に書かれているような形に明示的にするなら、次のような形だろうか。

  print $ ((\x -> (\y -> x + y)) 1) 2

これで『1つの引数をとり「ひとつの引数をとる関数」』になった。(cf. 3.1 ラムダ抽象) 以下のように、内側の括弧をとっても大丈夫なようだ。

  print $ (\x -> \y -> x + y) 1 2

これは、無名関数が、関数適用と同じく 結合性 の優先順位が 10 と高いためのようだ。

Haskell 98 Report: 式 via kwout

 

同様に、二つの引数を足し合わせる関数もいろいろな書き方で定義できる。

addTwo x y = x + y
addTwo' x  = \y -> x + y
 
addTwo''  = \x y -> x + y
addTwo''' = \x -> \y -> x + y
addTwo'''' = \x -> (\y -> x + y)

main = do
  print $ addTwo 1 2
  print $ (addTwo 1) 2
  print $ (addTwo' 1) 2
  print $ (addTwo'' 1) 2
  print $ (addTwo''' 1) 2
  print $ (addTwo'''' 1) 2

 

わかっちゃいないけどモナド

sequence 関数に戻る。わからなかった定義の一部を再掲。

where mcons p q = p >>= \x -> q >>= \y -> return (x:y)

見やすくするために括弧を付けるなら、

where mcons p q = p >>= (\x -> q >>= (\y -> return (x:y)))

 

ところで、Monad クラスの定義は、

class Monad m where
    (>>=)  :: m a -> (a -> m b) -> m b
    return :: a -> m a

(>>=) 演算子の第2引数は (a –> m b) 型の関数。

sequence 関数の定義における p, q は、型宣言より、それぞれモナドのインスタンスである型の値に束縛される。sequence の最後を見ると return (x:y) となっており、リストがモナドのインスタンスで包まれたものが返される。つまり、上記の無名関数のところだけ見れば (>>=) の右側は (a –> m b) 型になっており、そこへ p または q のモナドのインスタンスで包まれた中身が (>>=) で無名関数へ投入される形。 (この説明が適切なのかわからないのだけれど…)

ということで、なんとなく読めるようにはなった。

 

とにかく使ってみる

さて、ここで「モナド」も「モナド則」もわかっていないけれど、Maybe を使って sequence の定義を真似た関数を作成してみることに。わからないものはとりあえず動作しているもの見て、見慣れてからそれが何なのか理解する方向で。 ^^;

作成するのは、「Maybe で包んだ数値を二つ引数として与えると、中身を足して、その結果を Maybe で包んで返す」関数。関数名を addTwoM とした。まずは型宣言。

addTwoM :: Num a => Maybe a -> Maybe a -> Maybe a

 

いきなり、全部真似るとわからなくなるので、まず、第1引数に渡された Maybe の中身を (>>=) で渡し、それを単純に Maybe で包んで返すだけの動作を確認。

addTwoM p _ = p >>= \x –> Just x

以下を実行。

  print $ addTwoM (Just 1) (Just 2)      -- Just 1

お～、返ってきた。^^

次に、二つの Maybe の中身を受け取り、足し合わせるように変更。

addTwoM p q = p >>= \x -> q >>= \y –> Just $ x + y

括弧をつけて見やすくすると、

addTwoM p q = p >>= (\x -> q >>= (\y –> Just $ x + y))

以下を実行。

  print $ addTwoM (Just 1) (Just 2)   -- Just 3
  print $ addTwoM (Just 1) Nothing    -- Nothing
  print $ addTwoM Nothing (Just 2)    -- Nothing

 

型宣言を Monad へ

せっかくなので、関数の型を Maybe から Monad に変更してみる。

addTwoM :: (Monad m, Num a) => m a -> m a -> m a

変更しても動くかな？と思い試してみると、

    Couldn't match expected type `m' against inferred type `Maybe'
      `m' is a rigid type variable bound by
          the type signature for `addTwoM' at lambdatest.hs:9:18
      Expected type: m a
      Inferred type: Maybe a
    In the expression: Just $ x + y
    In the second argument of `(>>=)', namely `\ y -> Just $ x + y'

定義で Just を使っているので、この関数は Maybe a 型に固定されてしまっているということだろうか。これも sequence 関数を参考にして、return に変更する。

addTwoM p q = p >>= \x -> q >>= \y -> return $ x + y

なぜ return なのだろう？これは型宣言を見るとわかるが、先ほどまで関数は Maybe について書いていた。しかし、今この関数の型宣言は、もう１つ抽象的な Monad のレベルで定義している。だから、Maybe のように特定の型について言及していてはダメということなのだろう。(多分) だから、Monad に定義されているメソッドを使って関数を定義する。

 

Maybe の定義

Maybe に戻り Maybe モナド を見ると、(>>=) や return の具体的な定義が書かれている。そもそも以下のように Monad のインスタンスであると宣言しているので、Maybe a 型の値を上記の addTwoM に適用することができる。

instance Monad Maybe where
    return         = Just
    fail           = Nothing
    Nothing  >>= f = Nothing
    (Just x) >>= f = f x

それぞれの関数の型はどうなっているのだろうかと思い、先ほどの Monad クラスの定義の中の `m’ を Maybe で置き換えて書いてみると、

class Monad Maybe where
    (>>=)  :: Maybe a -> (a -> Maybe b) -> Maybe b
    return :: a -> Maybe a

上記の Maybe の定義はこの型宣言に合わせ、また Monad の 三つの基本則

1. (return x) >>= f == f x
2. m >>= return == m
3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)

を満たすように定義されている。しかし、なぜこの規則を満たす必要があるのかまだ理解できない。(+_+)

 

リストもモナド

Monad クラスのインスタンスを見ると、リストも仲間だということがわかる。ということは addTwoM 関数を適用できるということ。

  print $ addTwoM [1] [2]         -- [3]
  print $ addTwoM [1,2] [2]       -- [3,4]
  print $ addTwoM [1] [2,3]       -- [3,4]
  print $ addTwoM [1,2] [2,3]     -- [3,4,4,5]
  print $ addTwoM [] [1]          -- []
  print $ addTwoM [1] []          -- []

ふ～む、[1] というのは `1’ が [ ] で包まれているということだったのか。 (@_@) それにしても、この結果はどうしてなんだろう？

List モナド を見たら、以下のように定義されてる。

instance Monad [] where
    m >>= f  = concatMap f m
    return x = [x]
    fail s   = []

具体的に試してみる。

  print $ [1..5] >>= \x -> return x             -- [1,2,3,4,5]
  print $ [1..5] >>= \x -> return (x*2)         -- [2,4,6,8,10]
  print $ concatMap (\x -> return x) [1..5]     -- [1,2,3,4,5]
  print $ [1,100] >>= (\x -> [11,12] >>= (\y -> return $ x + y))  -- [12,13,111,112]

は～、なるほど (>>=) と return はリストに対してそういう働きをするわけか。

Monad 自体の意味はよくわからないけれど、少しだけ Monad に近づけた気がした。

Haskell の Maybe 型に馴染む

モナドの説明を読みはじめると最初の方に必ず出てくる Maybe 型。モナド自体いつか理解したいと思いつつ、解説されているサイトを読んでも途中で挫折。(o_ _)ｏ~† ここは一つ外堀から埋めていこうと、 Monad クラスのインスタンスである Maybe 型から見ていくことに。

 

Prelude における位置付け

Maybe 型は、Prelude の説明の最初、「Basic data types 」の中に含まれていることから考えて、相当重要な型のようだ。Basic data types に含まれている他の型を挙げると、

• data Bool
• data Either a b
• data Ordering
• data Char

Either a b 型って何だろうなと横目で見つつ、他の型を見ると基本的で重要なものばかり。(@_@) ちなみに、Haskell Hierarchical Libraries には Data.Maybe とある。

「All About Monads」 を読んでも、冒頭の Introduction から Maybe について書かれている。

これは結果を返しそこなうかもしれない計算の型を表現しています。 Maybe 型が示唆するものは、Maybe 型の値を返す計算の合成に関する戦略です。

何やら難しい表現が… (@_@;)

 

Java の null

これが例えば Java なら、次のような場合を考えてみる。例えばここに「人」を表わす Person クラスがあるとする。属性に名前を持つ。Person クラスの配列から `名前’ を元に Person オブジェクトを検索するメソッド (Search.find) を考えると、

public class Search {
    private static Person[] persons = {new Person("Tarou"), 
                                       new Person("Hanako"),
                                       new Person("Jiro")};
    public static void main(String[] args) {
        System.out.println(find("Hanako"));
        System.out.println(find("Saburou"));
    }
    static Person find(String name){
        for(Person p : persons){
            if (p.getName().equals(name)){
                return p;
            }
        }
        return null;
    }
}
class Person{
    private String name;
    Person(String name){
        this.name = name;
    }
    String getName(){
        return this.name;
    }
    @Override
    public String toString(){
        return this.name;
    }
}

“Hanako” を検索した場合は、Person(“Hanako”) を返すことができる。しかし、”Saburou” を検索しても見つけることができない。Search.find メソッドは Person クラスのオブジェクトを返すが、Java において、参照型をメソッドの返り値にすると null も返すことができる。

式 null の型である特別な 空型(null type) も存在する。それには名前がない。空型には名前がないので，空型の変数を宣言すること又は空型にキャストすることはできない。空型の式が取りうる唯一の値が空参照となる。 空参照は，常に任意の参照型にキャストできる。実際には，Javaプログラマは，空型を無視し，空型は任意の参照型となれる単なる特別なリテラルであると見なしても良い。

(Java言語規定 型，値及び変数 より。太字は引用者による)

検索しても見つからなかったら null を返す。これが自分にとって、メソッドにおける普通の感覚だった。

 

Haskell で検索メソッドを実装

Haskell でも上記の Java と同じような内容のコードを書いてみる。Data.List に find 関数があるが、これは使わずに横に置いておく。

最初、次のように書いてみた。

data Person = Person {name :: String} deriving (Show,Eq)

persons = [Person "Tarou", Person "Hanako", Person "Jiro"]

find1 :: String -> [Person] -> Person
find1 n (p:ps) = if (name p) == n then p else find1 n ps

main = do
  print $ find1 "Hanako" persons
  print $ find1 "Saburou" persons

結果は “Saburou” の検索で、

Non-exhaustive patterns in function find1

 

ここで当初、null とか nil とか None のようなものを返すことはできないかな？と思った。しかし、リストの要素が空であるか確かめる null 関数は見つかったが、探しものは見つからず。

さすがに、find1 で次のようにするわけにもいかないし。

find1 n [] = Person("null")

これでは 名前が「null」さんを返すことになってしまう。^^; 「見つからなかった」と意味が全然違う。

 

では、Person 型に Empty というデータコンストラクタを定義し、

data Person = Person {name :: String} 
            | Empty 
              deriving (Show,Eq)

find1 に以下を追加したらどうだろう？

find1 n [] = Empty

しかし、これも名前のない「空の人」という意味として使ったとして、何だかしっくりこない感じが。「見つからなかった」ということに使うにしても、それが Person 型の値になるので違和感もある。

 

Maybe

と、そのとき、ふつうのHaskellプログラミング がモナドの章に到達し、何がなんだかわからないうちに Maybe モナドが出現。(@_@;) lookup 関数を使って Monad と Maybe の関係が説明されていたが、このときモナドだけで目が回っていたので、当然ながらその関係も把握できず。ただし、これを使えば上記の null に相当するものに使えそうなことだけはわかった。Prelude の説明を読むと、

Using Maybe is a good way to deal with errors or exceptional cases without resorting to drastic measures such as error.

データコンストラクタは、Nothing と Just a。

 

Monad についてよくわからないけれど、とにかく Maybe を使ってみることに。検索して見つかったら Just で包み、見つからなかったら Nothing を返す。

find2 :: String -> [Person] -> Maybe Person
find2 n [] = Nothing
find2 n (p:ps) = if (name p) == n then Just p else find2 n ps

この関数を使うと、

  print $ find2 "Hanako" persons     # Just (Person {name = "Hanako"})
  print $ find2 "Saburou" persons    # Nothing

 

ただし、上記の方法だと、検索が Person 型に固定されてしまっている。Person 型から 型変数 a に変えるなら、

find3 :: a -> [a] -> Maybe a
find3 t [] = Nothing
find3 t (x:xs) = if x == t then Just t else find3 t xs

しかし、これだとエラーが。 (+_+)

    Could not deduce (Eq a) from the context ()
      arising from a use of `==' at searchtest.hs:20:20-25
    Possible fix:
      add (Eq a) to the context of the type signature for `find3'
    In the predicate expression: x == t
    …

なるほど、x == t と演算子を適用できるには、型変数に対応した値が、 Eq クラスのインスタンスである型の値である必要があるということ。だから、関数の型宣言を以下のように変更。

find3 :: Eq a => a -> [a] -> Maybe a

Person 型は Eq クラスのインスタンスなので、find3 関数を適用することができる。

 

しかし、上記の find3 関数は Eq クラスの (==) メソッドの実装に依存し、検索方法が固定されてしまっている。そこで、「検索の基準」を与えることによって、探したい値を得ることができるように変更。

find4 :: (a -> Bool) -> [a] -> Maybe a
find4 f [] = Nothing
find4 f (x:xs) = if f x then Just x else find4 f xs

この関数を使うには、

  print $ find4 (\p -> (name p) == "Hanako") persons
  print $ find4 (\p -> (name p) == "Saburou") persons

 

Data.List の find

これで Data.List の find 関数の見かけと同じようになった。

find :: (a -> Bool) -> [a] -> Maybe a

Data.List の find の定義を見たら、filter 関数が使われていた。

find                    :: (a -> Bool) -> [a] -> Maybe a
find p                  =  listToMaybe . filter p
(The Haskell 98 Library Report: List Utilities より)

あぁ～、「検索」と「フィルタ」は同じことか。 (@_@)

listToMaybe  関数は、リストを与えると、その先頭要素を Just で包んで返してくれる。

listToMaybe            :: [a] -> Maybe a
listToMaybe []         =  Nothing
listToMaybe (a:_)      =  Just a
(The Haskell 98 Library Report: Maybe Utilities より)

関連記事

• Haskell の Maybe 型に馴染む (2)