《函数式编程精粹》(3) Functional Design
Functional Design
Core Principles of FP design
Functions
types
composition
Function as parameters
Abstraction,Dependency injection
Patial application, Continuation, Folds
Chaining functions
Error handling, Async
Monads
Deealing with wrapped data
Lifting, Functors
Validation with Applicatives
Aggregation data and operations
Monoids
热身：When is Cheryl’s Birthday ?
题目
1.Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl gives them a list of 10 possible dates.
May 15 May 16 May 19
June 17 June 18
July 14 July 16
August 14 August 15 August 17
2.Cheryl then tells Albert and Bernard separately the month and the day of her birthday respectively.
6.So when is Cheryl’s birthday?
这是一个很经典的逻辑题，我们可以用 Functional 的思想来表达。
基本语素
最高层说明
形式化条件
3.Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard does not know too.
4.Bernard: At first I didn’t know when Cheryl’s birthday is, but I know now.
5.Albert: Then I also know when Cheryl’s birthday is.
Monad
the most powerful idea of computing
Monad 是范畴论里的概念，很简单，很抽象，很难理解。
历史演进：
最初是研究语言语义的，后来发现可以用来程序的组合方式，逐步进入到函数式编程领域里了。
各种语言的学习曲线（图）。
Monad 可以说是是 Haskell 语言第一个门槛。
Problem
投票系统，明星投票。
web server。
异步 request。
无阻塞。
控制流流程不清楚，很多中间状态并不是领域中的状态，而是我实现层次上为了实现异步方式增加的状态。
erlang 的解决方案：
每个用户启动一个并发体
receive..模式
WE WANT
这是我们接下来要实现的语言。
底层是异步的，顶层是顺序化编程。
Monad From the First Principle
An Example
这个时候，函数之间是可以组合的。
提炼组合方式
Debugging
有 io 就不是一个纯的 fuction，有副作用。
我们把副作用外化，变成一个指示。
我们可以把函数变成：
问题来了，原来返回值可以直接组合，现在没法组合了，程序就乱写了：
if ..... else ....
就变成这样的编程方法了。
我们希望还能 compose。
More glue is required
只有这样才能组合。
或者函数签名还需要修改成：
可以通过原来的 compose 来组合（最平凡的 compose）
代价：为了功能，增加了参数和返回值的复杂性。
这种写法就丧失了伸缩性，又很繁琐。
lift/bind(我能不能把这个工作变成自动的)
lift：把一个类型 lift 到另一个类型，然后 compose。
自动 lift 到 =====>
尝试写一下 lift 函数：
先 lift，再组合：
思考问题的时候，把函数当成一个整体。
在函数式编程里 Lift 通常叫做 bind。目的就是为了组合。
unit (类型 lift)
or
这样程序写出来之后，层次就非常漂亮了（清晰）。将一个层次 Lift 到另外一个层次。
Abstractions
lift
convert a simple function into debuggable function
bind
converts a debuggable function into a composable form
unit
converts a simple value into the format required for debuggable, by placing it in a container.
TWO WORLDS
EXERCISE:MAYBE MONAD & LIST MONAD
maybe monad 和之前讲的 option 是一个概念。
可以做规范错误处理。
在 maybe 的世界里面，function 是什么类型？
MONOIDS(幺半群)
概念来自于范畴论。
直观感受
数学上的概念不多讲，我们直观的感受一下是什么意思:
加法
1).
1+2 = 3
2).
1+(2+3) = (1+2) + 3
3).
1+0 = 1
0+1 = 1
1).Object 封闭。整数的加法还是整数，它们的性质是一样的。
2).结合律。为什么满足结合律？
这就是定义，我定义了"+"这个 opertion 就一定是这样的，是人为定义的。
3).幺元。
0 这个对象比较特殊。集合里有个特殊的元素，这个元素和任何元素计算结果都不变。这个集合就是幺半群。
通过这样的性质组合我们的程序可以很好的控制复杂性。
乘法：
乘法也满足上面的性质。
乘法的幺元就是 1.
max
满足 1），2）
幺元是什么？怎么变成幺半群？
字符串加法
"a"+"b"="ab"
满足 1),2)
幺元是空字符串
注：不一定满足交换律。满足交换律的叫做交换幺半群。
define
https://fsharpforfunandprofit.com/posts/monoids-without-tears/
But now we have something much more abstract, a set of generalized requirements that can apply to all sorts of things:
You start with a bunch of things, and some way of combining them two at a time.
Rule 1 (Closure): The result of combining two things is always another one of the things.
Rule 2 (Associativity): When combining more than two things, which pairwise combination you do first doesn’t matter.
Rule 3 (Identity element): There is a special thing called “zero” such that when you combine any thing with “zero” you get the original thing back.
这个东西看起来好像没啥用，但其实对于设计上指导意义非常大。
把一个问题领域计算化。一旦找到之后就很舒服了。
比如：顺序没有关系，Monoid 就可以 reduce，很好的进行并行计算。
Maybe
再来看 Maybe,发现是满足结合律，unit 就是幺元。
A CONTINUATION-BASED DSL
基于这个 Monad 做一个编程语言。
Continuation
Essence of control Flow:
concurrency,exception,async callbacks,continue....
控制流在什么地方？
我们在编程的时候，通常只关注数据。控制流我们看不见，控制流在什么地方？
假设我每个代码都加一个标签的话。。。
其实这个控制流是硬件决定的，我们看不见。比如我们永远没有办法在 C 语言层面上新增一个控制流。除非 C 语言的作者新增一个关键字。
比如，这个控制流就是我们控制不了的。我们如何把控制流捕获到交给我们自己做？
简单的，我们可以利用之前讲的 compose
Continuation passing style(CPS)
按照这个思路把 func_a 也改一下：
发现个问题，func_b 就传不到 func_a 里面去了。
“任何问题都可以通过增加一层来解决”：
what we need:
现在控制流是通过 cont_a 传进去了，我自己可以控制了。
convert func_c to CPS:
还需要增加 cont_b：
总体：
现在是我起了个名字，但是还拿不到，不能管理它
把 fn_4 也变成一个 cps
CONT 化
思考一下函数调用过程。
在这里面整个控制流是我控制的，而不是编译器控制的，这个是最重要的区别。
如何组合呢？
现在我们考虑组合的问题。
原来可以通过 compose 方法来组合，现在如何通过 compose 方法来组合呢？
用类型去思考：
原来 func_a 可以说是“看得见摸不着”的我们要把 currying 一把，变成一个"看得见摸得着"的。
那么 func_a 的参数应该是什么？返回值应该是什么？
参数应该是 integer(), 返回值应该是一个函数，这个函数的参数是 Cont。
变换后：
我们把 func_a，func_b，func_c 都改成这种方式，再思考下如何串起来。
先手工串起来：
首先
C1 是什么类型呢？
bind / unit
一定要在类型的角度去想，不要去想细节。
bind 简单实现
bind 正确实现
两种实现执行结果是一样的。
bind 简单实现，bind 正确实现 的区别：bind 简单实现就立即执行了，bind 正确实现只是描述，需要的时候才执行，将整个计算的描述和执行分离。
application
compose
通过加打印的方式可以观察到，func_a 和 func_b 的执行是在最后调用的时候。
体会和 bind 简单实现版本的区别：
这种思想就包含了之前提到的
partial application
lazy evaluation
m_chain()
type:
[integer() -> Cont(integer())] -> integer() -> Cont(integer())
把一串 Mf 变成一个整体的 Mf
halt()
Continuation 如果只能定义出来，不能管理就没有意义。
基于 m_chain，我们需要把 Cont 都拿出来并且管理。
这就是最简单的控制流。 halt 就相当于操作系统里的 exit
bounce()
先猜一下这个函数是做什么的？
先运行一下试试。
bounce()就像断点一样。先不执行，把函数返回回来，需要执行的时候再执行。
trampoline()
它的本意是释放堆栈的。
mark()
可以实现替换中间计算结果，传入到后面的 Cont。
m_if()
如何设计 if 的原语呢？首先还是考虑类型。
那么 m_if 的函数签名是什么呢？
m_if 肯定也是个能组合的。
Cond, Then, Else 分别是什么类型？
也是有 2 种写法
两种写法结果是一样的。
还未添加个人签名 2019.04.11 加入
还未添加个人简介
评论