如何在Haskell中将功能DSL转换为Monad？

Question

以下Haskell代码是一个简单的"控制台IO"DSL:

data Ap a = Ap { runAp :: ApStep a }

data ApStep a =
    ApRead   (String -> Ap a)
  | ApReturn a
  | ApWrite  String (Ap a)

ioRead    k   = Ap $ ApRead k
ioReturn  a   = Ap $ ApReturn a
ioWrite   s k = Ap $ ApWrite s k
ioWriteLn s   = ioWrite (s ++ "\n")

apTest =
  ioWriteLn "Hello world!" $
  ioRead $ \i ->
  ioWriteLn ("You wrote [" ++ i ++ "]") $
  ioReturn 10

uiRun ap =
  case runAp ap of
    ApRead k     -> uiRun (k "Some input")
    ApReturn a   -> return a
    ApWrite s k  -> putStr s >> uiRun k

run = uiRun apTest

它工作正常然而我想使用monad而不是使用$编写"应用程序"apTest.换句话说,像这样:

apTest = do
  ioWriteLn "Hello world!"
  i <- ioRead
  ioWriteLn $ "You wrote [" ++ i ++ "]"
  return 10

问题是代码抵制了我将"功能样式"DSL转换为monad的所有尝试.所以问题是如何为这个DSL实现一个monad实例,它允许你编写apTest monad样式而不是"$"样式？

Answer 1

当然这是一个单子.事实上,将它表达为一个免费的monad会更简单[1],但我们可以使用你所拥有的东西.

下面是我们如何知道这是一个单子:如果你有一个类型data Foo a = ...,其中Foo代表某种递归树结构的地方a,那么你有一个单子上唯一发生在叶. return a是"给我一棵由一片叶子组成的树a",并且>>=是"叶子上的替代".

在你的情况下Ap是树结构在哪里

• ApReturn a 是一片叶子

• 有两种内部节点

  1. ApRead 是一个没有标签的节点,每个类型的值都有一个后代 String
  2. ApWrite是一个由a标记的节点,String只有一个后代从中脱离

我在下面的代码中添加了monad实例. return只是AppReturn(加上Ap包装). >>=只是递归地申请>>=和替换叶子.

有关未来的几点提示

1. 在顶级的所有内容上放置类型签名.您的同事,Stack Overflow评论者和您未来的自我感谢您.
2. 该Ap包装是不必要的.考虑删除它.

请享用!

data Ap a = Ap { runAp :: ApStep a }

data ApStep a =
    ApRead      (String -> Ap a)
    |   ApReturn    a
    |   ApWrite     String (Ap a)

ioRead    k   = Ap $ ApRead k
ioReturn  a   = Ap $ ApReturn a
ioWrite   s k = Ap $ ApWrite s k
ioWriteLn s   = ioWrite (s ++ "\n")

apTest =
  ioWriteLn "Hello world!" $
  ioRead $ \i ->
  ioWriteLn ("You wrote [" ++ i ++ "]") $
  ioReturn 10

uiRun ap =
  case runAp ap of
    ApRead k        -> uiRun (k "Some input")
    ApReturn a      -> return a
    ApWrite s k     -> putStr s >> uiRun k

run = uiRun apTest

instance Monad Ap where
    return = Ap . ApReturn
    Ap (ApReturn a) >>= f = f a
    Ap (ApRead r) >>= f = Ap (ApRead (\s -> r s >>= f))
    Ap (ApWrite s a) >>= f = Ap (ApWrite s (a >>= f))

monadRead = Ap (ApRead (\s -> return s))
monadWrite s = Ap (ApWrite s (return ()))
monadWriteLn = monadWrite . (++ "\n")

apTestMonad = do
  monadWriteLn "Hello world!"
  i <- monadRead
  monadWriteLn $ "You wrote [" ++ i ++ "]"
  return 10

monadRun = uiRun apTestMonad

[1] http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html

Answer 2

我的东西是monad吗？

我没有任何具体的帮助,但我有一些总体指导,这对评论来说太长了.当我的直觉告诉我我想做一些事情的时候Monad,我做的第一件事就是用笔和一张纸坐下来问我自己,

不过,我的东西真的是单身吗？

事实证明,很多时候事实并非如此 - 只是我的直觉想要快速地加入这个潮流.Monad如果你的东西不是monad,你就不能很好地为你的东西创建一个实例.这是我在将我的东西称为monad之前需要涵盖的三件事的清单.

当我确定我的东西是 monad时,我通常也会在这个过程中意外地想出为我的东西创建monad实例所需的一切,所以这不是一个严谨无用的练习.这实际上将为您提供为您的东西创建monad实例所需的两个操作的实现.

什么是monads？

为了你的东西是monad,它需要有两个操作.这些是常见的是,在世界上的Haskell,称为return和(>>=)(发音为"绑定".)一个单子可以被看作是具有某种"环境"的计算.在这种情况下IO,上下文是副作用.在这种情况下Maybe,上下文无法提供值,等等.所以monad是有价值的东西,但不仅仅是价值.由于缺乏更好的词,这一点通常被称为"背景".

操作

无论如何,涉及的签名是

return :: Monad m => a -> m a
(>>=) :: Monad m => m a -> (a -> m b) -> m b

这意味着return接受任何旧值a并以某种方式将其放入monad的上下文中.这通常是一个相当容易实现的功能(没有太多方法可以将任何a值放入上下文中.)

有趣的是(>>=).它需要amonad上下文中的值和从任何值a到新值的函数,b 但在monad上下文中.然后它返回b带有上下文的值.在考虑Monad为您的事物制作实例之前,您需要有一个明智的实现.没有(>>=),你的东西肯定不是monad.

法律

然而,这是不够的,有return和(>>=)!我说实施需要合情合理.这也意味着你的东西必须实现return并(>>=)遵守monad法则.它们如下:

1. return a >>= f 应该是一样的 f a
2. m >>= return 应该和刚才一样 m
3. (m >>= f) >>= g 应该是一样的 m >>= (\x -> f x >>= g)

这些很有意义*(前两个是微不足道的,第三个只是一个相关性法则),我们需要所有monad遵守它们.编译器不会对此进行检查(但可能会认为它们会保留),因此您有责任确保它们成立.

如果你的monad遵守这些法律,你会得到一个monad!恭喜!其余的只是文书工作,即将实例定义为

instance Monad MyThing where
  return a = {- definition -}
  m >>= f  = {- definition -}

然后你也准备好使用do语法了!

*有关monad法律的Haskell维基页面的更多信息.

Answer 3

我认为这就是您的目标。唯一的变化我做是凝聚Ap和ApStep成一个单一的类型。

data Ap a =
    ApRead   (String -> Ap a)
  | ApWrite  String (Ap a)
  | ApReturn a

instance Monad Ap where
    return = ApReturn
    m >>= f = case m of
        ApRead      k  -> ApRead  (\x -> k x >>= f)
        ApWrite str m' -> ApWrite str (m' >>= f)
        ApReturn    r  -> f r

ioWriteLn :: String -> Ap ()
ioWriteLn str = ApWrite str (ApReturn ())

ioRead :: Ap String
ioRead = ApRead ApReturn

apTest :: Ap Int
apTest = do
    ioWriteLn "Hello world!"
    i <- ioRead
    ioWriteLn ("You wrote [" ++ i ++ "]")
    return 10

尽管使用do符号以单子形式编写，但apTest与以下手写构造函数链相同：

apTest :: Ap Int
apTest =
    ApWrite "Hello, world!"             $
    ApRead                              $ \i -> 
    ApWrite ("You wrote [" ++ i ++ "]") $
    ApReturn 10

这是免费monad的特例，因此您可以通过编写以下代码来大大简化代码：

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad.Free

data ApF next = Read (String -> next) | Write String next deriving (Functor)

type Ap = Free ApF

ioWriteLn :: String -> Ap ()
ioWriteLn str = liftF (Write str ())

ioRead :: Ap String
ioRead = liftF (Read id)

要了解有关免费monad的更多信息，您可以阅读我关于free monads的文章，其中详细介绍了如何将DSL转换为免费monad并建立了它们如何工作的直觉。