Scalaz（31）－ Free ：自由数据结构－算式和算法的关注分离

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## Scalaz（31）－ Free ：自由数据结构－算式和算法的关注分离

1、一个二元函数 append: (A,A)=>A

2、一个A类型的初始值（零值）zero

Monoid必须遵循以下定律：

1、append函数的关联性associativity: 对任意A类型的x,y,z - append(x,append(y,z)) === append(append(x,y),z)

2、zero的同一律identity law: 对任意类型的x - append(zero,x) === append(x,zero)

``````1 sealed trait FreeMonoid[+A]
2 final case object Zero extends FreeMonoid[Nothing]
3 final case class Append[A](l: A, r: FreeMonoid[A]) extends FreeMonoid[A]``````

1::2::3::Nil >>> List(1,2,3)，如果A是个Monoid那么List[A]也是个Monoid，List[A]是个Free Monoid自由数据结构，我们看下面的示范：

``````1 def listOp[A](l: List[A]): FreeMonoid[A] = l match {
2     case Nil => Zero
3     case h :: t => Append(h,listOp(t))
4 }                                                 //> listOp: [A](l: List[A])Exercises.freestruct.FreeMonoid[A]
5 listOp(List(1,2,3))                               //> res0: Exercises.freestruct.FreeMonoid[Int] = Append(1,Append(2,Append(3,Zero
6                                                   //| )))``````

List是一个Free Monoid, 它的 Nil === Zero,  a ++ b === Append(a,b)。

1、point: A => M[A]

2、join: M[M[A]] => M[A]

3、map: (M[A], A => B) => M[B]

sealed trait Free[F[_],A]

final case class Return[F[_],A](a: A) extends Free[F,A]

join的输入类型是F[F[A]]，我们需要把Free[F,A]放在内里：

final case class Suspend[F[_],A](ffa: F[Free[F,A]) extends Free[F,A]

``````1 sealed trait Free[F[_], A]
2 final case class Return[F[_],A](a: A) extends Free[F,A]
3 final case class Suspend[F[_],A](ffa: F[Free[F,A]]) extends Free[F,A]``````

`````` 1 import scalaz.Functor
2 final case class Return[F[_],A](a: A) extends Free[F,A]
3 final case class Suspend[F[_],A](ffa: F[Free[F,A]]) extends Free[F,A]
4 sealed trait Free[F[_],A] {
5   def point(a: A) = Return[F,A](a)
6   def flatMap[B](f: A => Free[F,B])(implicit F: Functor[F]): Free[F,B] =
7     this match {
8       case Return(a) => f(a)
9       case Suspend(ffa) => Suspend[F,B](F.map(ffa)(fa => fa flatMap f))
10     }
11   def map[B](f: A => B): Free[F,B] = flatMap(a => Return[F,B](f(a)))
12   def join(ffa: F[Free[F,A]]): Free[F,A] = Suspend[F,A](ffa)
13
14 }``````

+ 关注

corcosa 14158人浏览