Существуют ли нетривиальные экземпляры Foldable или Traversable, которые не похожи на контейнеры?

Ответ 1

Каждый допустимый Traversable f изоморфен Normal s для некоторого s :: Nat -> *, где

data Normal (s :: Nat -> *) (x :: *) where  -- Normal is Girard terminology
  (:-) :: s n -> Vec n x -> Normal s x

data Nat = Zero | Suc Nat

data Vec (n :: Nat) (x :: *) where
  Nil   :: Vec Zero n
  (:::) :: x -> Vec n x -> Vec (Suc n) x

но это вовсе не тривиально реализовать iso в Haskell (но это стоит пойти с полными зависимыми типами). Морально, s вы выбираете

data {- not really -} ShapeSize (f :: * -> *) (n :: Nat) where
  Sized :: pi (xs :: f ()) -> ShapeSize f (length xs)

и двух направлениях изо-раздельной и рекомбинированной формы и содержимого. Форма вещи задается как раз fmap (const ()), а ключевым моментом является то, что длина формы f x равна самой длине f x.

Векторы пересекаются в смысле visit-each-once-left-right-right. Нормали проходят в точности путем сохранения формы (отсюда размер) и перемещения вектора элементов. Чтобы быть проезжаемым, нужно иметь конечное число положений элементов, расположенных в линейном порядке: изоморфизм нормального функтора точно раскрывает элементы в их линейном порядке. Соответственно, каждая структура Traversable является (финитным) контейнером: у них есть набор фигур с размером и соответствующее понятие положения, заданное начальным отрезком натуральных чисел, строго меньшим размера.

Foldable вещи также являются финитными, и они хранят вещи в порядке (есть разумный toList), но они не гарантируются как Functor s, поэтому они не имеют такого четкого представления формы. В этом смысле (смысл "контейнера", определенного моими коллегами Эбботтом, Альтенкирхом и Гани), они не обязательно допускают характеристики фигур и позиций и, следовательно, не являются контейнерами. Если вам повезет, некоторые из них могут быть контейнерами до некоторого частного. Действительно существует Foldable, чтобы разрешить обработку таких структур, как Set, чья внутренняя структура призвана быть секретом и, безусловно, зависит от упорядочивания информации об элементах, которые не обязательно соблюдаются посредством операций перемещения. Однако именно то, что представляет собой хорошо выполненный Foldable, является довольно спорным вопросом: я не буду спорить с прагматическими преимуществами выбора этого дизайна библиотеки, но я мог бы пожелать более четкой спецификации.

Ответ 2

Ну, с помощью universe можно было бы потенциально написать экземпляры Foldable и Traversable для трансформаторов состояний в конечном состоянии пространства. Идея будет примерно похожа на экземпляры Foldable и Traversable для функций: запустите функцию всюду за Foldable и создайте таблицу поиска для Traversable. Таким образом:

import Control.Monad.State
import Data.Map
import Data.Universe

-- e.g. `m ~ Identity` satisfies these constraints
instance (Finite s, Foldable m, Monad m) => Foldable (StateT s m) where
    foldMap f m = mconcat [foldMap f (evalStateT m s) | s <- universeF]

fromTable :: (Finite s, Ord s) => [m (a, s)] -> StateT s m a
fromTable vs = StateT (fromList (zip universeF vs) !)

float :: (Traversable m, Applicative f) => m (f a, s) -> f (m (a, s))
float = traverse (\(fa, s) -> fmap (\a -> (a, s)) fa)

instance (Finite s, Ord s, Traversable m, Monad m) => Traversable (StateT s m) where
    sequenceA m = fromTable <$> traverse (float . runStateT m) universeF

Я не уверен, что это имеет смысл. Если да, я думаю, я был бы рад добавить его в пакет; как вы думаете?

Ответ 3

Я не считаю его Foldable или Traversible, но MonadRandom является примером того, что может быть, функционирующим как бесконечный список, но который больше не похож на контейнер, чем на все остальное, что складно. Понятно, что это случайная величина.