时间戳

首页 > 解决方案 > 玫瑰树的单子

haskell - 玫瑰树的单子

问题描述

我有这种数据类型

> data Rose a
>   = RoseNode a [Rose a]
>   | RoseLeaf

我需要为它创建一个 monad 实例。这是我的尝试

> instance Monad Rose where
>    return = RoseNode
>    RoseNode a rs >>= f = RoseNode (f a) (rs >>= f)
>    RoseLeaf >>= _ = RoseLeaf

但我收到了这个错误

app\Main.lhs:599:15: error:
    * Couldn't match type `[Rose a] -> Rose a' with `Rose a'
      Expected type: a -> Rose a
        Actual type: a -> [Rose a] -> Rose a
    * Probable cause: `RoseNode' is applied to too few arguments
      In the expression: RoseNode
      In an equation for `return': return = RoseNode
      In the instance declaration for `Monad Rose'
    * Relevant bindings include
        return :: a -> Rose a (bound at app\Main.lhs:599:6)
    |
599 | >    return = RoseNode
    |               ^^^^^^

和这个

app\Main.lhs:601:51: error:
    * Couldn't match type `Rose' with `[]'
      Expected type: Rose a -> [b]
        Actual type: a -> Rose b
    * In the second argument of `(>>=)', namely `f'
      In the second argument of `RoseNode', namely `(rs >>= f)'
      In the expression: RoseNode (f a) (rs >>= f)
    |
601 | >    RoseNode a rs >>= f = RoseNode (f a) (rs >>= f)
    |

我该如何解决这些问题？

编辑 这是 Rose 的应用程序

> instance Applicative Rose where
>     pure x = RoseNode x []
>     (<*>) _ RoseLeaf = RoseLeaf
>     (<*>) RoseLeaf _ = RoseLeaf
>     (<*>) (RoseNode f rosa) n@(RoseNode x subrosa) = RoseNode (f x) (map (fmap f) subrosa ++ map (<*> n) rosa)

标签： haskell

解决方案

这是家庭作业吗？如果是这样，Rose数据类型是给你的，还是你自己想出来的？有可能你应该想出一个不同的Rose类型，用叶子而不是节点中的值，因为叶子值玫瑰树的 monad 实例比节点值玫瑰树的 monad 更明显。

如您所知，对于列表，一元绑定操作lst >>= f使用f子列表替换原始列表中的每个值，然后将结果“展平”，因此它仍然是值列表，而不是值列表列表.

类似地，对于一棵树，单子绑定操作tree >>= f应该应用f将树中的每个值替换为一个子树，然后“展平”结果，所以它仍然是一棵值树，而不是一棵值树。

具体来说，对于叶子中的值的玫瑰树，预期的定义rose >>= f很简单——它应该用叶子树替换每个叶子值，然后“扁平化”结果，因此新的子树被嫁接到原来的树。

对于节点中有值的玫瑰树，很难弄清楚应该发生什么。节点中的每个值都应该被子树替换，但是要弄清楚如何“展平”结果有点困难，因为它不像将子树嫁接到叶子上那么简单。在每个节点上，您都有新的子树，然后在该节点下还有主树分支，每个子树都是需要展平的子树。我想明显的可能性是（1）将节点的子树与该节点下其他分支的扁平化连接；或（2）以相反的顺序连接它们，首先展平该节点下的其他分支，然后展平该节点的子树。

看起来您的应用实例实现了 (1) 的等价物。

因此，您可能想要的实例是：

data Rose a
  = RoseNode a [Rose a]
  | RoseLeaf
  deriving (Functor)
instance Applicative Rose where
  pure x = RoseNode x []
  (<*>) _ RoseLeaf = RoseLeaf
  (<*>) RoseLeaf _ = RoseLeaf
  (<*>) (RoseNode f rosa) n@(RoseNode x subrosa) 
    = RoseNode (f x) (map (fmap f) subrosa ++ map (<*> n) rosa)
instance Monad Rose where
  RoseLeaf >>= _ = RoseLeaf
  RoseNode x branches >>= f = case f x of
    RoseLeaf -> RoseLeaf
    RoseNode y branches' -> RoseNode y (branches' ++ fmap (>>= f) branches)

请注意，您不需要定义return，因为它默认为pure.

(<*>)您可以通过从Applicative实例与apfrom进行比较来确保 applicative 和 monad 实例是“兼容的” Control.Monad，它(<*>)使用 monadic 操作实现：

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad

data Rose a
  = RoseNode a [Rose a]
  | RoseLeaf
  deriving (Functor, Show)
instance Applicative Rose where
  pure x = RoseNode x []
  (<*>) _ RoseLeaf = RoseLeaf
  (<*>) RoseLeaf _ = RoseLeaf
  (<*>) (RoseNode f rosa) n@(RoseNode x subrosa)
    = RoseNode (f x) (map (fmap f) subrosa ++ map (<*> n) rosa)
instance Monad Rose where
  RoseLeaf >>= _ = RoseLeaf
  RoseNode x branches >>= f = case f x of
    RoseLeaf -> RoseLeaf
    RoseNode y branches' -> RoseNode y (branches' ++ fmap (>>= f) branches)

t1 = RoseNode (+1) [RoseNode (+2) [], RoseNode (+3) []]
t2 = RoseNode 17 [RoseNode 23 [], RoseNode 29 []]

main = do
  print $ t1 <*> t2
  print $ t1 `ap` t2

推荐阅读