3.20

语法分析monad

当处理字符串信息的时候经常需要将这一系列的字符串分析成想要的结构。这种结构通常是树状的，常常是上下文相关文法（context sensitive grammar），比如下面左侧 HTML 的字符串，使用下面的这种类型定义分析成右侧这种树状结构。


data Node = Tag String [Node]
					| Text String
					deriving (Show, Eq)
<html>
	<head>Hello</head>
	<body>Hello2</body>
</html>


Tag "html"
	[Tag "head"
		[Text "Hello"],
		Tag "body" [Text "hello2"]
	]

语法单元 token

more monad

语法分析monad, Stream monad, 异常monad, free monad, 续延monad(continuation monad) 处理流的Iteratee monad Pipie Conduit monad

Conduit

Your intended one-stop-shop for conduit functionality. This re-exports functions from many commonly used modules. When there is a conflict with standard functions, functions in this module are disambiguated by adding a trailing C (or for chunked functions, replacing a trailing E with CE). This means that the Conduit module can be imported unqualified without causing naming conflicts.

https://hackage.haskell.org/package/conduit-1.3.5/docs/Conduit.html

Type data ConduitT i o m r

https://hackage.haskell.org/package/conduit-1.3.5/docs/Data-Conduit.html#t:ConduitT

https://hackage.haskell.org/package/conduit-1.3.5/docs/src/Data.Conduit.Combinators.Unqualified.html#dropCE

reference counter 引用计数器

Parsec库


--接CountMonad1.hs
fact_cps1 :: Int -> Cont r Int
fact_cps1 0 = return 1
fact_cps1 n = do
	n1 <- fact_cps (n - 1)
	callCC $ \k ->
		let r - n * n1
		in if r > 10000
			then k 0
			else return r

callCC (call with current continuation)的函数：可以把续延的回调函数显示地引入进来供我们明确的调用，在调用k 0 以后，返回的结果直接就为0了，所以也有人称这个函数k为逃逸函数，因为程序相当于从中间计算的过程中跳出了，比如计算fact_cps1 8的时候这个函数就会发现超过10000了，所以后续的计算都不会计算了，接下来的计算直接会被终止，然后返回0


fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n - 1)

fact' n = let r = fact n in if r > 10000 then 0 els r

首先 callCC 是续延 Monad 的通用属性，也就是说任意一个 monad 转换器组合续延 Monad 以后就可以使用 callCC 函数, 这一点与 MonadState 还有 MonadWriter 类型类相似。其实 callCC 中的回调函数对于每步计算都是隐式存在的

需要手动处理句柄的资源与处理可能出现的输入输出异常，即便有bracket与finally函数


fact_cps2 :: Int -> Cont r Int
fact_cps2 n = do
	(goto, acc, num) <-
		callCC $ \k ->
			let f x y = k(f, x, y)
			in return (f, 1, n)
		if num == 1
			then return acc
			else goto (acc * num) (num - 1)
> runCont (fact_cps2 5) id
120

the c:


int fact(int n) {
	int acc = 1, num = n;
label:
	if (num == 1) {
		return acc;
	} else {
		acc = acc * num;
		n = n - 1;
		goto label;
	}
}

首先函数f的类型应该为Int → Int → ContT r Int

那么k的类型为((Int → Int → Cont r Int, Int, Int) → Cont r b0)

来看fact_cps2的计算过程

把facts_cps2的do语法糖去掉，就可以写成


fact_cps2' n =
	(callCC $ \k ->
		let f x y = k(f, x, y)
		in return(f, 1, n)) >>= \(goto, acc, num) ->
	if num == 1
		then return acc
		else goto (acc * num) (num - 1)

其中callCC的部分可以根据定义重新写：


callCC (\k -> let f x y - k (f, x, y) in return (f, 1, n))
{由定义callCC f = Const $ \h -> runCont (f \a -> Cont $ _ -> h a)}h，替换f}
= Cont $ \h -> runCont ((\k -> let f x y = k(f,x,y)
																in return (f, 1, n)(\a -> Cont $ \_ -> h a) h ))
//...

展开>> =运算并去掉续延Monad包装我们可以得到


import System.IO

main = do
	h <- openFile "foo.txt" ReadMode
	file <- hGetContents h 
	--let len = length file -- 由于惰性求值即便加了这行也没有用处
	hClose h
	putStrLn file

> :! echo this is the first line > foo.txt
> main
*** Exception: foo.txt: hGetContents: illegal operation (delayed read on closed handle)

这种情形下会得到运行时异常

它（下）是一个高阶函数，需要3个参数

合并累计结果与后面的值，它描述了计算是如何进行的

累积结果，累计结果可以看作是foldl维护的一个状态

传入的数据，这里是一个列表，可以看做成数据流


foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z0 xs0 = step z0 xs0
	where
		step z [] = z
		step z (x:xs) = step (f z x) xs


instance MonadTrans (Iteratee a) where
	lift m = Iteratee (m >>= runIteratee . return)

instance MonadIO m => MonadIO (Iteratee a m) where
liftIO = lift . liftIO

运行一个Iteratee的函数返回结果也十分容易，如果为Yield, 那么直接取得第一个参数，如果为Continue则说明这个Iteratee还需要一些输入，那么我们无法返回最后结果说明输入不够


run :: Monad m => Iteratee a m b -> m (Either Exc.SomeException b)
run i = do
	mStep <- runIteratee $ enumEOF ==< i
	case mStep of
		Error err -> return $ Left err
		Yield x_ -> return $ Right x
		Continue _ -> error "run: divergent iteratee"

run_ :: Monad m => Iteratee a m b -> m b
run_ i = run i >>= either Exc.throw return


type Enumerator a m b = Step a m b -> Iteratee a m b

从一个列表得到一个Enumerator


enumList :: Monad m => Int -> [a] -> Enumerator a m b
enumList n = loop
	where
		loop xs (Continue k)
		| not (null xs) =
			let (s1, s2) = splitAt n xs
			in k (Chunks s1) >>== loop s2
		loop _ step = returnI step

iteratee库中的API与我们之前讲解的几乎相同

第二版第二卷

惰性求值、类型推断

第15章惰性求值简介

函数应用function application

lamda抽象默认为右结合的，而函数应用默认为左结合的

15.2 ⊥ Bottom

Miranda (programming language)

Miranda is a lazy, purely functional programming language designed by David Turner as a successor to his earlier programming languages SASL and KRC, using some concepts from ML and Hope. It was produced by Research Software Ltd. of England and was the first purely functional language to be commercially supported.

https://en.wikipedia.org/wiki/Miranda_(programming_language)

15.3 表达式形态和thunk

弱首范式与范式

weak head normal form

延迟计算（suspended computation）

thunk:thunk

https://wiki.haskell.org/Weak_head_normal_form#:~:text=An expression is in weak,abstraction \x -> expression .

deepseq

在 Haskell 中使用 seq 与 deepseq 来严格求值是不同的。seq 通常只是称为严格求值，而 deepseq 称为深度严格求值或者完全严格求值（fully strict evaluation）。

求值策略（evaluation strategy）传值调用（call by value）

传名调用（call by name）这种求值方式是指在应用函数时不必计算参数的值，而是将参数直接替换到函数体当中

常序求值（normal order evaluation）：首先从左手边最外侧的不在lamda函数定义内部的式子开始化简

lazy evaluation惰性求值 strict evaluation严格求值

惰性求值不是一种固定的求值策略，而是结合了多种求值策略的优势的求值方法

15.7 严格模式匹配与惰性模式匹配

高秩类型 higher ranked type

高阶类型higher order type

化1：unification: 把等式两端的类型型通过替换转化为相同类型的过程称为化一

unifier

flip id :: y → (y → z) → z

函数的元arity一般所指的是函数需要多少个参数

明确全称量词（explicit universal quantification）


{-# LANGUAGE RankNTypes #-}
foo :: forall b c. (forall a . [a] -> [a]) -> ([b],[c]) -> ([b],[c])
foo f (xs, ys) = (f xs, f ys)

rank3 :: ((forall a. a->a) -> (Bool, Char)) -> (Char, Bool)
rank3 f = (\x -> (snd x, fst x)) (f id)

这些函数类型的秩实际上是forall所在的位置的想做嵌套的深度，也就是forall所在深度，如果一个类型中不包含有堕胎类型变量那么这个类型的秩为0

任何堕胎类型必须有明确的全称量词对其限定，否则就会引发类型错误，之前的多态函数如id, const等函数中的类型变量也有明确的限定，只是秩为1时可以省略，没有写出来

16.3.3 ST monad