haskell - 努力实现 Monad 函数

Question

最近，我在玩 Haskell monad 并试图了解这个概念。

假设声明了一个树数据类型，它可以有多个子树。

data MyTree a = MyTree a [MyTree a]

如果树在树中包含任何“Nothing”值，我正在尝试实现一个返回“Nothing”的函数。否则，提取所有 m 值并返回包装树。

所以函数类型签名有以下内容。

check :: Monad m => MyTree (m a) -> m (MyTree a)

这是我目前的实现。

check (MyTree v []) = v >>= (\v' -> return (MyTree v' []))
check (MyTree v (x:xs)) =
  v >>= (\v' -> check x >>= (\t' -> return (MyTree v' [t'])))

我在 v 上使用绑定(bind)运算符，以便获得它的纯值。然后我用列表中的头值递归调用“检查”函数。最后，我包装最终结果。

我用一些 sample 进行了测试，得到了以下结果。

> test1 = MyTree (Just 1) [MyTree (Just 2) [MyTree (Just 3) []]]
> check test1
Just (MyTree 1 [MyTree 2 [MyTree 3 []]])

> test2 = MyTree (Just 1) [MyTree (Just 2) [], MyTree (Just 3) []]
> check test2
-- expected: Just (MyTree 1 [MyTree 2 [], MyTree 3 []]
-- actual:   Just (MyTree 1 [MyTree 2 []])

因此，当输入树有多个子树时，当前的实现存在问题。我已经意识到问题是我只使用 x但不是 xs .我转过头想正确的方法，但仍在弄清楚。如果有人对此有想法，那将非常有帮助。

Answer 1

您的 check函数更广为人知的是 Traversable 的方法。类(class)。

class (Functor t, Foldable t) => Traversable t where
  -- The main method
  traverse
    :: Applicative f
    => (a -> f b) -> t a -> f (t b)
  traverse f = sequenceA . fmap f

  -- An alternative
  sequenceA
    :: Applicative f
    => t (f a) -> f (t a)
  sequenceA = traverse id

  -- (Mostly) legacy methods
  mapM
    :: Monad m
    => (a -> m b) -> t a -> m (t b)
  mapM = traverse

  sequence
    :: Monad m
    => t (m a) -> m (t a)
  sequence = sequenceA

具体来说，check是 sequence对于 MyTree .所以如果我们写一个 Traversable MyTree 就会得到它。实例。但是，让我们首先从两个方向退后一步。 Traversable是 Functor 的子类和 Foldable ，这绝非巧合。可以同时实现 fmap和 foldMap使用 traverse .但更重要的是，fmap 的结构, foldMap和 traverse往往看起来几乎相同!所以让我们从那些更容易的开始。

instance Functor MyTree where
  fmap f (MyTree a ts) = MyTree (f a) _

那个空白里有什么？我们有一个子树列表，我们需要生成一个新的，所以一个不错的选择是

  fmap f (MyTree a ts) = MyTree (f a) (fmap _ ts)

现在空白的类型为 MyTree a -> MyTree b ，所以我们只需调用 fmap递归:

  fmap f (MyTree a ts) = MyTree (f a) (fmap (fmap f) ts)

我们完成了。现在让我们转向Foldable .

foldMap f (MyTree a ts) = _

好吧，我们需要申请f至a在幺半群中得到一个值，然后折叠子树并组合结果。这最终看起来有点像 fmap ， 按照 promise 。

foldMap f (MyTree a ts) = f a <> foldMap (foldMap f) ts

所以现在我们到达 Traversable .它将非常类似于 fmap ，但我们需要使用 Applicative 组合结果操作有点像我们合并 foldMap结果使用 Monoid操作。

instance Traversable MyTree where
   traverse f (MyTree a ts) = _

我们有

a :: a
ts :: [MyTree a]
f :: a -> f b

显然，我们要申请 f至a .遵循 fmap 的模式和 foldMap , 我们要计算 traverse (traverse f) ts .因此，让我们看看这对我们有什么帮助:

traverse f (MyTree a ts) = _ (f a) (traverse (traverse f) ts)

现在 GHC 会告诉我们

_ :: f b -> f [MyTree b] -> f (MyTree b)

我们需要采取b第一个 Action 和 [MyTree b] 的结果第二个 Action 的结果并应用 MyTree构造函数将它们放在一起。我们可以使用 liftA2 :

traverse f (MyTree a ts) = liftA2 MyTree (f a) (traverse (traverse f) ts)

一旦你掌握了写作的窍门 Functor , Foldable , 和 Traversable实例，这样做往往会变得相当乏味。所以 GHC 有一个扩展，可以让编译器为你编写它们。

{-# language DeriveTraversable #-}

module MyModule where

data MyTree a = MyTree a [MyTree a]
  deriving (Functor, Foldable, Traversable)

你完成了。