会社の勉強会でプログラミングHaskell14章を読んだ

ついに14章まで来ました。書籍は17章までなので、もう少しで完走できる、、、！

勉強会を始めたのが去年の8月なので、なんとか今年の8月までに完走したいところ。

あと、このブログに適当に貼ってる勉強会のメモをちゃんと整形して、プログラミングHaskellを読むための本みたいにすることができたら良いなぁ。

14章で扱うテーマ

モノイド
Foldable
Traversable

モノイド

集合が「集合の二つの要素を結びつける結合的な演算子」と「その演算子に対する単位元」を持つとき、その代数的構造をモノイドと呼ぶ

-- Haskellにおける型クラス宣言
-- モノイドの概念の抽象化
class Monoid a where
  -- 単位元
  mempty :: a
  -- 演算子
  mappend :: a -> a -> a
  
  mconcat :: [a] -> a
  mconcat :: foldr mappend mempty

-- 単位元と演算子が満たさなければならない則（モノイド則）
mempty `mappend` x           = x
x `mappend` mempty           = x
x `mapppend` (y `mappend` z) = (x `mappend` y) `mappend` z

mempty, mappendといった命名から、空のもの、追加に関する演算子を連想するが、２つのメソッドは、あくまで「モノイド則」を満たしていれば良い。

Foldable

リストに対する畳込関数の考え方を、型変数をもつ型へと拡張したもの

モノイドを使用して、あるデータ構造の中にある全ての値を１つにまとめるという作業がよく行われる

例えば、リストの場合(他にはTreeなどが紹介されていた)

-- リストの中の値を１つにまとめる関数
-- 空リストにfoldを適用すると、モノイドの単位元memptyとなる
-- 空でないリストでは、「リストの先頭」と「残りのリストを再帰的に処理した結果」をmappendで連結する
-- ※Monoidなのはリストの要素であり、リスト自体ではないため注意
fold :: Monoid a => [a] -> a
fold []     = mempty
fold (x:xs) = x `mappend` fold xs

「データ構造の中の値をモノイドを使って畳み込む操作」は、リストやTreeだけでなく、型引数をもつ型全般に対して抽象化できる -> この抽象化はFoldableと呼ばれる

class Foldable t where
  fold    :: Monoid a => t a -> a -- リストの中の値を１つに畳み込むイメージ
  foldMap :: Monoid b => (a -> b) -> t a -> b -- リストの中の値に一つずつ関数を適用し、その結果を畳み込んで１つの値にするイメージ
  
  -- リスト用高階関数の一般化、初期値と二つの値を連結する関数を引数として明示的に渡すので、モノイドに関する制約はない
  foldr   :: (a -> b -> b) -> b -> t a -> b
  foldl   :: (a -> b -> a) -> a -> t b -> a

また、Foldableクラスではデータ構造の中の値を処理するためのメソッドがたくさん提供されている（null, length, elem ...etc）特に、データ構造を平坦化しリストへ変換するメソッドtoListは、リスト向けのメソッドを流用して実装を与えるために便利（Foldableのデフォルト実装にも使われている）

-- toList :: t a -> [a]

-- いくつか例
null    = null . toList
length  = length . toList
maximum = maximum . toList
sum     = sum . toList

Foldableに抽象化することの利点は、Foldableクラスのメソッドを使って、Foldableであれば何にでも使える汎用的な関数を定義可能になったこと

-- リスト構造の中の値の平均を求める関数をFoldableに抽象化
average :: Foldable t => t Int -> Int
average ns = sum ns `div` length ns


-- 上記関数は、（Foldable型クラスのインスタンスである）リストと木の両方に適用できる
> average [1..10]
5

> average (Node (Leaf 1) (Leaf 3))
2

toListによりFoldableは必ずリストに変換できる

-- 以下と同等らしい
toList :: Foldable t => t a -> [a]
toList = foldMap (\x -> [x])

これは[x]がMonoidであることが暗黙に前提となっている。ここでのmappendは(:)となる（実験より）つまり、foldMap(\x -> [x])は、対象のFolable t x型の各要素を[x]に置き換え（つまり t [x]型にして）それをfoldしたものになり、これは結局[x]の全要素を(:)で連結した要素を返すということになる。

参考： https://hackage.haskell.org/package/base-4.15.0.0/docs/src/Data-Foldable.html#toList （わかりにくいというかbuildがわからない）

https://namc.in/posts/foldables-traversals/ 上の定義が例示されている。おそらく実質同じであると予想

Traversable

あるデータ構造を走査するという考え方を抽象化したもの

class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

-- 参考
class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  -- fmap :: (a -> b) -> f a -> f b
  
class Functor t where
  fmap :: (a -> b) -> t a -> t b

疑問としては「Traversableである必要あるの？foldrでいけるのでは？」

dec :: Int -> Maybe Int
dec n = if n > 0 then Just (n-1) else Nothing

instance Traversable Tree where
  traverse g (Leaf x)   = pure Leaf <*> g x
  traverse g (Node l r) =
     pure Node <*> traverse g l <*> traverse g r


> traverse dec [1,2,3]
=> Just [0,1,2]

> traverse dec (Node(Leaf 0) (Leaf 1))
=> Nothing

-- 型が違う気がする（雑直感）fmapだと[Nothing]みたいになりそう。Foldableじゃないとどうなるんだっけ？

Traversableである型tが関手であるという制約は、Traversableが変換の概念を一般化したものであり、fmapが提供されているという事実を反映している（関手はデータ構造の中の各要素に関数を適用していくという考え方の抽象化）また、型tがFoldableであるという制約から、Traversableの値は必要に応じて畳み込めることが保証されている