Каким будет "отличный метод", который есть у Traversable в дополнение к Foldable?

Foldable это суперкласс Traversable аналогично тому, как Functor это суперкласс Applicative а также Monad,

Аналогично случаю Monadгде можно в принципе реализовать fmap как

liftM :: Monad m => (a->b) -> m a -> m b
liftM f q = return . f =<< q

мы могли бы также подражать foldMap как

foldLiftT :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldLiftT f = fst . traverse (f >>> \x -> (x,x))
           -- or: . sequenceA . fmap (f >>> \x -> (x, x))

с использованием Monoid m => (,) m монада. Таким образом, сочетание суперкласса и методов в обоих случаях несет определенную избыточность.

В случае монад можно утверждать, что "лучшим" определением класса типов будет (я пропущу аппликативный / моноидальный)

class (Functor m) => Monad m where
  return :: a -> m a
  join :: m (m a) -> m a

по крайней мере, это то, что используется в теории категорий. Это определение делает, не используя Functor суперкласс, не разрешать liftM так что без этой избыточности.

Возможно ли подобное преобразование для Traversable учебный класс?

Чтобы уточнить: что мне нужно, это переопределение, давайте назовем это,

class (Functor t, Foldable t) => Traversable t where
  skim :: ???

так что мы могли бы сделать фактический Traverse методы функций верхнего уровня

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

но было бы невозможно сделать в общем

instance (Traversable t) => Foldable t where
  foldMap = ... skim ...

data T
instance Traversable T where
  skim = ...

Я не спрашиваю, потому что мне нужно это для чего-то конкретного; это концептуальный вопрос, чтобы лучше понять разницу между Foldable а также Traversable, Снова очень похоже Monad против Functor: в то время как >>= гораздо удобнее, чем join для повседневного программирования на Haskell (потому что вам обычно нужна именно эта комбинация fmap а также join), последнее облегчает понимание того, что такое монада.

Источник

2 ответа

Решение

Foldable это к Functor как Traversable это к Monadт.е. Foldable а также Functor суперклассы Monad а также Traversable (по модулю все аппликативный / монадный шум предложения).

Действительно, это уже в коде

instance Foldable f => Traversable f where
  ...

Так что не ясно, что еще нужно хотеть. Foldable характеризуется toList :: Foldable f => f a -> [a] в то время как Traversable в конечном итоге зависит не только от возможности абстрагировать контент в виде списка toList делает, но и иметь возможность извлечь форму

shape :: Functor f => f a -> f ()
shape = fmap (const ())

а затем рекомбинировать их

combine :: Traversable f => f () -> [a] -> Maybe (f a)
combine f_ = evalStateT (traverse pop f_) where
  pop :: StateT [a] Maybe a
  pop = do x <- get
           case x of
             [] = empty
             (a:as) = set as >> return a

который зависит от traverse,

Для получения дополнительной информации об этой собственности см. Этот пост в блоге Рассел О'Коннор.

Источник

Супер волнистые, потому что уже поздно, но дополнительная сила, которая Traversable имеет более Foldable это способ восстановить первоначальную структуру. Например, со списками:

module MyTraverse where

import Data.Foldable
import Data.Traversable
import Control.Applicative
import Data.Monoid

data ListRec f x = ListRec
  { el :: f (Endo [x])
  }

instance Applicative f => Monoid (ListRec f x) where
    mempty = ListRec (pure mempty)
    mappend (ListRec l) (ListRec r) =
        ListRec (mappend <$> l <*> r)

toM :: Functor f => f b -> ListRec f b
toM this = ListRec $ (Endo . (:)) <$> this

fromM :: Functor f => ListRec f b -> f [b]
fromM (ListRec l) = flip appEndo [] <$> l

myTraverse :: Applicative f => (a-> f b)  -> [a] -> f [b]
myTraverse f xs = fromM $ foldMap (toM . f) xs

я думаю это myTraverse ведет себя так же, как traverse, используя только классы Applicative, Foldable, а также Monoid, Вы можете переписать его, чтобы использовать foldr вместо foldMap если ты хотел избавиться от Monoid,

списки просты, потому что они плоская структура. Тем не менее, я сильно подозреваю, что вы можете использовать Zipper, чтобы получить правильную функцию восстановления для любой структуры (так как молнии являются производными в общем, они всегда должны существовать).

Но даже с застежкой-молнией у вас нет никакого способа указать эту структуру моноиду / функции. По идее, похоже Traversable добавляет что-то вроде

class Traversed t where
  type Path t :: *
  annotate :: t a -> [(Path t, a)]
  fromKeyed :: [(Path t, a)] -> t a

это, кажется, сильно пересекается с Foldable, но я думаю, что это неизбежно при попытке связать пути с их составляющими ценностями.

Источник
Другие вопросы по тегам