Monads - flatMap 和 unit 的抽象介面

在介紹 Monad 之前，先聊聊一個之前有在 Option 和 Parser 下用到的 function map2，它能用一個 high-order function，把 2 個 Parser/Option 舉起來之後，轉成新的給你，

def map2[A, B, C](oa: Option[A], ob: Option[B])(f: (A, B) => C): Option[C] =
	oa.flatMap(a => ob.map(b => f(a, b)))	

def map2[A, B, C](pa: Parser[A], pb: Parser[B])(f: (A, B) => C): Parser[C] =
	pa.flatMap(a => pb.map(b => f(a, b)))

若我們要一般化這些動作的話，就是 flatMap 和 map，然而若有 flatMap，map 就可以用 flatMap + unit 來實作，

def map[A, B](pa: Parser[A])(f: A => B): Parser[B] =
  pa.flatMap(a => unit(f(a)))

所以我們就可以用 flatMap 和 unit 當做抽象介面裡的核心 function，此介面被稱為 Monad，

trait Monad[F[_]] extends Functor[F]:
  def unit[A](a: => A): F[A]

  extension[A] (fa: F[A])
    def flatMap[B](f: A => F[B]): F[B]

    def map[B](f: A => B): F[B] =
      fa.flatMap(a => unit(f(a)))

    def map2[B, C](fb: F[B])(f: (A, B) => C): F[C] =
      fa.flatMap(a => fb.map(b => f(a, b)))

Monad 的概念也是來自於 Category Theory，它被定義為 Functor 下的其中一個結構，所以我們才會看到 Monad 繼承了 Functor，代表了所有的 Monad 都是 Functor，但不是所有的 Functor 都是 Monad，

我們用來實作一個 Parser 的 Monad 吧！

  def parserMonad[P[+_]](p: Parsers[P]): Monad[P] = new:
    def unit[A](a: => A) = p.succeed(a)

    extension[A] (fa: P[A])
      def flatMap[B](f: A => P[B]): P[B] =
        p.flatMap(fa)(f)

Exercise D26-1

實作一個 Option 和 List 的 Monad（跟 Day 24 的 Foldable[List] 一樣，這裡用 given 關鍵字讓它變成具有上下文關係）。

given listMonad: Monad[List] with
given optionMonad: Monad[Option] with

Monad 組合器方法

跟 Monoids 一樣，我們可以設計多樣化組合器 function 來操作 Monad，例如 product function，它能將 2 個 Monad 配對成一個 Monad（放在 Monad 的 extension 底下）；

def product[B](fb: F[B]): F[(A, B)] =
  fa.map2(fb)((_, _))

而另一個組合器例子可以來看看 traverse function，它能夠僅使用一次迭代就把 List[A] 轉成 Monad with List[B]。

def traverse[A, B](as: List[A])(f: A => F[B]): F[List[B]] =
  as.foldRight(unit(List[B]()))((a, acc) => f(a).map2(acc)(_ :: _))

Exercise D26-2

來嘗試實作 sequence function 吧，它的實作程式跟 traverse 很類似。

def sequence[A](fas: List[F[A]]): F[List[A]]

我們在 Day 19 - 能自由組合的解析器 Library (1) 的 Parser 下定義過 listOfN function，

def listOfN[A](n: Int, Parser[A]): Parser[List[A]]

它讓我們重覆一個 Parser n 次，然後得到相對應長度 List 的 Parser，這裡我們也可以把它一般化並放到 Monad 介面底下，但這次給它個更通俗的名稱吧！

Exercise D26-3

實作 replicateM。

def replicateM[A](n: Int, fa: F[A]): F[List[A]]

截至目前為止看到的組合器 function 只是一小部份的範例，最重要的是想像和動手下去玩，明天繼續介紹 Monad 的定律。

Day 26 - Exercise answer