如何在 Applicative (Haskell) 中将函数映射到 RoseTree 上？

Question

如何将 applicative 应用于 RoseTree，即 return 由连续将函数应用于初始节点而创建的树组成的树。这是我编写的代码：

{-# LANGUAGE DeriveFunctor, InstanceSigs #-}

data RoseTree a = Nil | Node a [RoseTree a] deriving(Functor,Show)

instance Applicative RoseTree where
    pure :: a -> RoseTree a
    pure x = Node x []

    (<*>) :: RoseTree (a -> b) -> RoseTree a -> RoseTree b
    (<*>) _ Nil = Nil
    (<*>) Nil _ = Nil
    (<*>) (Node f tree) (Node x subtrees) = Node (f x) (zipWith (<*>) tree subtrees)

我不确定我对 pure and (<*>) 的定义有什么问题。这是我得到的错误：

错误： failure in expression `(Node (+1) []) <*> (Node 7 [Node 1 [], Node 2 [], Node 3 [Node 4 []]])' expected: Node 8 [Node 2 [],Node 3 [],Node 4 [Node 5 []]] but got: Node 8 []

参考测试用例：

-- >>> (Node (+1) [Node (*2) []]) <*> Nil
-- Nil
--
-- >>> Nil <*> (Node 7 [Node 1 [], Node 2 [], Node 3 [Node 4 []]])
-- Nil
--
-- >>> (Node (+1) []) <*> (Node 7 [Node 1 [], Node 2 [], Node 3 [Node 4 []]])
-- Node 8 [Node 2 [],Node 3 [],Node 4 [Node 5 []]]
--
-- >>> (Node (+1) [Node (*2) []]) <*> (Node 5 [Node 2 [], Node 8 [Node 1 []]])
-- Node 6 [Node 3 [],Node 9 [Node 2 []],Node 10 [Node 4 [],Node 16 [Node 2 []]]]

Answer 1

类型可以有多个有效的 Applicative 实例（例如列表如何直接在 [] 上有一个，而另一个在它们的 newtype 包装器 ZipList 上）。您的 <*> 函数似乎对 an 应用实例有效，只是根据您的测试用例不是您想要的那个（而且也不是使用 pure).

问题出在这里：

(<*>) (Node f tree) (Node x subtrees) = Node (f x) (zipWith (<*>) tree subtrees)

根据您的测试用例的预期，它存在三个主要问题：

它从未将 f 应用于 subtrees 中的任何内容。
它不会将 tree 中的任何内容应用到 x。
它只将每个 tree 元素应用于 subtrees 中的一个元素。

这一行应该可以代替：

(<*>) (Node f tree) n@(Node x subtrees) = Node (f x) (map (fmap f) subtrees ++ map (<*> n) tree)

此外，虽然这会使您的测试用例按预期工作，但我还没有严格验证它实际上是一个合法的实例。（我简单地看了看，似乎还不错，但我也是在凌晨 1 点写的。）

Answer 2

我们可以将您的 RoseTree 视为特定 monad 转换器的特定应用。让我们将您自己的定义放入名为 Rose 的模块中，并为 RoseTree 派生 Read 和 Show 实例。现在我们可以开始幻想了。注意：您可能还不能理解这里的所有内容。其中一些使用了非常高级的 GHC 语言扩展。不过我觉得还是挺有意思的。

我们将使用 free 包中的 cofree comonad transformer。顾名思义，它相对于 Comonad class 起着特殊的作用，但事实证明它也可以用 Monad 做一些有用的事情！

{-# language PatternSynonyms, ViewPatterns, GeneralizedNewtypeDeriving #-}
module FancyRose where

import Text.Read (Read (readPrec))
import qualified Rose
import Control.Comonad.Trans.Cofree
{-
newtype CofreeT f w a = CofreeT
  { runCofreeT :: w (CofreeF f a (CofreeT f w a)) }

data CofreeF f a b = a :< f b
-}

newtype RoseTree a = RoseTree { unRoseTree :: CofreeT [] Maybe a }
  deriving (Functor, Applicative, Monad, Eq, Ord)

很棒的是，我们不必自己提出 Applicative（或 Monad）定律的证明。你可以全部找到 in the free git repository!

这些模式同义词允许用户假装（大部分）RoseTree 被定义简单的方法。不要太在意细节。

-- Create or match on an empty 'RoseTree'. This is a simple
-- bidirectional pattern synonym: writing `Nil` in an expression
-- or a pattern is just the same as writing
-- `RoseTree (CofreeT Nothing)`
pattern Nil :: RoseTree a
pattern Nil = RoseTree (CofreeT Nothing)

-- Create or match on a non-empty 'RoseTree'. This is an explicit
-- bidirectional pattern synonym. We use a view pattern to show
-- how to match on a node, and then in the `where` clause we show
-- how to construct one.
pattern Node :: a -> [RoseTree a] -> RoseTree a
pattern Node a ts <- RoseTree (CofreeT (fmap (fmap RoseTree) -> Just (a :< ts)))
  where
    Node a ts = RoseTree $ CofreeT $ Just $ a :< map unRoseTree ts

以下是我们可以毫不费力地实现 Show 和 Read 的方法：

-- Convert a `RoseTree` to the simple representation of one.
-- Note that the pattern synonyms make this really easy!
toBasicRose :: RoseTree a -> Rose.RoseTree a
toBasicRose Nil = Rose.Nil
toBasicRose (Node a ts) = Rose.Node a (map toBasicRose ts)

-- Convert the simple representation back to a `RoseTree`.
fromBasicRose :: Rose.RoseTree a -> RoseTree a
fromBasicRose Rose.Nil = Nil
fromBasicRose (Rose.Node a ts) = Node a (map fromBasicRose ts)

instance Show a => Show (RoseTree a) where
  showsPrec p = showsPrec p . toBasicRose
instance Read a => Read (RoseTree a) where
  readPrec = fmap fromBasicRose readPrec

你所有的测试用例都通过了。

性能说明

我担心所有映射都会使 Node 模式变慢。但是我刚刚检查了编译器中间语言并确定 GHC 的重写规则实际上开始并无条件地摆脱了所有映射。

如何在 Applicative (Haskell) 中将函数映射到 RoseTree 上？

How do I map functions over a RoseTree in Applicative (Haskell)?

haskell

applicative

性能说明