10月 6 2015

[开个大坑] Monad习作二则

虽说一直很懒不过发现神社已经有一年多的时间没有打理的时候还是很吃惊。想想真是惭愧，不过没有人来参拜果然还是没有什么动力更新呢（趴）。

说起来这一年里几乎没干什么值得一提的事情。一如往常地挖了好多的坑，填上的也没有几个。最大的收获或许就是Haskell终于感觉入了一点门，虽然依然不太敢用来写程序就是了。

那么！今天的主角自然就是Haskell了，准确的说应该就是这个名声在外的Monad（笑）。

诶等等别跑啊我还没说完呢！

在这里吾辈自然是不会说什么

Monad不过是自函子范畴上的幺半群而已，不懂的都是⑨！

之类的老梗啦ww 毕竟有关Monad的教程实在是太多了，所以这里吾辈只是简单谈谈对于Monad的理解。

TL;DR

Monad就是可编程的分号。

对于新手而言对这句话肯定是一头雾水吧ww 其实配合例子来看非常简单。

那么现在假设我们要做一个数字电子线路的仿真系统。让我们要求高一点，这个系统要有时延。于是我们可以用这么个类型来表达这些信息：

1	newtype Signal a = Signal { time :: Int, value :: a }

非常简单，对吧？这个类型实际上就可以看作附加了时间上下文（time :: Int）的值。

有了基本的表示类型，下面我们来表示一些基本元件。假设我们的需求很简单，只需要非门就够了：

1 2	notGate :: a -> Signal a notGate something = Signal { time = 1, value = not something }

对于任何传进来的信号，我们的非门将它附加一个非门时延，然后将输入取反。

那么现在问题来了。这个非门如何处理已经带有一个时延的信号？当然，我们在创建基本类型的时候用了Record Syntax，所以可以构造这样一个函数，对每个Signal a，将其中的value送给非门，将时延相加。于是可以这样：

1
2
3

bind :: Signal a -> (a -> Signal b) -> Signal b
bind (Signal t s) f = let r = f s
                      in r { time = time r + t }

到这里，其实你已经实现了Monad的核心了。剩下的无非是实现return。对于普通的值，我们希望它的时延为0:

instance Monad Signal where
truereturn a = Signal 0 a
true(Signal t s) >>= f = let r = f s
true                in r { time = time r + t }

就是这么简单。现在我们可以享受Haskell的do语法糖了

delay2 :: a -> Signal a
delay2 a = do
truet <- notGate a
truenotGate t

你看，Monad不过也就是这么个小儿科的东西。它只不过是一种保持你所定义的类型所附带的额外信息的结构罢了。现在再回想一下前面那句“Monad就是可编程的分号”是不是感觉明白了很多呢。

P.S. 关于为什么只实现了非门，其实是由于这种模拟方法处理时间有一点麻烦… 例如与门，就需要处理时间同步的问题。这里就不涉及了。

下面放上最初的两个习作，也正是实现了这两种Monad吾辈才感觉差不多理解了Monad。下一步就要去研究Monad Transformer了，是个更大更深的坑呢。

-- Monad implemented here.
-- beacuse since GHC 7.10 there must be
-- Functor => Applicative => Monad
-- so we have to build it from scratch
newtype M a = M { time :: Int, value :: a } 
            deriving (Show, Eq)

instance Functor M where
    f `fmap` a = a { value = f (value a) }

instance Applicative M where
    pure = M 0
    (M t f) <*> s = fmap f (s { time = time s + t} )

instance Monad M where
    return = pure
    (M t s) >>= f = let r = f s
                    in r { time = time r + t}


-- A more complicated one
newtype T a = T { runT :: Int -> a }

instance Monad T where
    return a = T $ const a
    x >>= f = T $ \t -> runT (f (runT x t)) t
    -- x :: (Int -> a)
    -- f :: a -> (Int -> a)

instance Applicative T where
    pure = return
    (T f) <*> x = T $ \t -> f t (runT x t)

instance Functor T where
    f `fmap` a = T $ \t -> f (runT a t)

关于为什么第二个实现是倒序的… 螃蟹卡农。嗯。

今天的幻想乡也很和平呢。

Phantom Shrine

Haskell, Programming Languages, Hardware, and Happy Hacking!

[开个大坑] Monad习作二则

TL;DR