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

Question

Есть много функторов, которые выглядят как контейнеры (списки, последовательности, карты и т. Д.), И многие другие, которые не похожи (преобразователи состояния, IOпарсеры и пр.). Я еще не видел ни одного нетривиального Foldable или же Traversable экземпляры, которые не похожи на контейнеры (по крайней мере, если вы немного щурились). Кто-нибудь существует? Если нет, я бы хотел лучше понять, почему они не могут.

Answer 1

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

data Normal (s :: Nat -> *) (x :: *) where  -- Normal is Girard's 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 сам.

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

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

Answer 2

Ну, с помощью вселенной можно было бы написать 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

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

Answer 3

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