# Scalaz（40）－ Free ：versioned up，再回顾

```def lift[F[_],G[_],A](fa: F[A])(implicit I: Inject[F,G]): Free.FreeC[G,A] =
Free.liftFC(I.inj(fa)) ```

```sealed abstract class Free[S[_], A] {
final def map[B](f: A => B): Free[S, B] =
flatMap(a => Return(f(a)))

/** Alias for `flatMap` */
final def >>=[B](f: A => Free[S, B]): Free[S, B] = this flatMap f

/** Binds the given continuation to the result of this computation. */
final def flatMap[B](f: A => Free[S, B]): Free[S, B] = gosub(this)(f)
...
/** Return from the computation with the given value. */
private case class Return[S[_], A](a: A) extends Free[S, A]

/** Suspend the computation with the given suspension. */
private case class Suspend[S[_], A](a: S[A]) extends Free[S, A]

/** Call a subroutine and continue with the given function. */
private sealed abstract case class Gosub[S[_], B]() extends Free[S, B] {
type C
val a: Free[S, C]
val f: C => Free[S, B]
}

private def gosub[S[_], B, C0](a0: Free[S, C0])(f0: C0 => Free[S, B]): Free[S, B] =
new Gosub[S, B] {
type C = C0
val a = a0
val f = f0
}```

```1 trait Free[S[_],A]
2 case class Return[S[_],A](a: A) extends Free[S,A]
3 case class FlatMap[S[_],A,B](fa: Free[S,A], f: A => Free[S,B]) extends Free[S,B]
4 case class Suspend[S[_],A](s: S[A]) extends Free[S,A]```

``` /** Suspends a value within a functor in a single step. Monadic unit for a higher-order monad. */
def liftF[S[_], A](value: S[A]): Free[S, A] =
Suspend(value)```

``` 1 object FreeADTs {
2   sealed trait Interact[+NextFree]
3   case class Ask[NextFree](prompt: String, onInput: String => NextFree) extends Interact[NextFree]
4   case class Tell[NextFree](msg: String, next: NextFree) extends Interact[NextFree]
5   sealed trait InteractInstances {
6     object InteractFunctor extends Functor[Interact] {
7       def map[A,B](ia: Interact[A])(f: A => B): Interact[B] = ia match {
9         case Tell(msg,next) => Tell(msg, f(next))
10       }
11     }
12   }
13   sealed trait InteractFunctions {
14     def ask[G[_],A](p: String, f: String => A)(implicit I: Inject[Interact,G]): Free[G,A] =
16     def tell[G[_],A](m: String)(implicit I: Inject[Interact,G]): Free[G,Unit] =
17       Free.liftF(I.inj(Tell(m,Free.pure(()))))
18   }
19   object Interacts extends InteractInstances with InteractFunctions
20 }```

2、ASTs:

```1 object FreeASTs {
3   import Interacts._
4   val interactScript = for {
7     _ <- tell(s"hello, \$first \$last")
8   } yield ()
9 }```

3、Interpreter:

```1 object FreeInterps {
3   object InteractConsole extends (Interact ~> Id) {
4     def apply[A](ia: Interact[A]): Id[A] = ia match {
6       case Tell(m,n) => println(m); n
7     }
8   }
9 }```

4、运行：

```1 object FreePrgDemo extends App {
2   import FreeASTs._
3   import FreeInterps._
4   interactScript.foldMapRec(InteractConsole)
5 }```

```  final def foldMapRec[M[_]](f: S ~> M)(implicit M: Applicative[M], B: BindRec[M]): M[A] =
B.tailrecM[Free[S, A], A]{
_.step match {
case Return(a) => M.point(\/-(a))
case Suspend(t) => M.map(f(t))(\/.right)
case b @ Gosub() => (b.a: @unchecked) match {
case Suspend(t) => M.map(f(t))(a => -\/(b.f(a)))
}
}
}(this)```

foldMapRec又调用了BindRec typeclass的tailrecM函数：

```/**
* [[scalaz.Bind]] capable of using constant stack space when doing recursive
* binds.
*
* Implementations of `tailrecM` should not make recursive calls without the
* `@tailrec` annotation.
*
* Based on Phil Freeman's work on stack safety in PureScript, described in
* [[http://functorial.com/stack-safety-for-free/index.pdf Stack Safety for
* Free]].
*/
////
trait BindRec[F[_]] extends Bind[F] { self =>
////

def tailrecM[A, B](f: A => F[A \/ B])(a: A): F[B]```

```sealed abstract class FreeInstances extends FreeInstances0 with TrampolineInstances with SinkInstances with SourceInstances {
new Monad[Free[S, ?]] with BindRec[Free[S, ?]] {
override def map[A, B](fa: Free[S, A])(f: A => B) = fa map f
def bind[A, B](a: Free[S, A])(f: A => Free[S, B]) = a flatMap f
def point[A](a: => A) = Free.point(a)
// Free trampolines, should be alright to just perform binds.
def tailrecM[A, B](f: A => Free[S, A \/ B])(a: A): Free[S, B] =
f(a).flatMap(_.fold(tailrecM(f), point(_)))
}
...```

```what's your first name?
tiger
chan
hello, tiger chan```

``` 1  sealed trait UserLogin[+A]  //非Functor 高阶类
2   case class CheckId(uid: String) extends UserLogin[Boolean]
5     def checkId[G[_]](uid: String)(implicit I: Inject[UserLogin,G]): Free[G,Boolean] =
6       Free.liftF(I.inj(CheckId(uid)))
9   }

2、ASTs：

``` 1   import Logins._
3   val loginScript = for {
6     _ <- if (idok) tell[InteractLogin](s"hi, \$uid") else tell[InteractLogin]("sorry, don't know you!")
12            else tell[InteractLogin](idok ? "sorry, no pass!" | "")

```1 object Dependencies {
2   trait UserControl {
3     val pswdMap: Map[String,String]
4     def validateId: Boolean
6   }
7 }```

``` 1   import Dependencies._
4     def apply[A](ia: Interact[A]): AuthReader[A] = ia match {
6       case Tell(msg,n) => println(msg); Reader {m => n}
7     }
8   }
11       case CheckId(uid) => Reader {m => m.validateId(uid)}
13     }
14   }
15   def or[F[_],H[_],G[_]](f: F~>G, h: H~>G) =
16     new (({type l[x] = Coproduct[F,H,x]})#l ~> G) {
17       def apply[A](ca: Coproduct[F,H,A]):G[A] = ca.run match {
18         case -\/(fg) => f(fg)
19         case \/-(hg) => h(hg)
20       }
21   }```

4、运算时把依赖注入：

``` 1 object FreeDemo extends App {
2   import FreeASTs._
3   import FreeInterps._
4   import Dependencies._
5   object AuthControl extends UserControl {
6     val pswdMap = Map (
7       "Tiger" -> "1234",
8       "John" -> "0000"
9     )
10    override def validateId(uid: String) =
11      pswdMap.getOrElse(uid,"???") /== "???"
12    override def validatePassword(uid: String, pswd: String) =
13       pswdMap.getOrElse(uid, pswd+"!") === pswd
14   }
15

```what's you id?
Tiger
hi, Tiger
0123
sorry, no pass!
...
what's you id?
foo
sorry, don't know you!
...
what's you id?
Tiger
hi, Tiger
1234
congratulations，Tiger```

```1   sealed trait Permission[+A]
2   case class HasPermission(uid: String, acc: Int) extends Permission[Boolean]
3   sealed trait PermissionFunctions {
4     def hasPermission[G[_]](uid: String, acc: Int)(implicit I: Inject[Permission,G]): Free[G,Boolean] =
5       Free.liftF(I.inj(HasPermission(uid,acc)))
6   }
7   object Permissions extends PermissionFunctions```

2、ASTs:

``` 1   import Permissions._
4   val authScript = for {
5     uid <- ask[T,String]("what's you id?",identity)
6     idok <- checkId[T](uid)
7     _ <- if (idok) tell[T](s"hi, \$uid")
8          else tell[T]("sorry, don't know you!")
10            else Free.point[T,String]("")
12            else Free.point[T,Boolean](false)
13       _ <- if (login) tell[T](s"congratulations，\$uid")
14            else tell[T](idok ? "sorry, no pass!" | "")
16            else Free.point[T,Int](0)
17     perm <- if (login) hasPermission[T](uid,acc)
18             else Free.point[T,Boolean](false)
19     _ <- if (perm) tell[T](s"you may use the system，\$uid")
20            else tell[T]((idok && login)  ? "sorry, you are banned!" | "")
21
22   } yield ()```

``` 1 object Dependencies {
2   trait UserControl {
3     val pswdMap: Map[String,String]
4     def validateId(uid: String): Boolean
5     def validatePassword(uid: String, pswd: String): Boolean
6   }
7   trait AccessControl {
8     val accMap: Map[String, Int]
9     def grandAccess(uid: String, acc: Int): Boolean
10   }
11   trait Authenticator extends UserControl with AccessControl
12 }```

3、Interpreters：

``` 1   import Dependencies._
4     def apply[A](ia: Interact[A]): AuthReader[A] = ia match {
6       case Tell(msg,n) => println(msg); Reader {m => n}
7     }
8   }
11       case CheckId(uid) => Reader {m => m.validateId(uid)}
13     }
14   }
16   object PermConsole extends (Permission ~> AuthReader) {
17     def apply[A](pa: Permission[A]): AuthReader[A] = pa match {
18       case HasPermission(uid,acc) => Reader {m => m.grandAccess(uid, acc)}
19     }
20   }
21   def or[F[_],H[_],G[_]](f: F~>G, h: H~>G) =
22     new (({type l[x] = Coproduct[F,H,x]})#l ~> G) {
23       def apply[A](ca: Coproduct[F,H,A]):G[A] = ca.run match {
24         case -\/(fg) => f(fg)
25         case \/-(hg) => h(hg)
26       }
27   }
28   def among3[F[_],H[_],K[_],G[_]](f: F~>G, h: H~>G, k: K~>G) = {
29     type FH[A] = Coproduct[F,H,A]
30     type KFH[A] = Coproduct[K,FH,A]
31     new (({type l[x] = Coproduct[K,FH,x]})#l ~> G) {
32       def apply[A](kfh: KFH[A]): G[A] = kfh.run match {
33         case -\/(kg) => k(kg)
34         case \/-(cfh) => cfh.run match {
35            case -\/(fg) => f(fg)
36            case \/-(hg) => h(hg)
37           }
38        }
39     }
40   }```

4、运算：

``` 1 object FreeDemo extends App {
2   import FreeASTs._
3   import FreeInterps._
4   import Dependencies._
5   object AuthControl extends Authenticator {
6     val pswdMap = Map (
7       "Tiger" -> "1234",
8       "John" -> "0000"
9     )
10    override def validateId(uid: String) =
11      pswdMap.getOrElse(uid,"???") /== "???"
12    override def validatePassword(uid: String, pswd: String) =
13       pswdMap.getOrElse(uid, pswd+"!") === pswd
14
15    val accMap = Map (
16      "Tiger" -> 8,
17      "John" -> 0
18    )
19    override def grandAccess(uid: String, acc: Int) =
20      accMap.getOrElse(uid, -1) > acc
21   }
24 //  interactScript.foldMapRec(InteractConsole)
25
26 }```

```what's you id?
Tiger
hi, Tiger
1234
congratulations，Tiger
3
you may use the system，Tiger```

Beautiful! 下面是本文示范的完整代码：

```  1 package demo.app
2 import scalaz._
3 import Scalaz._
4 import scala.language.implicitConversions
5 import scala.language.higherKinds
6 import com.sun.beans.decoder.FalseElementHandler
7 import java.rmi.server.UID
8
10   sealed trait Interact[NextFree]
11   case class Ask[NextFree](prompt: String, onInput: String => NextFree) extends Interact[NextFree]
12   case class Tell[NextFree](msg: String, next: NextFree) extends Interact[NextFree]
13   sealed trait InteractInstances {
14     object InteractFunctor extends Functor[Interact] {
15       def map[A,B](ia: Interact[A])(f: A => B): Interact[B] = ia match {
17         case Tell(msg,next) => Tell(msg, f(next))
18       }
19     }
20   }
21   sealed trait InteractFunctions {
22     def ask[G[_],A](p: String, f: String => A)(implicit I: Inject[Interact,G]): Free[G,A] =
24     def tell[G[_]](m: String)(implicit I: Inject[Interact,G]): Free[G,Unit] =
25       Free.liftF(I.inj(Tell(m,Free.pure(()))))
26   }
27   object Interacts extends InteractInstances with InteractFunctions
28
29   sealed trait UserLogin[+A]  //非Functor 高阶类
30   case class CheckId(uid: String) extends UserLogin[Boolean]
33     def checkId[G[_]](uid: String)(implicit I: Inject[UserLogin,G]): Free[G,Boolean] =
34       Free.liftF(I.inj(CheckId(uid)))
37   }
39   sealed trait Permission[+A]
40   case class HasPermission(uid: String, acc: Int) extends Permission[Boolean]
41   sealed trait PermissionFunctions {
42     def hasPermission[G[_]](uid: String, acc: Int)(implicit I: Inject[Permission,G]): Free[G,Boolean] =
43       Free.liftF(I.inj(HasPermission(uid,acc)))
44   }
45   object Permissions extends PermissionFunctions
46 }
47 object FreeASTs {
49   import Interacts._
50   val interactScript = for {
53     _ <- tell(s"hello, \$first \$last")
54   } yield ()
57   val loginScript = for {
60     _ <- if (idok) tell[InteractLogin](s"hi, \$uid") else tell[InteractLogin]("sorry, don't know you!")
66            else tell[InteractLogin](idok ? "sorry, no pass!" | "")
68   import Permissions._
71   val authScript = for {
72     uid <- ask[T,String]("what's you id?",identity)
73     idok <- checkId[T](uid)
74     _ <- if (idok) tell[T](s"hi, \$uid")
75          else tell[T]("sorry, don't know you!")
77            else Free.point[T,String]("")
79            else Free.point[T,Boolean](false)
80       _ <- if (login) tell[T](s"congratulations，\$uid")
81            else tell[T](idok ? "sorry, no pass!" | "")
83            else Free.point[T,Int](0)
84     perm <- if (login) hasPermission[T](uid,acc)
85             else Free.point[T,Boolean](false)
86     _ <- if (perm) tell[T](s"you may use the system，\$uid")
87            else tell[T]((idok && login)  ? "sorry, you are banned!" | "")
88
89   } yield ()
90 }
91 object FreeInterps {
93   object InteractConsole extends (Interact ~> Id) {
94     def apply[A](ia: Interact[A]): Id[A] = ia match {
96       case Tell(m,n) => println(m); n
97     }
98   }
99   import Dependencies._
102     def apply[A](ia: Interact[A]): AuthReader[A] = ia match {
104       case Tell(msg,n) => println(msg); Reader {m => n}
105     }
106   }
109       case CheckId(uid) => Reader {m => m.validateId(uid)}
111     }
112   }
113   object PermConsole extends (Permission ~> AuthReader) {
114     def apply[A](pa: Permission[A]): AuthReader[A] = pa match {
115       case HasPermission(uid,acc) => Reader {m => m.grandAccess(uid, acc)}
116     }
117   }
118   def or[F[_],H[_],G[_]](f: F~>G, h: H~>G) =
119     new (({type l[x] = Coproduct[F,H,x]})#l ~> G) {
120       def apply[A](ca: Coproduct[F,H,A]):G[A] = ca.run match {
121         case -\/(fg) => f(fg)
122         case \/-(hg) => h(hg)
123       }
124   }
125   def among3[F[_],H[_],K[_],G[_]](f: F~>G, h: H~>G, k: K~>G) = {
126     type FH[A] = Coproduct[F,H,A]
127     type KFH[A] = Coproduct[K,FH,A]
128     new (({type l[x] = Coproduct[K,FH,x]})#l ~> G) {
129       def apply[A](kfh: KFH[A]): G[A] = kfh.run match {
130         case -\/(kg) => k(kg)
131         case \/-(cfh) => cfh.run match {
132            case -\/(fg) => f(fg)
133            case \/-(hg) => h(hg)
134           }
135        }
136     }
137   }
138 }
139 object Dependencies {
140   trait UserControl {
141     val pswdMap: Map[String,String]
142     def validateId(uid: String): Boolean
143     def validatePassword(uid: String, pswd: String): Boolean
144   }
145   trait AccessControl {
146     val accMap: Map[String, Int]
147     def grandAccess(uid: String, acc: Int): Boolean
148   }
149   trait Authenticator extends UserControl with AccessControl
150 }
151 object FreeDemo extends App {
152   import FreeASTs._
153   import FreeInterps._
154   import Dependencies._
155   object AuthControl extends Authenticator {
156     val pswdMap = Map (
157       "Tiger" -> "1234",
158       "John" -> "0000"
159     )
160    override def validateId(uid: String) =
161      pswdMap.getOrElse(uid,"???") /== "???"
162    override def validatePassword(uid: String, pswd: String) =
163       pswdMap.getOrElse(uid, pswd+"!") === pswd
164
165    val accMap = Map (
166      "Tiger" -> 8,
167      "John" -> 0
168    )
169    override def grandAccess(uid: String, acc: Int) =
170      accMap.getOrElse(uid, -1) > acc
171   }
174 //  interactScript.foldMapRec(InteractConsole)
175
176 }```

0 条评论

## 相关文章

1595

### Akka（7）： FSM：通过状态变化来转换运算行为

在上篇讨论里我们提到了become/unbecome。由于它们本质上是堆栈操作，所以只能在较少的状态切换下才能保证堆栈操作的协调及维持程序的清晰逻辑。对于比...

6108

1777

3357

### 算法导论第十九章 斐波那契堆

《算法导论》第二版中在讨论斐波那契堆之前还讨论了二项堆，但是第三版中已经把这块的内容放到思考题中，究极原因我想大概是二项堆只是个引子，目的是为了引出斐波那契...

2298

4857

745

### HLS综合策略

Loop：rolled00 Array: BRAM Struct：被分解为成员变量 操作符：硬件核 优化策略 The Initial Optimization...

2027

8657

391