haskell - tutorial - google tag manager

¿Hay instancias no triviales plegables o transitables que no parecen contenedores?

Question

Hay muchos funtores que parecen contenedores (listas, secuencias, mapas, etc.) y muchos otros que no lo son (transformadores de estado, IO , analizadores, etc.). Todavía no he visto ninguna instancia no trivial Foldable o Traversable que no parezca un contenedor (al menos si entrecierras un poco los ojos). ¿Existen algunas? Si no, me encantaría entender mejor por qué no pueden.

Answer 1

Bueno, con la ayuda del universe , uno podría escribir instancias Foldable y Traversable para transformadores de estado en espacios de estado finitos. La idea sería aproximadamente similar a las instancias Foldable y Traversable para funciones: ejecute la función en todas partes para Foldable y haga una tabla de búsqueda para Traversable . Así:

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

No estoy seguro de si esto tiene sentido. Si lo hace, creo que estaría feliz de agregarlo al paquete; ¿Qué piensas?

Answer 2

Cada Traversable f válido Traversable f es isomorfo a Normal s para algunos s :: Nat -> * donde

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

pero no es en absoluto trivial implementar la iso en Haskell (pero vale la pena intentarlo con tipos dependientes completos). Moralmente, el que escoges es

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

y las dos direcciones de la iso se separan y recombinan la forma y los contenidos. La forma de una cosa está dada solo por fmap (const ()) , y el punto clave es que la longitud de la forma de un fx es la longitud del mismo fx .

Los vectores se pueden atravesar en el sentido de visita una vez de izquierda a derecha. Las normales se pueden atravesar exactamente preservando la forma (de ahí el tamaño) y atravesando el vector de elementos. Ser transitable es tener finamente muchas posiciones de elementos dispuestas en un orden lineal: el isomorfismo a un funtor normal expone exactamente los elementos en su orden lineal. En consecuencia, cada estructura Traversable es un contenedor (finito): tiene un conjunto de formas con tamaño y una correspondiente noción de posición dada por el segmento inicial de los números naturales estrictamente menor que el tamaño.

Las cosas Foldable también son finitas y mantienen las cosas en un orden (hay una lista de toList sensible), pero no se garantiza que sean Functor , por lo que no tienen una noción tan clara de forma . En ese sentido (el sentido de "contenedor" definido por mis colegas Abbott, Altenkirch y Ghani), no admiten necesariamente una caracterización de formas y posiciones y, por lo tanto, no son contenedores. Si tiene suerte, algunos de ellos pueden ser contenedores hasta algún cociente. De hecho, Foldable existe para permitir el procesamiento de estructuras como Set cuya estructura interna pretende ser un secreto, y ciertamente depende de ordenar información sobre los elementos que no necesariamente se respetan en las operaciones de desplazamiento. Exactamente, lo que constituye un Foldable bien comportado es más bien un punto discutible, sin embargo, no voy a discutir los beneficios pragmáticos de la elección del diseño de la biblioteca, pero podría desear una especificación más clara.

Answer 3

No creo que sea realmente plegable o transitable, pero MonadRandom es un ejemplo de algo que podría ser, que funciona como una lista infinita, pero que no se parece más a un contenedor que a cualquier otra cosa que sea plegable. Conceptualmente, es una variable aleatoria.