Esistono istanze pieghevoli o percorribili non banali che non sembrano contenitori?

Question

Ci sono molti funtori che sembrano contenitori (elenchi, sequenze, mappe, ecc.) E molti altri che non lo fanno (trasformatori di stato, IO, parser, ecc.). Non ho ancora visto istanze non banali Foldable o Traversable che non sembrano contenitori (almeno se si strizza un po '). Esiste? In caso contrario, mi piacerebbe avere una migliore comprensione del perché non possono.

Answer 1

Ogni valida Traversable f è isomorfo a Normal s per qualche s :: Nat -> * dove

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 

ma non è affatto banale per implementare l'iso in Haskell (ma vale la pena di andare con tipi dipendenti completi). Moralmente, il s si sceglie è

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

e le due direzioni della iso separata e ricombinare la forma e il contenuto. La forma di una cosa è data solo da fmap (const()) e il punto chiave è che la lunghezza della forma di una f x corrisponde alla lunghezza dello stesso f x.

I vettori sono percorribili nel senso della visita-una-volta-sinistra-destra-destra. Le normali sono attraversabili esattamente conservando la forma (quindi la dimensione) e attraversando il vettore di elementi. Essere attraversabili significa avere finitamente molte posizioni di elementi disposte in un ordine lineare: l'isomorfismo di un normale functor espone esattamente gli elementi nel loro ordine lineare. Corrispondentemente, ogni struttura Traversable è un contenitore (finito): hanno un insieme di forme con dimensioni e una nozione corrispondente di posizione data dal segmento iniziale dei numeri naturali strettamente inferiore alla dimensione.

Le Foldable cose sono anche finitario e mantenere le cose in un ordine (v'è un sensibile toList), ma non sono garantiti per essere Functor s, in modo da non avere un concetto così nitido di forma. In questo senso (il senso di "contenitore" definito dai miei colleghi Abbott, Altenkirch e Ghani), non necessariamente ammettono una caratterizzazione di forme e posizioni e quindi non sono contenitori. Se sei fortunato, alcuni di questi potrebbero essere contenitori fino a un certo quoziente. Infatti, Foldable esiste per consentire l'elaborazione di strutture come Set la cui struttura interna è destinata a essere un segreto, e certamente dipende dall'ordinare le informazioni sugli elementi che non sono necessariamente rispettate dalle operazioni di movimento.Esattamente ciò che costituisce un buon comportamento Foldable è piuttosto un punto controverso, tuttavia: non voglio cavillare con i benefici pragmatici di quella scelta di progettazione della libreria, ma potrei desiderare una specifica più chiara.

Answer 2

Bene, con l'aiuto di universe, si potrebbero potenzialmente scrivere Foldable e Traversable istanze per trasformatori di stato su spazi di stato finiti. L'idea sarebbe più o meno simile alle istanze Foldable e Traversable per le funzioni: eseguire la funzione ovunque per Foldable e creare una tabella di ricerca per Traversable. Quindi:

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 

Non sono sicuro se questo ha senso. Se lo fa, penso che sarei felice di aggiungerlo al pacchetto; cosa ne pensi?

Answer 3

Non penso sia in realtà Pieghevole o Traversibile, ma MonadRandom è un esempio di qualcosa che potrebbe essere, funzionante come una lista infinita, ma che non assomiglia più ad un contenitore di qualsiasi altra cosa che sia pieghevole. Concettualmente, è una variabile casuale.