Una lista di cui "Nil" ha un valore?

Question

fa qualche libreria standard Haskell definire un tipo di dati come questo

data ListWithEnd e a = Cons a (ListWithEnd e a) 
        | End e 

Quella è una lista il cui elemento di chiusura porta un valore di un tipo designato?

Quindi ListWithEnd() è isomorfo a [] e ListWithEnd Void isomorfo a flussi infiniti. Oppure, visto in modo diverso, ListWithEnd e a è molto vicino al ConduitM() a Identity e ..

Answer 1

possiamo definire ListWithEnd come segue:

import Control.Monad.Free 

type LWE a e = Free ((,) a) e 

In genere abbiamo un'aspettativa che rappresentazioni astratte o generiche ci dovrebbero premiare con una riduzione complessiva di boilerplate . Vediamo cosa ci offre questa rappresentazione.

In ogni caso, definiremo un sinonimo modello per il caso contro:

{-# LANGUAGE PatternSynonyms #-} 

pattern x :> xs = Free (x, xs) 
infixr 5 :> 

Siamo in grado di mappare, piegare e attraversare sopra l'elemento terminale:

fmap (+1) (0 :> Pure 0) == (0 :> Pure 1) 
traverse print (0 :> Pure 1) -- prints 1 

L'istanza Applicative ci dà concatenazione molto ordinata:

xs = 1 :> 2 :> Pure 10 
ys = 3 :> 4 :> Pure 20 

xs *> ys   == 1 :> 2 :> 3 :> 4 :> Pure 20 -- use right end 
xs <* ys   == 1 :> 2 :> 3 :> 4 :> Pure 10 -- use left end 
(+) <$> xs <*> ys == 1 :> 2 :> 3 :> 4 :> Pure 30 -- combine ends 

Possiamo mappare sulla lista elem Ent, se un po 'tortuoso:

import Data.Bifunctor -- included in base-4.8! 

hoistFree (first (+10)) xs == 11 :> 12 :> Pure 10 

E possiamo fare uso di iter, naturalmente.

iter (uncurry (+)) (0 <$ xs) == 3 -- sum list elements 

Sarebbe bello se LWE potrebbe essere un Bitraversable (e Bifunctor e Bifoldable), perché allora potremmo accedere agli elementi della lista in modo più generico e di principio. Per questo abbiamo sicuramente bisogno di una newtype:

newtype LWE a e = LWE (Free ((,) a) e) deriving (lots of things) 

instance Bifunctor LWE where bimap = bimapDefault 
instance Bifoldable LWE where bifoldMap = bifoldMapDefault 
instance Bitraversable LWE where bitraverse = ... 

Ma a questo punto si potrebbe pensare solo scrivendo la pianura ADT fuori e scrivere le istanze Applicative, Monad e Bitraversable in un paio di righe di codice. In alternativa, si potrebbe usare lens e scrivere un Traversal per gli elementi della lista:

import Control.Lens 

elems :: Traversal (LWE a e) (LWE b e) a b 
elems f (Pure e) = pure (Pure e) 
elems f (x :> xs) = (:>) <$> f x <*> elems f xs 

Pensando ulteriormente lungo questa linea, si dovrebbe fare un Lens per l'elemento terminale. Questo è un po 'un vantaggio rispetto all'interfaccia generica Free, poiché sappiamo che ogni numero finito LWE deve contenere esattamente un elemento di estremità, e possiamo farlo esplicitamente avendo uno Lens per esso (piuttosto che uno Traversal o Prism).

end :: Lens (LWE a e) (LWE a e') e e' 
end f (Pure e) = Pure <$> f e 
end f (x :> xs) = (x :>) <$> end f xs