Haskell RankNTypes笔记

这个蛋疼的扩展的存在的必要性在于, 虽然Haskell默认泛型, 但是一个类型参数默认在一个特化的函数类型中也只能有一个特化

例如


length :: [a] -> Int

lengthInt = length :: [Int] -> Int

lengthChar = length :: String -> Int

当length这个函数作用于[Int]上时, 实际上length被特化成了lengthInt; 同理, length在String上会被特化为lengthChar

这个搞法通常是没有问题, 但是有时我们会发现需要两个特化

例如这个到处都是的例子


foo :: ([x] -> Int) -> ([a], [b]) -> (Int, Int)

foo f (a, b) = (f a, f b)

这看起来很美好, 但你们这样是不行的, 我建议你们再去学习一个

原因可能已经猜到了, 就是x这个类型参数不知道要被特化成a还是b

例如foo length [1] “a”里面, x应该是Int还是Char?

由于这个Haskell的设计失误(?), 我们需要RankNTypes, 并把foo的类型签名改成


foo :: (forall x. [x] -> Int) -> ([a], [b]) -> (Int, Int)

注意不要把这里的forall和其它的搞混啦, 可以参考这个SO问题

对了ST防止逃逸的办法也是相当有趣的, 感兴趣可以看看这个

Advertisements

一个40行的Lambda Exp evaluator

{-# LANGUAGE PatternGuards #-}
{-# LANGUAGE ViewPatterns #-}
type Identifier = String

data LambdaExp =
    Var {
        name :: Identifier
        } |
    Function {
        para :: Identifier,
        body :: LambdaExp
        } |
    App {
        func :: LambdaExp,
        arg :: LambdaExp
        }

eval :: LambdaExp -> LambdaExp
eval x@(Var n) = x
eval (Function p b) = Function p $ eval b
eval x@(App f a) = case f of
    Var _ -> x
    App _ _ -> let f' = eval f
                   a' = eval a
                in case f' of
                     Function p b -> replace b p a
                     _ -> App f' a'
    Function p b -> let b' = eval b
                        a' = eval a
                     in replace b' p a

--         expression   replacee      replacer
replace :: LambdaExp -> Identifier -> LambdaExp -> LambdaExp
replace x@(Var n) from to = if n == from
                               then to
                               else x
replace x@(Function p b) from to = if p == from
                                      then x
                                      else Function p $ replace b from to
replace (App f a) from to = let t x = replace x from to
                             in App (t f) (t a)

还实现了一个Show Class和Read Class就不发了

略trivial

YAME — Yet Another Monad Explaination

Monad有什么难的?自函子范畴上的一个幺半群而已。

理论上的Monad按照定义理解就可以了,而实际应用中Monad在我看来是一个带context的值(这个context可以存在,或尚未存在)。return函数返回一个无论context都包含有它的参数的Monad,(>>=)函数把一个函数apply到Monad内部的确切的值上,当内部还不存在确切值时,计算被暂停,等待一个确切值的出现。(有点类似currying/Cont/State的概念)或者可能不存在值,此时计算被取消了。

1.列表Monad

这个Monad的context尚未存在,在给定了一个下标context之后,能够获得一个确切的值。return函数返回一个只含一个元素的列表,使得这个monad的值被确定了(任何合法的context都会返回确定的值)。(>>=)把一个函数map进列表,但是这时monad的值由于缺乏context还无法确定,所以函数会在取得了确定的context之后起效(这是从lazy evaluation的角度上看;如果从strict evaluation上来说,因为无法确定以后哪个可能的值会被访问,所以必须把所有可能的值都用函数运算一遍)。如果把一个函数(>>=)进空列表,因为不存在值,所以计算被取消了。

2. Maybe Monad

这个Monad是一个有着两种context(Just或Nothing)的值。return返回一个只包含了给定的值的monad(Just x)。如果context是Just,那么(>>=)把函数map到Monad内部的值上。如果context是Nothing,那么根本就没有头发值,因此计算被取消。

3. Either Monad

这个Monad带着一个比Maybe信息更丰富的context(Left)。取值为Left [some info]或者Right [some value]。基本上和Maybe相同。

4. IO Monad

这个Monad的context尚未存在,在给定了某一个时刻的一个外部世界context后,能够获得一个确切的值。return返回一个无论外部世界的context如何都包含了给定参数的monad。(>>=)试图把一个函数apply到这个Monad内部的值上,但是由于缺少Context,值还处于量子态,所以函数等待到确定的值出现后再起效。

5. 函数Monad(a.k.a reader Monad)

这个Monad的context尚未存在,在给定了一个参数context后,能够获得一个确切的值。return返回一个无论参数context是什么都返回给定值的monad。f >>= g在g获得一个context前无法给f一个确切的参数,所以必须等g获得context后再和context一起feed f。为什么那么诡异,而不是像functor那样只是函数复合?因为类型系统呀。

instance Monad ((->) r) where
    (>>=) :: ((->) r a) -> (a -> ((->) r a)) -> ((->) r a)
    h >>= f = \w -> f (h w) w

6. State Monad

这个Monad的context尚未存在,在给定了一个state context后,能够获得一个确切的值。return理所当然返回一个无论state context如何都能返回一个固定值得monad。f >>= s试图把一个f函数map到s里面的值上,但是只能等state context出现塌缩为一个确切值后才能进行。由于f必须返回一个新的state(换言之,返回另一个运算),而且是在冬堡坍缩前返回,坍缩后,f应该返回一个(Value, State)。至于为什么是用原始运算的值作为f的参数产生新State然后用上一次运算的状态runState,没办法,这是Monad Laws决定的。(话说State这个名字有点误导,让人以为里面包含了一个State,实际上应该叫Transition)

所以其实如果GHC能够通过runState作出正确的推导,state monad的(>>=)可以定义为这样(不要搞混State和S!State指transition, S指literally state)

instance Monad (State s) where
    runState (state >>= f) s =
        let
            (midV, midS) = runState state s
            (newV, newS) = runState (f midV) midS
        in (newV, newS)

7. Cont Monad

这个Monad的context尚未存在,在给定了一个continuation context后,能够获得一个确切的值。别的基本和State Monad相同。这个Monad相当有意思,有时间专门写一篇笔记。

8. STM/ST Monad

这两个Monad存粹是为了用类型系统来限制用户的操作,没什么实际含义。

Haskell Maybe/Either Functor, Monad和Applicative用法的一些总结

注意这篇文章只针对Maybe/Either!

Functor: 需要操作的数据可能已经失败, 但是操作一定成功

假设我们是某运维, 我们接到了一份错误日志说某个地方有问题, 我们被指派去用某种方式(例如单元测试)检查那个据说会出问题的地方, 如果真的有问题就要写一份报告(如果没问题就不用写了), 我们的测试方法绝对可靠.

type TestMethod = Error -> Report
check :: TestMethod -> Maybe Bug -> Maybe Report
check method bug = fmap method bug
-- Alternative:
check method bug = method <$> bug

值得注意后一种写法, 虽然是Applicative模块用来把函数装入Applicative的, 但是在Functor上也相当好用(本身fmap和<$>就是别名而已嘛).

Monad: 需要操作的数据可能已经失败, 而且操作可能失败

在前一个场景的基础上, 如果我们的测试方法可能出现玄学… 测不出来当然不需要写报告咯

type TestMethod = Error -> Maybe Report
check :: TestMethod -> Maybe Bug -> Maybe Report
check method bug = bug >>= method

Applicative: 需要操作的数据可能已经失败, 而且操作可能不存在(什么鬼), 但是操作一定成功

如果上面的大人物的方法是不会出错的, 但是我们可能根本就不会被指示用哪种测试方法, 而且作为好吃懒做的员工我们没有指示决不会轻举妄动, 在这种情况下, 当然也不可能有报告啦

type TestMethod = Error -> Report
check :: Maybe TestMethod -> Maybe Error -> Maybe Report
check method bug = method <*> bug

Either其实类似, 返回的错误信息更丰富

Haskell: 如何compose一个二元函数与一个一元函数

大概是这样的, 逛SO的时候发现了这个帖子, 觉得相当有趣, 大意是要把nub和(++) compose成一个函数, 达到先连接再nub的效果

当然可以

f a b = nub $ a ++ b

但是这样很丑嘛

所以就可以使用

((nub .) .) (++)

于是我们来分析一下类型(为了避免混淆我适当地更改了类型变量名):

(.) :: (b -> c) -> (a -> b) -> (a -> c)
nub :: [a] -> [a]
(++) :: [a] -> [a] -> [a]

(nub .) :: (b -> [a]) -> (b -> [a])

((nub .) .) :: (c -> (b -> [a]) ) -> (c -> (b -> [a]) )

((nub .) .) (++) :: [a] -> ([a] -> [a])

类型演算麻烦就麻烦在要不停地换元容易把自己绕晕了表情

接下来再分析一下curry:

(.) = \f.(\g.(\a.f(ga)))
(++) = \a.(\b.a++b)
nub = \a.nub(a)

(.) nub = (\f.(\g.(\a.f(ga))))nub = \g.(\a.nub(ga)) = \g.(\a.nub(ga))

(.) ((.) nub) = (\f.(\g.(\a.f(ga))))(\g.(\a.nub(ga))) = \h.(\b.(\g.(\a.nub(ga)))(hb)) = \h.(\b.(\a.nub((hb)a)))

((.) ((.) nub)) (++) = (\h.(\b.(\a.nub((hb)a))))(++) = \b.(\a.nub(((++)b)a) = \b.(\a.nub(a++b))

因为lambda calculus还不够熟练所以就把很多中间步骤都写出来了还偷偷换了元orz

似乎要去补一补orz