努力实现 Monad 函数

Question

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

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

data MyTree a = MyTree a [MyTree a]

我正在尝试实现一个 returns "Nothing" 如果树中包含任何 "Nothing" 值的函数。否则，提取所有 m 值和 returns 一棵包裹的树。

所以函数类型签名如下。

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 上使用了绑定运算符，以便我可以获得它的纯值。然后我使用列表中的 head 值递归调用 "check" 函数。最后，我总结一下最终结果。

我测试了一些样本并得到了以下结果。

> 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

具体来说，对于 MyTree，check 是 sequence。所以如果我们写一个 Traversable MyTree 实例，我们就会得到它。但是，让我们先从两个方向退后一步。 Traversable 是 Functor 和 Foldable 的子 class，这并非巧合。使用 traverse 可以实现 fmap 和 foldMap。但更重要的是，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。

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

所以现在我们到了 Traversable。它将与 fmap 非常相似，但我们需要使用 Applicative 操作合并结果有点就像我们使用 [=47] 合并 foldMap 结果=] 操作。

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 结果和第二个操作的 [MyTree b] 结果，并应用 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)

大功告成。

努力实现 Monad 函数

Struggling with implementing a Monad function

monads

haskell

functional-programming