Как сопоставить функции с RoseTree в Applicative (Haskell)?

Типы могут иметь более одного действительного экземпляра Applicative (например, как списки имеют один непосредственно в [], а другой - в их newtype оболочке ZipList). Ваша функция <*> кажется допустимой для применимого экземпляра, но не для того, который вам нужен в соответствии с вашими тестовыми примерами (а также не для того, который использует это определение pure).

Проблема здесь:

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

С ним связаны три основные проблемы, учитывая то, что ожидают ваши тестовые примеры:

1. Он никогда не применяет f ни к чему в subtrees.
2. Он никогда ничего не применяет в tree к x.
3. Он применяет каждый элемент tree только к одному элементу в subtrees.

Вместо этого должна работать эта строка:

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

Кроме того, хотя это заставляет ваши тестовые примеры работать должным образом, я не проверял, действительно ли это законный экземпляр. (Я бегло просмотрел его, и он кажется хорошим, но я также пишу это в час ночи.)

Мы можем видеть ваш RoseTree как конкретное приложение конкретного монадного преобразователя. Давайте поместим ваше собственное определение в модуль с именем Rose и получим экземпляры Read и Show для RoseTree. Теперь мы можем пофантазировать. Примечание: вы, вероятно, еще не все поймете здесь. Некоторые из них используют довольно продвинутые языковые расширения GHC. Но я думаю, что это все равно интересно.

Мы будем использовать преобразователь cofree comonad из пакета free. Как следует из названия, он играет особую роль по отношению к классу Comonad, но оказывается, что и с 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) законов. Вы можете найти их все в free репозитории git. !

-- 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

-- 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