Liste definite come Forse in Haskell? Perchè no?

Question

Non è offen vedere Maybe List tranne che per la gestione degli errori, ad esempio, perché le liste sono un po 'se stessi Maybe: hanno il loro "Nothing ': [] e la propria' Just": (:). Ho scritto un tipo di lista usando Maybe e funzioni per convertire liste standard e "sperimentali". toStd . toExp == id.

data List a = List a (Maybe (List a)) 
    deriving (Eq, Show, Read) 

toExp [] = Nothing 
toExp (x:xs) = Just (List x (toExp xs)) 

toStd Nothing = [] 
toStd (Just (List x xs)) = x : (toStd xs) 

Cosa ne pensi, come un tentativo di ridurre la ripetizione, per generalizzare?

Alberi troppo potrebbe essere definito l'utilizzo di questi elenchi:

type Tree a = List (Tree a, Tree a) 

non ho ancora testato questo ultimo pezzo di codice, però.

Answer 1

Tutti ADT sono isomorfi (quasi - vedi end) per una qualche combinazione di (,), Either, (), (->), Void e Mu dove

data Void --using empty data decls or 
newtype Void = Void Void 

e Mu calcola il punto fisso di un funtore

newtype Mu f = Mu (f (Mu f)) 

quindi ad esempio

data [a] = [] | (a:[a]) 

è uguale

data [a] = Mu (ListF a) 
data ListF a f = End | Pair a f 

che si è isomorfo a

newtype ListF a f = ListF (Either() (a,f)) 

dal

data Maybe a = Nothing | Just a 

è isomorfo a

newtype Maybe a = Maybe (Either() a) 

avete

newtype ListF a f = ListF (Maybe (a,f)) 

che può essere inline nei mu per

data List a = List (Maybe (a,List a)) 

e la tua definizione

data List a = List a (Maybe (List a)) 

è solo lo svolgersi del Mu e l'eliminazione del esterna Forse (corrispondente a liste non vuote)

e il gioco è fatto ...

un paio di cose

1. Uso ADT personalizzati aumenta la chiarezza e il tipo di sicurezza

2. Questa universalità è utile: vedo GHC.Generic

---

Va bene, detto quasi isomorfo. Non è esattamente, e cioè

hmm = List (Just undefined) 

non ha valore equivalente nella [a] = [] | (a:[a]) definizione di liste. Questo perché i tipi di dati Haskell sono coinduttivi ed è stato a point of criticism of the lazy evaluation model. È possibile aggirare questi problemi solo con le somme e prodotti severi (e chiamare da funzioni di valore), e l'aggiunta di un costruttore dati speciali "pigro"

data SPair a b = SPair !a !b 
data SEither a b = SLeft !a | SRight !b 
data Lazy a = Lazy a --Note, this has no obvious encoding in Pure CBV languages, 
--although Laza a = (() -> a) is semantically correct, 
--it is strictly less efficient than Haskell's CB-Need 

e poi tutti gli isomorfismi possono essere codificati con fedeltà.

Answer 2

È possibile definire elenchi in termini di Maybe, ma non in questo modo. Il tuo tipo non può essere vuoto. O intendevi sostituire Maybe (List a)[a]. Questo sembra male poiché non distingue l'elenco e forse i tipi.

Questo potrebbe funzionare

newtype List a = List (Maybe (a, List a)) 

Questo ha qualche problema. Il primo utilizzo di questo sarebbe più verboso delle solite liste, e in secondo luogo, il dominio non è isomorfo alle liste dato che abbiamo una coppia (che può essere indefinita, aggiungendo un livello extra nel dominio).

Answer 3

È possibile definire elenchi in vari modi in Haskell. Ad esempio, come funzioni:

{-# LANGUAGE RankNTypes #-} 

newtype List a = List { runList :: forall b. (a -> b -> b) -> b -> b } 

nil :: List a 
nil = List (\_ z -> z) 

cons :: a -> List a -> List a 
cons x xs = List (\f z -> f x (runList xs f z)) 

isNil :: List a -> Bool 
isNil xs = runList xs (\x xs -> False) True 

head :: List a -> a 
head xs = runList xs (\x xs -> x) (error "empty list") 

tail :: List a -> List a 
tail xs | isNil xs = error "empty list" 
tail xs = fst (runList xs go (nil, nil)) 
    where go x (xs, xs') = (xs', cons x xs) 

foldr :: (a -> b -> b) -> b -> List a -> b 
foldr f z xs = runList xs f z 

Il trucco per questa implementazione è che gli elenchi sono stati rappresentati come funzioni che eseguono una piega sugli elementi della lista:

fromNative :: [a] -> List a 
fromNative xs = List (\f z -> foldr f z xs) 

toNative :: List a -> [a] 
toNative xs = runList xs (:) [] 

In ogni caso, ciò che realmente è importante il contratto (o leggi) che seguono il tipo e le sue operazioni e la prestazione di implementazione. In sostanza, qualsiasi implementazione che soddisfi il contratto ti fornirà programmi corretti e implementazioni più veloci ti daranno programmi più veloci.

Qual è il contratto delle liste?Beh, io non ho intenzione di esprimere in dettaglio completo, ma le liste obbedire a dichiarazioni come questi:

1. head (x:xs) == x
2. tail (x:xs) == xs
3. [] == []
4. [] /= x:xs
5. Se xs == ys e x == y, poi x:xs == y:ys
6. foldr f z [] == z
7. foldr f z (x:xs) == f x (foldr f z xs)

EDIT: E per legare questo per augustss' risposta:

newtype ExpList a = ExpList (Maybe (a, ExpList a)) 

toExpList :: List a -> ExpList a 
toExpList xs = runList xs (\x xs -> ExpList (Just (x, xs))) (ExpList Nothing) 

foldExpList f z (ExpList Nothing) = z 
foldExpList f z (ExpList (Just (head, taill))) = f head (foldExpList f z tail) 

fromExpList :: ExpList a -> List a 
fromExpList xs = List (\f z -> foldExpList f z xs) 

Answer 4

Se si tratta di una lista, dovrebbe essere un esempio di Functor, giusto?

instance Functor List 
    where fmap f (List a as) = List (f a) (mapMaybeList f as) 

mapMaybeList :: (a -> b) -> Maybe (List a) -> Maybe (List b) 
mapMaybeList f as = fmap (fmap f) as 

Ecco un problema: si può fare List un'istanza di Functor, ma il vostro forse elenco non è: anche se Maybe non era già un caso di Functor a sé stante, non è possibile effettuare direttamente una costruzione come Maybe . List in un'istanza di qualsiasi cosa (avresti bisogno di un tipo di wrapper).

Analogamente per altri tipi di caratteri.

---

Detto questo, con la formulazione si può fare questo, che non si può fare con standard di Haskell liste:

instance Comonad List 
    where extract (List a _) = a 
     duplicate x @ (List _ y) = List x (duplicate y) 

Un Forse elenco ancora non sarebbe comonadic però.

Answer 5

Quando ho iniziato a utilizzare Haskell, ho provato a rappresentare le cose nei tipi esistenti il ​​più possibile sulla base del fatto che è opportuno evitare la ridondanza. La mia attuale comprensione (spostare l'obiettivo!) Tende a coinvolgere maggiormente l'idea di una rete multidimensionale di compromessi. Non darò alcuna "risposta" qui tanto quanto incollare esempi e chiedere "capisci cosa intendo?" Spero che aiuti comunque.

Diamo un'occhiata a un po 'di codice di Darcs:

data UseCache = YesUseCache | NoUseCache 
    deriving (Eq) 

data DryRun = YesDryRun | NoDryRun 
    deriving (Eq) 

data Compression = NoCompression 
       | GzipCompression 
    deriving (Eq) 

Avete notato che questi tre tipi potrebbero tutti sono stati Bool 's? Perché pensi che gli hacker di Darcs abbiano deciso di introdurre questo tipo di ridondanza nel loro codice? Come altro esempio, ecco un pezzo di codice abbiamo cambiato qualche anno fa:

type Slot = Maybe Bool     -- OLD code 
data Slot = InFirst | InMiddle | InLast -- newer code 

Perché pensi abbiamo deciso che il secondo codice è stato un miglioramento rispetto al primo?

Infine, ecco un po 'di codice da alcuni dei miei lavori di giornata. Esso utilizza la sintassi che newtype augustss menzionato,

newtype Role = Role { fromRole :: Text } 
    deriving (Eq, Ord) 

newtype KmClass = KmClass { fromKmClass :: Text } 
    deriving (Eq, Ord) 

newtype Lemma = Lemma { fromLemma :: Text } 
    deriving (Eq, Ord) 

Qui si noterà che ho fatto la cosa curiosa di prendere un buon perfettamente Text tipo e poi avvolgendolo in tre cose diverse. Le tre cose non hanno nuove funzionalità rispetto al semplice vecchio Text. Sono lì solo per essere diversi. Ad essere onesti, non sono del tutto sicuro se fosse una buona idea per me farlo. Ritengo provvisoriamente che sia stato perché ho manipolato un sacco di bit e parti di testo diversi per molte ragioni, ma il tempo lo dirà.

Riesci a vedere cosa sto cercando di ottenere?