В Haskell, как fmap между отдельными Traversables?

Один трюк, который мы часто используем в Haskell, чтобы показать, что это невозможно, — это попытка произвести с ним «false» — иначе говоря, создать значение типа

data Void

тип без конструкторов. Если возможно, используя вашу подпись типа, создать значение типа Void, то ваша подпись типа не может быть реализована. Это также известно как «reducto ad absurdum» или «опровержение от противного». Если ваша сигнатура типа позволит нам создать значение типа Void... тогда "очевидно" ваша сигнатура типа является чушью и не может быть реализована.

В этом случае мы «возвращаем» экземпляр Traversable, поэтому давайте использовать Traversable как (,) Void:

instance Traversable ((,) w) where
    traverse f (x, y) = (x,) <$> f y

Теперь воспользуемся f как любым старым функтором. Это может быть что угодно... давайте использовать Maybe, потому что кажется, что все уже это понимают.

Тогда вы могли бы написать:

gmap :: (a -> b) -> Maybe a -> (Void, b)

О нет, этого не может быть... похоже, с помощью gmap вы можете создать Void, просто передав любую старую вещь:

gmap :: (() -> ()) -> Maybe () -> (Void, ())

Итак, теперь моя стратегия создания Void:

bad :: Void
bad = fst (gmap id Nothing)

Поскольку у Void нет конструкторов, значение типа bad :: Void не должно существовать (не учитывая что-то вроде бесконечного цикла или частичной функции). Итак, если само существование if gmap может позволить нам создать значение типа Void... это должно означать, что gmap не может существовать в той форме, которую вы дали.

Что касается вашей более общей проблемы, «почему» в том, как работает Traversable, заключается в том, что он может только когда-либо модифицировать структуры. Он не может создавать их. Здесь вы хотите создать значение g b, но Traversable не может его "создать", оно может только "преобразовать" его. Ваше непонимание может исходить из того, что вы думаете, что Traversable - это класс типов, похожий на список: это не совсем так. Использование [] в качестве архетипа может ввести вас в заблуждение.

Моим "типичным" Traversable для представления свойств класса типов является Map k из контейнеров Data.Map: Map не является а, а скорее значениями, связанными с ключами. Любые операции над ним должны учитывать это свойство ассоциации... и не рассматривать его как большой список без дополнительной структуры.

Итак, что было бы возможно, выглядит примерно так:

replace :: (Foldable f, Traversable g) => f a -> g b -> g a

Где все значения g b заменены всеми значениями f a. Это на самом деле весело писать, если вы ищете упражнение. По сути, replace сохранит ту же структуру, что и g a, но просто заменит значения. Таким образом, вы можете «создать» g a из f a, если у вас есть, так сказать, «пример g b». Если вы использовали что-то вроде:

replace :: [a] -> Map k b -> Map k a

затем replace заменит все значения во второй карте элементами в списке, заменив их на правильные значения ключей.

Затем вы можете написать:

gmap :: (Traversable a, Traversable g) => (a -> b) -> f a -> g c -> g b

Где вы берете «пример» g a структуры, которую хотите скопировать.

Ближе всего к возможности «построить» структуру в общих классах типов Haskell — это IsList из https://hackage.haskell.org/package/base-4.12.0.0/docs/GHC-Exts.html.#t:IsList

Этот класс типов дает вам две функции, fromList и toList, так что вы можете написать:

throughIsList :: (IsList l, IsList m, Item l ~ Item m) => l -> m
throughIsList = fromList . toList

И заставить его работать более Functors:

gmap :: (IsList (f a), IsList (g b), Item (f a) ~ a, Item (g b) ~ b) => (a -> b) -> f a -> g b
gmap f = fromList . map f . toList

Проблема в том, что большинство Functor не являются экземплярами IsList... и многие из реальных экземпляров не являются тотальными. Так что это не совсем удобно для большинства Functor.

Так что, в конце концов, я не думаю, что есть удовлетворительный ответ. Если что-то, что вы делаете, зависит от того факта, что есть хороший ответ (кроме ответа «нет») ... может быть, я могу спросить, какова ваша «конечная цель»? Для чего вы планируете использовать этот тип?

(Например, в 90 % ситуаций, когда люди задают вопросы вроде «Могу ли я преобразовать монады» или что-то в этом роде, обычно они не хотят что-то делать в общем , а имели в виду конкретные типы.)

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

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleContexts #-}

class (Functor f, Functor g) => GFunctor f g where
  toG :: f a -> g a
  gmap :: (a -> b) -> (f a) -> (g b)
  gmap fn functor = toG $ fmap fn functor

data Tree a = Leaf | Node (Tree a) a (Tree a) deriving Show

instance Functor Tree where
  fmap f Leaf = Leaf
  fmap f (Node t1 x t2) = Node (fmap f t1) (f x) (fmap f t2)

instance GFunctor [] Tree  where
  toG [] = Leaf 
  toG [x] = Node Leaf x Leaf
  toG (x:xs) = Node (toG $ (takeHalf xs)) x ((toG $ dropHald xs))

takeHalf xs = take ((length xs) `div` 2) xs
dropHald xs = drop ((length xs) `div` 2) xs

res :: Tree Int
res = gmap (+1) [1,2,3,4,5]

выход:

   res
=> Node (Node Leaf 3 (Node Leaf 4 Leaf)) 2 (Node Leaf 5 (Node Leaf 6 Leaf))

Я думаю, что вы можете сделать это с помощью fmap и естественного преобразования. Вот пример использования пакета natural-transformations, просто чтобы продемонстрировать идею.

Первое естественное преобразование, которое приходит мне в голову, это safeHead:

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x

Запуск GHCi с пакетом natural-transformations:

Prelude Control.Natural> t = wrapNT safeHead
Prelude Control.Natural> t # [1..3]
Just 1
Prelude Control.Natural> t # []
Nothing
Prelude Control.Natural> fmap show (t # [1..3])
Just "1"
Prelude Control.Natural> fmap show (t # [])
Nothing

Итак, для естественного преобразования t будет ли что-то вроде fmap f . (t #) делать то, что вы хотите?

(Здесь я представляю, что f — это обычная функция a -> b.)