Eine Liste, deren "Nil" einen Wert enthält?

Question

hat einige Standard-Haskell-Bibliothek einen Datentyp wie diese, die

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

definieren, deren eine Liste Abschlusselement trägt, einen Wert von einem bestimmten Typ?

So ist ListWithEnd() isomorph zu [] und ListWithEnd Void isomorph zu unendlichen Strömen. Oder anders betrachtet, ist ListWithEnd e a ganz in der Nähe ConduitM() a Identity e ..

Answer 1

Wir ListWithEnd definieren können wie folgt:

import Control.Monad.Free 

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

Wir in der Regel eine Erwartung haben, dass abstrakte oder allgemeine Darstellungen uns mit einer Gesamtreduktion von vorformulierten belohnen sollte . Mal sehen, was diese Darstellung uns bietet.

{-# LANGUAGE PatternSynonyms #-} 

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

Wir Karte, falten und das Endglied durchqueren über:

Auf jeden Fall werden wir ein Muster Synonym für die cons Fall definieren

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

Die Applicative Instanz gibt uns sehr saubere Verkettung:

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 

Wir können über die Liste elem abbilden ents, wenn auch ein wenig gewunden:

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

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

Und wir können von iter, natürlich machen.

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

Es wäre schön, wenn LWE ein Bitraversable sein könnte (und Bifunctor und Bifoldable), denn dann könnten wir die Listenelemente in einer allgemeineren und prinzipien Weise zugreifen. Dafür brauchen wir auf jeden Fall eine 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 = ... 

Aber an diesem Punkt könnten wir darüber nachdenken, nur die Ebene ADT aus Schreiben und Schreiben der Applicative, Monad und Bitraversable Instanzen in ein paar Zeilen Code. Alternativ könnten wir lens verwenden und eine Traversal für die Listenelemente schreiben:

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 

Denken weiter entlang dieser Linie sollten wir eine Lens für das Endglied machen. Dies ist ein bisschen ein Bonus gegenüber der generischen Free Schnittstelle, da wir wissen, dass jedes endliche LWE genau ein Endelement enthalten muss, und wir können dies explizit machen, indem wir eine Lens dafür haben (statt einer Traversal oder 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