田舎で並行処理の夢を見る

試したこと、需要がないかもしれないけど細々とアウトプットしてます

ElixirでListMonadを作ってみる

Monad(モナド)の魅力

関数型言語に触れていれば少なからず「Monad(モナド)」という言葉を耳にする。残念ながら私の愛するElixirではMonad(モナド)を大々的に取り扱うことはない(知らないだけなのかも)はないが、純粋関数型言語として有名なHaskellではMonad(モナド)をガンガン扱う。

Haskellについては「プログラミングHaskell」という書籍を読んだ程度の知見しかないが、Monad(モナド)を使うこなすことで関数の純粋さを保ち、参照透過性を担保するのだそう。ただでさえMonad(モナド)については多くの方が解説しており、複雑化して理解が難しくなっているため、自分が新たに説明をすることは控えておく。

圏論Monad(モナド)HaskellMonad(モナド)の違いとそれぞれの理解に4日ほど時間がかかってしまった。トホホ...

圏論におけるMonad(モナド)の定義

先ほども述べたようにHaskellでのMonad(モナド)圏論でのMonad(モナド)は異なっており、情報を分けないと理解が難しくなる。以下の記事が非常に分かりやすかった。理解のために幾らか情報を漁ったので、分かりやすかったものを参考文献にまとめたのでそちらもどうぞ。

kentutorialbook.github.io

情報量が非常に多いため、自分の言葉で簡単に圏論でのMonad(モナド)を要約しておく(※これは説明ではないのでご愛敬。明日の自分のための書き残し)。
そもそも圏論の「圏」というのは英訳すると「Category」になる。

圏論(けんろん、category theory)は、数学的構造とその間の関係を抽象的に扱う数学理論の 1 つである。

ja.wikipedia.org

プログラミング言語の中では圏というのはデータ構造であると考えると非常に分かりやすい。

  • 配列(リスト)
  • オブジェクト
  • 文字列(String)
  • 数値(Integer) etc...

それぞれが圏(言葉の意味の通りCategory)というまとまりであり、プログラミング言語においての圏論の立ち振る舞いはデータ構造同士の関係を扱うための理論であると考えることが出来る。

ここまで圏論プログラミング言語の関係性が分かったところで本題のMonad(モナド)について考えてみる。
圏論においてMonad(モナド)とは特定の条件を満たす圏のことであり、プログラミング言語に言い換えれば、先ほどの話から特定のルールを満たすデータ構造のことになる。

Monad(モナド)を満たす3条件

では、特定の条件が何かというと3つある。

数学の一分野である圏論において、モナド(英語: monad)あるいはトリプル(英語: triple)とは(自己)関手と2つの自然変換の三つ組である。

3つの組は⟨T,η,μ⟩と表現されることが多く、それぞれが以下のようになる。

自己函手 T:C→C
自然変換 η:IdC⇒T
自然変換 μ:T∘T⇒T

30分でわかるJavaScriptプログラマのためのモナド入門より引用

記号の読み方すら怪しいが、1つ1つ見てみれば難しいものではないのかもしれない。

自己函手(endofunctor)は自分自身と同じデータを返す関手(函手)であり、身近な関数で言えばmapが該当する。ところで関手とはAの圏をBの圏に変換するものであり、プログラミング言語で表現するなら、文字列(String)を数値(Integer)に変換するものだと考えるとしっくりくる。

自己関手というのは名前の通り、Aの圏をAの圏に変換(実際には変換していない)するものである。
残り2つの自然変換については以下のようになる。

  • 何らかの圏の値をAの圏の値に変換する(IdC⇒T)
  • AAの圏の値(配列だと[[]])をAの圏の値に変換する(T∘T⇒T)

Monad(モナド)を満たすリスト(データ構造)の作成

ElixirにはListというデータ構造が用意されているので、こちらを利用してMonad(モナド)の3条件を満たす3つの関数を用意してみる。今回はMonad(モナド)の優位性を体感するためにElixirの便利なEnumListモジュールを使用せずに作成する。
まずは自己関手から。

T:C→C

def map([], _), do: []
def map([h|t], f), do: [f.(h) | map(t, f)]

ただのmap関数ですね。リストの各要素に引数経由で受け取った関数を再帰させて適用していく。

IdC⇒T

def unit(v), do: [v]

受け取った値をリストにして返すのみ。

T∘T⇒T

定義がデータ構造によって捉え方が難しいが、リストであれば次元を1つ落とす関数であると考えると良い。すでに1次元のリストであれば、そのまま返す。

def flat(lst) when is_list(lst) do
    _flat(lst, [])
end
defp _flat([], acc), do: acc
defp _flat([h|t], acc) do
    if is_list(h) do
        _flat(t, acc ++ h)
    else
        _flat(t, acc ++ [h])
    end
end

これでMonad(モナド)の3つの条件を満たす関数を定義され、リストをMonad(モナド)として扱う準備が整った。

コードの全体像

# Define for Monad
defmodule Monad do
    def map([], _), do: []
    def map([h|t], f), do: [f.(h) | map(t, f)]
    def unit(v), do: [v]
    def flat(lst) when is_list(lst) do
        _flat(lst, [])
    end
    defp _flat([], acc), do: acc
    defp _flat([h|t], acc) do
        if is_list(h) do
            _flat(t, acc ++ h)
        else
            _flat(t, acc ++ [h])
        end
    end
end

さっそく使ってみる

ここにあるサンプルの関数をいくつか適当に真似てElixirListMonadを実装してみた。
kentutorialbook.github.io

使用するデータの作成

lst = for x <- 1..5, do: x

各要素を2倍にする

# Normal
lst
|> Enum.map(fn a -> a * 2 end)
|> IO.inspect() # [2, 4, 6, 8, 10]

# Monad
lst
|> Monad.map(fn a -> Monad.unit(a * 2) end)
|> Monad.flat()
|> IO.inspect() # [2, 4, 6, 8, 10]

各要素を2倍した後、全ての要素に1を足す

# Normal
lst
|> Enum.map(fn a -> a * 2 end)
|> Enum.map(fn a -> a + 1 end)
|> IO.inspect() # [3, 5, 7, 9, 11]

# Monad
lst
|> Monad.map(fn a -> [a * 2] end)
|> Monad.flat()
|> Monad.map(fn a -> [a + 1] end)
|> Monad.flat()
|> IO.inspect() # [3, 5, 7, 9, 11]

要素を増やす(eg: [1,2] -> [1,1,2,2])

# Normal
lst
|> Enum.map(fn a -> [a, a] end)
|> List.flatten()
|> IO.inspect() # [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]

# Monad
lst
|> Monad.map(fn a -> [[a, a]] end)
|> Monad.flat()
|> IO.inspect() # [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]

奇数の要素のみを抽出

以下、Monad(モナド)のみを定義

# Monad
lst
|> Monad.map(fn a -> if rem(a, 2) == 1, do: [a], else: [] end)
|> Monad.flat()
|> IO.inspect() # [1, 3, 5]

これが凄い。map関数のみであれば、要素数の変更を行う事は絶対に出来ないが、map(自己関手)flatを満たすMonad(モナド)であるため、[]の要素を上手く取り除く事が可能になっており、今回の1番の驚きポイント。

Monad(モナド)と合わせてflatMap(flat_map)という関数をよく見るが、今まで何気なくやってきたmap -> flatという操作を1つにまとめたものがflatMap(flat_map)に該当する関数であり、ListMonadをパワフルにしてくれる。

flat_mapを定義

ここでMonadモジュールにflat_map関数を用意。mapflatを結合した関数なのでflat_map命名されている。

def flat_map(lst, f) do
    lst
    |> map(f)
    |> flat()
end

flat_mapを使用して各要素を2倍した後、全ての要素に1を足す

# Monad
lst
|> Monad.flat_map(fn a -> [a * 2] end)
|> Monad.flat_map(fn a -> [a + 1] end)
|> IO.inspect() # [3, 5, 7, 9, 11]

リストの次元を1つ落とす

# Monad 
d_lst = for x <- 1..5, do: [x]

d_lst
|> Monad.flat_map(fn a -> a end)
|> Monad.flat_map(fn a -> [a * 2] end)
|> IO.inspect() # [2, 4, 6, 8, 10]

Monad(モナド)を使うメリットは何か

Monad(モナド)に用意された3つの関数(map, unit, flat)を組み合わせることであらゆる操作を行うことが出来るようだ。例えば、わざわざ言語に実装されているfilter関数などを意識せずとも、気軽に機能を満たす関数を作成することが出来る。これこそまさに関数型プログラミングの真髄である小さな関数を組み合わせて、強力な関数を作り上げていく操作そのものだと感じた。

lst = for x <- 1..5, do: x
filter = fn lst, cond_ ->
    Monad.flat_map(lst, fn a ->
            if cond_.(a), do: [a], else: [] 
        end
    )
end

filter.(lst, fn a -> a > 3 end)
|> IO.inspect() # [4, 5]

またMonad(モナド)は必ずMonad(モナド)を返すという性質があるため、ListMonadであれば必ず条件を満たすListMonadを返すため、Elixirのパイプライン構文と同じく処理の結合を行うことが可能であり、Monad(モナド)で作られた関数であれば、Monad(モナド)が常に返るためerrorとなることが無さそうだ。

ではreduce関数に該当する処理はどうすればいいのか。おそらく、StringMonadIntegerMonadのようなデータを用意して、ListMonadを別の圏に変換する関手を定義してあげれば良さそうだ。

参考文献