在前面的讨论里我们提到*数据结构就是产生某种类型的最简化结构，比如：free monoid, free monad, free category等等。我们也证明了List[A]是个free monoid。我们再看看free monad结构Free的定义：scalaz/Free.scala
/** A free operational monad for some functor `S`. Binding is done using the heap instead of the stack,
* allowing tail-call elimination. */
sealed abstract class Free[S[_], A] {
...
/** Return from the computation with the given value. */
private[scalaz] case class Return[S[_], A](a: A) extends Free[S, A] /** Suspend the computation with the given suspension. */
private[scalaz] case class Suspend[S[_], A](a: S[Free[S, A]]) extends Free[S, A]
...
我们在上一篇里证明过Free就是free monad，因为Free是个Monad而且它的结构是最简单的了：
1、Free[S[_],A]可以代表一个运算
2、case class Return是一个数据结构。Return(a:A)代表运算结束，运算结果a存放在结构中。另一个意义就是Monad.point(a:A),把一个任意A值a升格成Free
3、case class Suspend也是另一个数据结构。Suspend(a: S[Free[S,A]])代表把下一个运算存放在结构中。如果用Monad.join(a: F[F[A]])表示，那么里面的F[A]应该是个Free[S,A]，这样我们才可能把运算结束结构Return[S,A](a:A)存放到Suspend中来代表下一步结束运算。
注意，Suspend(a: S[Free[S,A]])是个递归类型，S必须是个Functor，但不是任何Functor，而是map over Free[S,A]的Functor，也就是运算另一个Free[S,A]值。如果这个Free是Return则返回运算结果，如果是Suspend则继续递归运算。
简单来说Free是一个把Functor S[_]升格成Monad的产生器。我们可以用Free.liftF函数来把任何一个Functor升格成Monad。看看Free.liftF的函数款式就知道了：
/** Suspends a value within a functor in a single step. Monadic unit for a higher-order monad. */
def liftF[S[_], A](value: => S[A])(implicit S: Functor[S]): Free[S, A] =
Suspend(S.map(value)(Return[S, A]))
liftF可以把一个S[A]升格成Free[S,A]。我们用个例子来证明：
package Exercises
import scalaz._
import Scalaz._
import scala.language.higherKinds
import scala.language.implicitConversions
object freelift {
trait Config[+A] {
def get: A
}
object Config {
def apply[A](a: A): Config[A] = new Config[A] { def get = a}
implicit val configFunctor = new Functor[Config] {
def map[A,B](ca: Config[A])(f: A => B) = Config[B](f(ca.get))
}
} val freeConfig = Free.liftF(Config("hi config")) //> freeConfig : scalaz.Free[Exercises.freelift.Config,String] = Suspend(Exercises.freelift$Config$$anon$2@d70c109)
在上面的例子里Config是个运算A值的Functor。我们可以用Free.liftF把Config(String)升格成Free[Config,String]。实际上我们可以把这个必须是Functor的门槛取消，因为用Coyoneda就可以把任何F[A]拆解成Coyoneda[F,A]，而Coyoneda天生是个Functor。我们先看个无法实现map函数的F[A]：
trait Interact[+A] //Console交互
//println(prompt: String) then readLine 返回String
case class Ask(prompt: String) extends Interact[String]
//println(msg: String) 不反回任何值
case class Tell(msg: String) extends Interact[Unit]
由于Ask和Tell都不会返回泛类值，所以无需或者无法实现map函数，Interact[A]是个不是Functor的高阶类。我们必须把它转成Coyoneda提供给Free产生Monad：
Free.liftFC(Tell("hello")) //> res0: scalaz.Free.FreeC[Exercises.freelift.Interact,Unit] = Suspend(scalaz.Coyoneda$$anon$22@71423665)
Free.liftFC(Ask("how are you")) //> res1: scalaz.Free.FreeC[Exercises.freelift.Interact,String] = Suspend(scalaz.Coyoneda$$anon$22@20398b7c)
我们看看liftFC函数定义：
/** A version of `liftF` that infers the nested type constructor. */
def liftFU[MA](value: => MA)(implicit MA: Unapply[Functor, MA]): Free[MA.M, MA.A] =
liftF(MA(value))(MA.TC) /** A free monad over a free functor of `S`. */
def liftFC[S[_], A](s: S[A]): FreeC[S, A] =
liftFU(Coyoneda lift s)
Coyoneda lift s 返回结果Coyoneda[S,A], liftFU用Unapply可以把Coyoneda[S,A]转化成S[A]并提供给liftF。看看Unapply这段：
/**Unpack a value of type `M0[A0, B0]` into types `[a]M0[a, B0]` and `A`, given an instance of `TC` */
implicit def unapplyMAB1[TC[_[_]], M0[_, _], A0, B0](implicit TC0: TC[({type λ[α] = M0[α, B0]})#λ]): Unapply[TC, M0[A0, B0]] {
type M[X] = M0[X, B0]
type A = A0
} = new Unapply[TC, M0[A0, B0]] {
type M[X] = M0[X, B0]
type A = A0
def TC = TC0
def leibniz = refl
} /**Unpack a value of type `M0[A0, B0]` into types `[b]M0[A0, b]` and `B`, given an instance of `TC` */
implicit def unapplyMAB2[TC[_[_]], M0[_, _], A0, B0](implicit TC0: TC[({type λ[α] = M0[A0, α]})#λ]): Unapply[TC, M0[A0, B0]] {
type M[X] = M0[A0, X]
type A = B0
} = new Unapply[TC, M0[A0, B0]] {
type M[X] = M0[A0, X]
type A = B0
def TC = TC0
def leibniz = refl
}
好了。但是又想了想，一个是Functor的Interact又是怎样的呢？那Ask必须返回一个值，而这个值应该是个Free，实际上是代表下一个运算：
package Exercises
import scalaz._
import Scalaz._
import scala.language.higherKinds
object interact {
trait Interact[+A]
case class Ask[Next](prompt: String, n: String => Next) extends Interact[Next]
case class Tell[Next](msg: String, n: Next) extends Interact[Next] object interFunctor extends Functor[Interact] {
def map[A,B](ia: Interact[A])(f: A => B): Interact[B] = ia match {
case Tell(m,n) => Tell(m, f(n))
case g: Ask[A] => Ask[B](g.prompt, g.n andThen f)
}
}
所以Ask返回Next类型值，应该是个Free，代表下一个运算。