Scalaz(31)- Free :自由数据结构-算式和算法的关注分离

   我们可以通过自由数据结构(Free Structure)实现对程序的算式和算法分离关注(separation of concern)。算式(Abstract Syntax Tree, AST)即运算表达式,是对程序功能的描述。算法则是程序的具体运算方式(Interpreter),它赋予了算式意义。下面我们先用一个例子简单解释何为算式、算法:

用一个简单的表达式 1+2+3,这个表达式同时包含了算式和算法:运算表达式是 a Op b Op c, 算法是:Int加法,a,b,c为Int, oP为Int+。那么我们可不可把它分解成算式和算法呢?我们可以先把算式推导出来:Op(a,Op(b,c))。我们可以在算法里对Op即a,b,c进行多种定义,即通过这些定义我们能赋予算式不同的意义。这个例子可以形象的描述算式、算法关注分离的全过程:抽象描述我们要运算的程序,定义具体运算方式可以分开进行。

实际上 1+2+3可以说是一种Monoid操作。我们看看是否能从中推导出Free Monoid,一个Monoid自由数据结构用来实现Monoidal操作的算式、算法分离关注。针对任意基本类型A的Monoid定义如下:

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+2+3 === 1+(2+(3+0))。它的算式可以是这样:append(x,append(y,append(z,zero)))。那么我们应该可以得到这样的Free Monoid自由数据结构:

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)。

同样,我们可以从Monad的特性操作函数来推导Free Monad自由数据结构。我们可以用以下操作函数来构建一个Monad M[_]:

1、point: A => M[A]

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

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

(point+flatMap组合同样能构建Monad)

Free Monad是基于类型构建器Functor F[_]的Free Monoid, 所以Free Monad的定义应该是这样的:

sealed trait Free[F[_],A]

我们可以直接把point转换成case class:

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]

我们现在可以猜测Free Monad的自由数据结构定义如下:

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]

我们只需证明用以上结构可以实现Monad的所有特性操作函数,那么这个Free就是一个用Functor F产生Monad的Monad构造器,一个最简单结构的Monad构造器,即Free Monad:

 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 }

这个Free自由数据结构足够支持我们实现point,flatMap,map,join这几个Monad特性操作函数,所以Free是个Free Monad。

如果Free是个Free Monad,我们可以把Free[F,A]里的F[A]当做Program[Commands]。即我们可以用命令集Commands来独立描述程序Program。最终的程序Program是不会产生副作用的,所以容许最大限度的函数组合(function composition)。对Program的具体运算方法则可以独立分开实现。我们将在下次讨论中着重介绍Free Monad的实际应用方式:AST和Interpreter的实现过程。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏zhisheng

#每日一题#4

4、已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是() A、head(tail(LS)) B、tail(...

3346
来自专栏CaiRui

网络体系结构

1.通信协议就是在网络信息传输过程中,数据通信格式的约定,是在网络中规定信息怎样流动的一组规则。它包括控制格式、分时和纠错的有关内容,它的基本功能是对外来信息进...

1955
来自专栏算法channel

1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。

550
来自专栏数据科学与人工智能

Python语言做数据探索教程

本文总结Python语言做数据探索的知识。 类似R语言做数据探索,利用Python语言做数据探索。 1 数据导入 2 数据类型变换 3 数据集变换 4 数据排序...

3525
来自专栏懒人开发

(6.4)James Stewart Calculus 5th Edition:Work

牛顿第二定律: F = ma (这里 dv = ds/dt, da=dv/dt) 于是有

892
来自专栏窗户

最多7次比较解决5个数的排序问题的解法

  这一篇是上一篇《12(13)个球1个不同重量称3次称出的详细分析》的姊妹篇,分析手段同出一辙,此题源于《算法导论》。   和上面一样分析,5个数的排列总共有...

19010
来自专栏算法修养

整数划分总结

整数划分问题: 笼统上说就是将一根整数划分成若干个整数之和的方案数。整数划分很多不同的问法,也有隐晦的问法。比如n个苹果放到m个盘子里,比如n个砖块堆成m个...

2916
来自专栏深度学习入门与实践

【原】Learning Spark (Python版) 学习笔记(四)----Spark Sreaming与MLlib机器学习

本来这篇是准备5.15更的,但是上周一直在忙签证和工作的事,没时间就推迟了,现在终于有时间来写写Learning Spark最后一部分内容了。   第10-1...

24310
来自专栏Vamei实验室

Python基础08 面向对象的基本概念

Python使用类(class)和对象(object),进行面向对象(object-oriented programming,简称OOP)的编程。 面向对象的最...

2027
来自专栏潇涧技术专栏

Python Algorithms - C2 The basics

本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。

852

扫码关注云+社区