Stack monads in Scala

A petty problem

一直有個問題縈繞在我的心頭，只是那時覺得這是無解的事情，交給開發人員自己去解決就行，最近有點時間，故又去思考了一下。

問題就是：當項目中使用Thrift/Finagle等RPC框架，以及鼓勵Reactive programming後，函數返回類型(ReturnType)不再是簡單的：Option，List，Either...了，而是Future[List[A]]，Future[Option[A]]，Future[Either[E, A]]...這樣複合的類型（包括用什麼Scalaz Task），這就導致沒法使用原來的for/yield sugar了

對相同的ReturnType：

type EitherSOF[+A] = String / Option[A] //Scalaz的Eithernval result: EitherSOF[Int] = Some(1).rightnnval result2: EitherSOF[Int] = Some(2).rightnval transformed =n for {n option <- result //解第一層n option2 <- result2n } yield {n for {n value <- option //解第二層n value2 <- option2n } yield value + value2n }n

需要解兩次 （套的層越多，解的次數越多）

對不同的ReturnType：

val res = for {n a <- Some(1)n b <- 1 :: 2 :: Niln} yield a + bn

sorry 編譯不過，for/yield的<-左邊是M[A]的A，右邊是M，也就是Monad，並且必須是同一個Monad類型（不信？你手動展開為flatMap看看就好了）

（Excuse me? 為啥要把Option和List放一起做計算？我也不知道，maybe你需要一個類型為Option[List[A]]的結果，ㄟ( ▔, ▔ )ㄏ）

Monad-Transformer

對第一種情況：要想一次性取出EitherSOF[+A]中的A值，必須把EitherSOF作為一個Monad，那就是使用monad-transformer（以下簡稱MT）了，令type EitherF[A] = Either[String, A], EitherF[Option[_]]是Either套Option，我們暫稱為Monad Stack，我們得把它變成一個Monad，所以我們需要OptionT[EitherF, A] (科普：MT的類型是與Monad Stack嵌套順序相反的, 由里往外層寫) ：

type EitherF[+A] = String / Antype OptionTEitherF[A] = OptionT[EitherF, A]nimplicit def liftToMT[A](e: EitherSOF[A]) = OptionT[EitherF, A](e)nnval transformedT = for {n value <- result : OptionTEitherF[Int]n value2 <- result2 : OptionTEitherF[Int]n} yield value + value2nnval transformed = transformedT.run n

對第二種情況：如果上面的例子編譯過了，那麼res將會是個Option[List[A]] （對，就是從上往下數），所以我們需要的是ListT[Option, A]這樣的MT:

def getOL[A](l: A*): ListT[Option, A] = ListT.fromList(Option(l.toList))nval res1 = for {n a <- getOL(1)n b <- getOL(1, 2)n} yield a + bnval res: Option[List[Int]] = res1.run n

得到你要的Option[List[A]]，不要問我看著咋這麼奇怪，這是你自己要的啊！（吐槽：大部分情況下不會存在這種類型，大部分情況下你需要的是Natural-Transformation，將Option[A] 轉為 List[A]，或反過來，你不覺得Size=1的List或Nil和Option是同一個意思嗎？...好吧，不是，作為monoid不一樣哦，List |+| Nil => List，Some |+| None => None，但作為container是一樣的）

納～尼？2個以上的Monad Stack呢？刷一發List[Either[Option]]吧

type Error = Stringntype LEO[A] = List[/[Error, Option[A]]]ntype LEOT[A] = OptionT[({type l[X] = EitherT[List, Error, X]})#l, A]ndef getLEOT[A](a: A): LEOT[A] = OptionT[({type l[+X] = EitherT[List, Error, X]})#l, A](EitherT[List, Error, Option[A]](List(/-(Option(a)))))nnval res2 = for {n a <- getLEOT(1)n b <- getLEOT(null.asInstanceOf[Int])n} yield a + bnnval res3: LEO[Int] = res2.run.run n

註：Monad Stack一般情況下通過MT的run方法轉換/解回來

Application layer

But！不可以讓application layer的人去寫MT的轉換， people will not be happy。（同事看到我在寫/的pattern matching（/-，-/），他說『你在練法輪功嗎？』）一些框架給的解決方案，太mathematic，太generic，有些東西直接放在application layer里並不友好，需要分離開來，這就是middleware思想，解決generic問題的邏輯不要和業務混在一起，可以用DSL的方式提供，Scala有implicit，可以很好的注入邏輯。

嘗試

暴力枚舉：項目中所有ReturnType

也就是這麼多。。。多（我將Writer和Reader和State歸為一類，作為ReturnType不太適合，若真有，自己去寫擴展去(╯‵□′)╯）為他們都寫一遍類似getLEOT的方法，量也不多嘛。。。嘛

但這只是針對ReturnType的Monad Stack相同的情況，不同時呢？

陷入如何做千層面的沉思 (￣へ￣)

MonadTrans & Hoist 內部加層&轉換中間層

MonadTrans是個typeclass，用來給F[A]內部增加一層MT，變為 F[M[A]]

val omt: OptionT[List, Int] = MonadTrans[OptionT].liftM(List(1)) //List(1) => List(Some(1)) 內部增加了一層Optionntype G[A] = String / Anval omt2: OptionT[G, Int] = MonadTrans[OptionT].liftMU(1.right[String]) // Right(1) => Right(Some(1))n

Hoist則是依靠自然變換來幹活：

trait Hoist[F[_[_], _]] extends MonadTrans[F] {n def hoist[M[_]: Monad, N[_]](f: M ~> N): ({type f[x] = F[M, x]})#f ~> ({type f[x] = F[N, x]})#fn}n

提供一個Monad1[_] ~> Monad2[_]的自然變換，和一個 MT，返回一個MT[Monad1, _] ~> MT[Monad2, _]的自然變換，提供MT[Monad1, _]就可以獲得MT[Monad2, _]啦

val nt: ({type λ[x] = OptionT[scala.List, x]})#λ ~> ({type λ[x] = OptionT[Future, x]})#λ =n Hoist[OptionT].hoist(new (List ~> Future) {def apply[A](fa: List[A]): Future[A] = Future(fa.head)})nval ofmt: OptionT[Future, Int] = nt(OptionT(List(Option(1)))) // List(Option(1)) => Future(Option(1))n

註：MT也是Monad 所以提供 Monad1[_] ~> MT1[Monad2, _] + MT2 可得到 MT2[Monad1, _] ~> MT2[MT1, _]

在stack monad時，如OptionT[ListT[Future]] 和 OptionT[EitherT[Future]] 提供ListT ~> EitherT 和 Hoist[OptionT] 就可以得到OptionT[ListT[Future]] ～> OptionT[EitherT[Future]]，實現中間層的轉換了

Kleisli - mapK & liftMK

def mapK[N[_], C](f: M[B] => N[C]): Kleisli[N, A, C] = kleisli(a => f(run(a)))n//run是 case class Kleisli[M[_], A, B](run: A => M[B])n

將A => M[B] 和 M[B] => N[C] 串起來

註：N和M是不同的Monad

再註：其實上面的f就是個自然變換，當N為MT[F[_], _]時就達到往外加層的目的了

val k1: Kleisli[List, Int, Int] = Kleisli{x: Int => List(x)}ntype ListTOF[A] = ListT[Option, A]nval k2: Kleisli[ListTOF, Int, Int] = k1.mapK[ListTOF, Int](e => ListT(Option(e))) //將K[List, A, B] 變成了K[ListT[Option], A, B]n//因為e是個List[A] 所以只能做ListT 或 ListT[MT] List只能在最裡面所以是往外加層 List[A] => M1[M2[List[A]]]n

def liftMK[T[_[_], _]](implicit T: MonadTrans[T], M: Monad[M]): Kleisli[({type l[a] = T[M, a]})#l, A, B] =n mapK[({type l[a] = T[M, a]})#l, B](ma => T.liftM(ma))n

接收一個MonadTrans，將M lift成了MT[M, B]，將A=>M[B] 變成了A => MT[M, B] （T.liftM(ma)乾的就是這個 ）

註：核心還是M[B] ~> MT[M, B]的自然變換，由T.liftM 提供

val k4: Kleisli[({type λ[a] = OptionT[List, a]})#λ, Int, Int] = k1.liftMK[OptionT] //將K[List, A, B] 變成了K[OptionT[List], A, B]n//很明顯是往內加層了 List(1) => List(Some(1))n

綜上，有那麼多trick去做面：

//一個無恥的例子ndef getIds: Future[List[Int]] = Future(List(1))ndef getBaba: Future[String/Option[String]] = Future(Some("Jack Ma").right[String])ndef getMenoy(baba: String): Future[Option[Int]] = Future(Some(100))ndef getWife(menoy: Int): Option[String] = Some("GAKKI")n//這個很關鍵ntype ResultT[A] = OptionT[({type l[X] = EitherT[Future, String, X]})#l, A]nnimplicit class ToResultT[A](a: Future[String/Option[A]]) {n def toT: ResultT[A] = OptionT[({type l[X] = EitherT[Future, String, X]})#l, A](EitherT[Future, String, Option[A]](a))n}nnval resT: ResultT[String] = for {n id <- getIds.map(_.headOption.right[String]).toTn baba <- getBaba.toTn menoy <- getMenoy(baba).map(_.right[String]).toTn wife <- (getWife(menoy).right[String]).point[Future].toTn} yield wifennval res: Future[/[String, Option[String]]] = resT.run.runn

ResultT 這個類型決定了你要什麼滑板鞋（你最後需要的類型），以上4個方法返回類型各不相同，我們並不是對其求個最小公倍數

上面做法的缺點是得自己手動做調整，變成同樣的Monad Stack，強行將不同ReturnType變為同一個type，而且上面寫的還不對（不要直接調right啊）。

或者先全轉為MT，再去做調整：

val getIdsT: ListT[Future, Option[Int]] = ListT[Future, Option[Int]](getIds.map(l => l.map(Some(_))))nval getBabaT: ResultT[String] = getBaba.toTndef getMenoyT(baba: String): OptionT[Future, Int] = OptionT[Future, Int](getMenoy(baba))ndef getWifeT(menoy: Int): OptionT[Future, String] = OptionT[Future, String](getWife(menoy).point[Future])nntype EitherTXF[F[_], A] = EitherT[F, String, A]ntype EitherTFA[A] = EitherTXF[Future, A] //不這麼寫|>=|的隱轉會找不到ntype ListTFA[A] = ListT[Future, A]nval ntlistT2EitherT = new (ListTFA ~> EitherTFA) {n def apply[A](fa: ListTFA[A]): EitherTFA[A] = EitherT[Future, String, A](fa.run.map(_.headOption.fold("error".left[A])(_.right[String])))n}nnval ntOptionTF2OTEitherTF: ({type λ[x] = OptionT[Future, x]})#λ ~> ({type λ[x] = OptionT[EitherTFA, x]})#λ =n Hoist[OptionT].hoist(implicitly[EitherTFA |>=| Future]) //那一段type lambda可以不寫，只是為了觀看nnval resT2 = for {n id <- Hoist[OptionT].hoist(ntlistT2EitherT).apply(OptionT[({type l[X] = ListT[Future, X]})#l, Int](getIdsT))n baba <- getBabaTn menoy <- ntOptionTF2OTEitherTF(getMenoyT(baba))n wife <- ntOptionTF2OTEitherTF(getWifeT(menoy))n} yield wifennval res2: Future[/[String, Option[String]]] = resT2.run.runn

以上，不管怎樣，都需要做手動的調整，殘念ながら

如果希望自動做，必須得使用些黑科技，type level的東西了。。。

救星出現

終於找到可以抱大腿的人了：m50d (Michael Donaghy) · GitHub

（事實證明亂戳shapeless的Contributors，還是有用的）

GitHub - m50d/scalaz-transfigure at e9c7ec44d3480e5e6faea3fbf063aa228d5a271f

前方略高能，可快速掃過。。。

transfigure的思路

0. 將Result Type寫出來，也就是你要的滑板鞋，不再是上面ResultT的形式，而是transfigureTo3[M1[_], M2[_], M3[_]]的方法類型參數形式

1. 將Monad Stack 如 M1[M2[A]] wrapper 成C1#C[D1#C[A]]的形式，C1/D1就是Context:

trait Context {n type C[_]n}n

n在伴生對象中為其加個輔助：type Aux[N[_]] = Context {type C[A] = N[A]}

至此，M1[A]， M2[A]變為了Context.Aux[M1]， Context.Aux[M2]我們用HList連起來

Context.Aux[M1] :: Context.Aux[M2] :: HNil

所以一個Monad Stack 有兩種表示方法：

M1[M2[A]] => C1#C[D1#C[A]] or C1 :: D1 :: HNil

前一種命名為*CS，後一種稱為Idx，就是我們最後要的Result Type

2.定義type GT[A <: Nat, B <: Nat], LE[A <: Nat, B <: Nat] 去標記A > B 和 A <= B

3. 定義type level function: IndexOf[Idx <: HList, A] 去做typelevel的操作，返回A在Idx這個HList中的index

註： IndexOf[C :: B :: A :: HNil, A].Out =:= _0

4. 組合IndexOf和LE&GT 為 IdxAndLtEq[Idx <: HList, A, B] & IdxAndGt[Idx <: HList, A, B]

使用IdxAndLtEq和IdxAndGt的Out類型存不存在（implicit instance(或稱type evidence) 找不找得到），定義：

LEIndexed[Idx <: HList, A, B] 和 GTIndexed[Idx <: HList, A, B]返回A, B在Idx中的順序是GT還是LE，也就是在前還是在後

implicitly[LEIndexed[Int :: String :: HNil, String, Int]] //編譯過nimplicitly[LEIndexed[Int :: String :: HNil, Int, String]] //不過n

5. 定義排序用的最簡組合子SelectionStep[Idx <: HList, C1 <: Context, D <: Context]使用上面的LEIndexed和GTIndexed來判斷是否需要交換C1和D在Idx中的位置

映射到value level的操作，就是一個nt, 若D在C1的前面，則C1#C[D#C[A]]交換順序只要用Traverse typeclass的sequence操作即可

6. 基於SelectionStep定義SelectLeast[Idx <: HList, L <: HList]，

L為某API返回的Return Type (如： Future[List[A]])轉為的Idx一樣的HList表示（Future[List[A]] => Context.Aux[Future] :: Context.Aux[List] :: HNil）

SelectLeast將以Idx為標準，將L中在Idx里排最前面的元素放到棧頂：F[G[H[A]]] => X[...[A]] X為F/G/H在Idx中的第一個

n若Idx為：OptionC :: EitherC :: ListC :: Nil ，L為：ListC :: OptionC :: EitherC :: Nil 則將List(Some(Right(5))) => Some(List(Right(5))) //Some是第一個，被放到棧頂

怎麼做到的？將L分解為C1 :: D :: L 直到C :: HNil，遞歸調用SelectionStep，交換出來

7. 終於可以定義排序了SelectionSort[Idx <: HList, L <: HList]，將L按照Idx的順序排列，層層調用SelectLeast，每次求出sub list的top就可以了

8.定義Normalizer，做補齊操作，按如下操作即可：

可見它只做point, join操作，加層和脫同層 （不符合上表的操作會編譯不過）

9. 組合Normalizer和SelectionSort為SortAndNormalizer 就可以做：

val sn = SortAndNormalizer[OptionContext :: ListContext :: HNil, HNil]nsn.trans.apply(5) ==== Some(List(5))nnval sn2 = SortAndNormalizer[OptionContext :: ListContext :: HNil, ListContext :: OptionContext :: HNil]nsn2.trans.apply(List(Some(5))) ==== Some(List(5))n

已經達到自動補齊的作用了

10. 偷師Haskell，採用Layer結構替換MonadTrans

trait Layer[M[_]] {n def monad[F[_]: Monad]: Monad[({ type L[A] = F[M[A]] })#L]nn def lift[N[_]](other: Layer[N]): Layer[({ type L[A] = N[M[A]] })#L] =n {n val self = thisn new Layer[({ type L[A] = N[M[A]] })#L] {n def monad[F[_]: Monad] = self.monad[({ type L[A] = F[N[A]] })#L](other.monad(Monad[F]))n }n }n}n

n這是個typeclass，我們需要為各種Monad實現Layer（就像各MT一樣），通過lift組合layers，通過monad方法返回最終的MT

11. 定義MonadStack 將L <: HList的context stack 轉為一個大MT

12.最後組合上面所有內容，定義ApplyBind，定義轉換：

trait SuperNaturalTransformation[-F[_], -G[_], +H[_]] {n def apply[A, B](f: F[A])(g: A => G[B]): H[B]n} n

先將L和R 轉換為Idx，獲取L和R的context stack LCS & RCS， 獲取Idx的MonadStack[Idx]

執行 LCS#C[A] >>= g: A => RCS#C[B] 返回 OCS#C[B]

而OCS就是Idx的context stack

並且要保證我們的I (M1[M2[A]]) === CS#C[A] (Leibniz)

type EitherFA[A] = /[String, A]nval baba: Future[EitherFA[Option[String]]] = getBabanval meony = baba.transfigureTo3[Future, EitherFA, Option](getMenoy)nval wife = (meony: Future[EitherFA[Option[Int]]]).transfigureTo3[Future, EitherFA, Option](getWife)nn(wife: Future[EitherFA[Option[String]]]).run.bimap(_ => (), r => println(r.getOrElse(""))) //=> GAKKI n

然而這犧牲了for/yield sugar， 殘念ながら（新版的transfigure 也支持不了for/yield，m50d大神還在努力）

（大神的代碼，我看了整整兩天，全是type level的（/TДT)/ ，5 years scala experience 寫的代碼就是不一樣）

最終策略

考慮實施，版本兼容（以及自身水平）等，一番糾結後，暫時得出如下todo list：

n1. 定義各種ReturnType的MT 隱轉 （暫時分為同步和非同步兩組吧） 並留好擴展口子

n2. 採用SortAndNormalizer 替代人工操作 （typelevel就是好），從而使用1定義的隱轉，保留for/yield （為何我如此介意這個？因為Monadic Programming，有機會再講這個話題）

n註：SortAndNormalizer並不能做到完全代替人工，它沒法做某層的NT，這個還得自己動手

n3. 為第三方編寫 Scalaz 各種typeclass的實現（如Traverse，Monad，因為SortAndNormalizer用到了sequence，point等）

n4. 使用shapeless的polymorphic function 去屏蔽各種庫的不同組合子（如Scala Future的sequence和twitter Future的join）

5. 將mathematic的東西，套個接地氣點的wrapper（這點，臨時想到的）

雖然不能全自動化，但至少將邏輯隔離開了

type Result[A] = Future[EitherFA[Option[A]]]ntype ResultStack = Future :/: EitherFA :/: Option :/: MNilnval sn1 = SortAndNormalizer.apply2[(Future :/: Option :/: MNil) --> ResultStack]nval sn2 = SortAndNormalizer.apply2[(Option :/: MNil) --> ResultStack]nnval resT3: ResultT[String] = for {n id <- sn1.trans(getIds.map(_.headOption)).toTn baba <- getBaba.toTn menoy <- sn1.trans(getMenoy(baba)).toTn wife <- sn2.trans(getWife(menoy)).toTn} yield wifennval res3: Result[String] = resT3.run.run n

我給SortAndNormalizer加了一點trick, 但是這麼寫idea里類型提示會徹底瓦特，所以若希望更好的查看類型提示，還是：

id <- (sn1.trans(getIds.map(_.headOption)): Result[Int]).toT //或nid: Int <- sn1.trans(getIds.map(_.headOption)).toTn

最後可以搞成這樣：

val resT3: ResultT[String] = for {n id <- getIds.map(_.headOption).to[ResultStack].toTn baba <- getBaba.toTn menoy <- getMenoy(baba).to[ResultStack].toTn wife <- getWife(menoy).to[ResultStack].toTn} yield wifennval res3: Result[String] = resT3.run.runn

留的擴展方式為：

abstract class ToRes[FromX[_], A](a: FromX[A]) { //不用trait是因為沒法帶構造參數n type From <: HListn type FromF[A] = FromX[A]n def to[Idx <: HList](implicit sn: SortAndNormalizer[Idx, From] {n type ICS = Context.Aux[FromF]n }): sn.OCS#C[A] = sn.trans(a)n}n//只要繼承ToRes，並寫上From的monad stack type 即可：nimplicit class ToResult2[A](a: Option[A]) extends ToRes(a) {n type From = Option :/: MNiln}nimplicit class ToResult[A](a: Future[Option[A]]) extends ToRes[({type l[X] = Future[Option[X]]})#l, A](a) {n type From = Future :/: Option :/: MNiln}n

能把From 這個抽象類型成員也弄掉就好了，可以基於StackHelper來弄

其實用別的框架也能解決這個問題，比如Scalaz-Stream，提供一個類型複合了很多Monad的語義，失敗時會怎樣，異常如何處理等，當然啦，這是另起爐灶了。

（有興趣還可以看看，評論區楊博大大推薦的 GitHub - ThoughtWorksInc/each: A macro library that converts native imperative syntax to scalazs monadic expressions）

End

一不小心流水賬了，感謝觀看，這真的是一個一直（至少兩個禮拜）在我心頭的事情，老實說，我並不覺得解決了問題，而是把問題以及能做的事給寫出來了，我們完全可以按照老套路去解值，寫業務，解值，寫業務。。。（這真的是在寫Scala，不是Java么？）

推薦閱讀：