实现`MyMonad Free f` [英] Implementing `MyMonad Free f`

问题描述

Typeclassopedia定义了 Free monad 数据类型。

data Free a = Var a
|节点（f（Free fa））

鉴于：

  class（MyMonad m）其中
 ret :: a  - > m a 
 flatMap :: m a  - > （a  - > m b） - > mb 
  

这是我在实现 MyMonad 这个类型类型的实例。

  instance Functor f => MyMonad（Free f）其中
 ret = Var 
 flatMap（Var x）f = fx 
 flatMap（Node xs）f =错误
  

请帮我理解>> = / binding是否超过免费 monad。

当我在实施方面苦苦挣扎时 Applicative（Free f），鼓励我尝试实现 Monad 实例。

解决方案

在这些情况下，输入漏洞可以帮助您如何继续。他们提供了关于尚未实现的漏洞应该具有的类型的信息。

使用类型化的洞而不是 error 在你的定义中：

  instance Functor f => MyMonad（Free f）其中
 ret = Var 
 flatMap（Var x）g = fx 
 flatMap（Node xs）g = _ 
  pre> 
 
 
给出一个错误信息，如下所示：
 找到类型为空的`_'：免费fb 
 ... 
相关绑定包括
g :: a  - > 
 xs :: f（Free f a）（绑定在Main.hs：10：17）
 flatMap :: Free f a  - > （a  - > Free f b） - > 
  
 <$ c 
（在Main.hs：9：3时绑定） $ c>在洞中释放fb  ...应该使用哪个构造函数？  Var 或 Node ？
 
 
 
现在，键入释放一个就像一棵树，它的叶子上有类型 a 的值（ Var 构造函数），并且其分支节点由函子 f 整形。
 
 
 
什么是>> = 对于免费？把它想象成一棵树，并在每片树叶上嫁接新树。这些新树是使用传递给>> = 的函数从树叶中的值构造的。
 
 
 <这有助于我们继续：现在我们知道 flatMap（Node xs）f = _ 模式右边的构造函数必须是 Node ，因为将新事物移植到树上从不会将已存在的节点折叠到树叶中，而只会将叶子扩展为全新的树状结构。类型hole： 
 
 
 实例Functor f => MyMonad（Free f）其中
 ret = Var 
 flatMap（Var x）g = fx 
 flatMap（Node xs）g = Node _ 
 
找到洞_ 'with type：f（Free fb）
 ... 
相关绑定包括
g :: a  - > 
 xs :: f（Free fa）（绑定在Main.hs：10：17）
  
在 xs 中，我们有一个 Free fa   f ，但 f 是一个函数，我们可以很容易地映射它。
 
 
 
但是如何将 Free fa 转换为洞所需的 Free fb ？直观地说，这个 Free fa 会比较小，因为>> = 开头，因为我们已经剥离了一个分支节点。也许它甚至是一个叶节点，就像其他模式匹配所涵盖的情况一样！这表明使用某种递归。
 
Typeclassopedia defines the Free monad data type. 

  
data Free f a = Var a
                 | Node (f (Free f a)) 
Given:
class (MyMonad m) where
    ret     :: a         -> m a
    flatMap :: m a -> (a -> m b) -> m b
Here's my incomplete attempt at implementing the MyMonad instance of this typeclass.
instance Functor f => MyMonad (Free f) where
  ret                 = Var
  flatMap (Var x)  f  = f x 
  flatMap (Node xs) f = error
Please help me reason about what >>=/binding means over a Free monad. 

When I struggled with implementing Applicative (Free f), I was encouraged to try to implement the Monad instance.
解决方案
In these kinds of situations, typed holes can help with how to proceed. They give information about the type the still unimplemented "hole" should have.

Using a typed hole instead of error in your definition:
instance Functor f => MyMonad (Free f) where
    ret                 = Var
    flatMap (Var x)  g  = f x
    flatMap (Node xs) g = _
Gives an error message like (here simplified):
Found hole `_' with type: Free f b
...
Relevant bindings include
  g :: a -> Free f b (bound at Main.hs:10:21)
  xs :: f (Free f a) (bound at Main.hs:10:17)
  flatMap :: Free f a -> (a -> Free f b) -> Free f b
    (bound at Main.hs:9:3)
That Free f b in the hole... which constructor should it have? Var or Node?

Now, a value of type Free a is like a tree that has values of type a on the leaves (the Var constructor) and whose branching nodes are "shaped" by the functor f.

What is >>= for Free? Think of it as taking a tree and "grafting" new trees on each of its leaves. These new trees are constructed from the values in the leaves using the function that is passed to >>=.

This helps us continue: now we know that the constructor on the right of the   flatMap (Node xs) f = _ pattern must be Node, because "grafting" new things onto the tree never collapses already existing nodes into leaves, it only expands leaves into whole new trees.

Still using type holes:
instance Functor f => MyMonad (Free f) where
    ret                 = Var
    flatMap (Var x)  g  = f x
    flatMap (Node xs) g = Node _

Found hole `_' with type: f (Free f b)
...
Relevant bindings include
g :: a -> Free f b (bound at Main.hs:10:21)
xs :: f (Free f a) (bound at Main.hs:10:17)
In xs we have a Free f a wrapped in a f, but f is a functor and we could easily map over it.

But how to convert that Free f a into the Free f b required by the hole? Intuitively, this Free f a will be "smaller" that the one the >>= started with, because we have stripped one "branching node". Maybe it is even a leaf node, like the case covered by the other pattern-match! This suggests using recursion of some kind.

                        
这篇关于实现`MyMonad Free f`的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！