Listas definidas como ¿Tal vez en Haskell? Por qué no?

Question

Usted no offen ver Maybe List excepción de control de errores, por ejemplo, porque las listas son un poco Maybe mismos: tienen su propio "Nothing ': [] y su propia' Just": (:). Escribí un tipo de lista usando Maybe y funciones para convertir listas estándar y "experimentales". 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) 

¿Qué opinas al respecto, como un intento de reducir la repetición, para generalizar?

Los árboles también se podría definir el uso de estas listas:

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

no he probado esta última pieza de código, sin embargo.

Answer 1

Todos ADTs son isomorfos (casi - véase el final) a alguna combinación de (,), Either, (), (->), Void y Mu donde

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

y Mu calcula el punto fijo de un funtor

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

así que por ejemplo

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

es la misma que

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

que en sí misma es isomorfo a

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

desde

data Maybe a = Nothing | Just a 

es isomorfo a

newtype Maybe a = Maybe (Either() a) 

tiene

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

que puede ser inline en las mu a

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

y su definición

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

es sólo el despliegue de la Mu y la eliminación del exterior Tal vez (correspondiente a listas no vacías)

y listo ...

un par de cosas

1. Uso de los ADT personalizados aumenta la claridad y el tipo de seguridad

2. Esta universalidad es útil: veo GHC.Generic

---

Vale, dijo casi isomorfo. No es exactamente, a saber

hmm = List (Just undefined) 

no tiene valor equivalente en la definición de las listas [a] = [] | (a:[a]). Esto se debe a que los tipos de datos Haskell son coinductivos y han sido a point of criticism of the lazy evaluation model. Usted puede obtener en torno a estos problemas utilizando sólo sumas y productos estrictas (y por llamar a funciones de valor), y añadiendo un constructor de datos especiales "perezoso"

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 

y luego todos los isomorfismos se pueden codificar con fidelidad.

Answer 2

Puede definir listas en términos de Maybe, pero no de esa manera. Su tipo List no puede estar vacío. ¿O pretendía que Maybe (List a) fuera el reemplazo de [a]? Esto parece malo ya que no distingue la lista y tal vez los tipos.

Esto funcionaría

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

Esto tiene algunos problemas. Primero usar esto sería más detallado que las listas habituales, y segundo, el dominio no es isomorfo para las listas ya que tenemos un par allí (que puede estar indefinido, agregando un nivel extra en el dominio).

Answer 3

Puede definir listas de muchas maneras en Haskell. Por ejemplo, como funciones:

{-# 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 

El truco de esta implementación es que las listas están siendo representadas como funciones que ejecutan un pliegue sobre los elementos de la lista:

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

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

En cualquier caso, lo que realmente es el contrato (o leyes) que el tipo y sus operaciones siguen, y el funcionamiento de la implementación. Básicamente, cualquier implementación que cumpla con el contrato le dará los programas correctos, y las implementaciones más rápidas le proporcionarán programas más rápidos.

¿Cuál es el contrato de listas?Bueno, no voy a expresarlo con todo detalle, pero las listas de obedecer a declaraciones como éstas:

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

EDIT: Y para atar a este augustss' respuesta:

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

Si se trata de una lista, que debe ser una instancia de Functor, ¿verdad?

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 

Aquí hay un problema: se puede hacer List una instancia de Functor, pero su Quizás lista no es: incluso si Maybe no era ya una instancia de Functor por derecho propio, no se puede hacer directamente una construcción como Maybe . List en una instancia de cualquier cosa (necesitaría un tipo de envoltura).

De forma similar para otras clases de tipos.

---

Una vez dicho esto, con su formulación se puede hacer esto, que no se puede hacer con el estándar Haskell estados:

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

Una lista Quizás todavía no sería comonadic sin embargo.

Answer 5

Cuando comencé a usar Haskell, también intenté representar cosas de tipos existentes tanto como pude sobre la base de que es bueno evitar la redundancia. Mi comprensión actual (¡objetivo móvil!) Tiende a involucrar más la idea de una red multidimensional de concesiones. No voy a dar ninguna "respuesta" aquí tanto como pegar ejemplos y preguntar "¿ves lo que quiero decir?" Espero que ayude de todos modos.

Vamos a echar un vistazo a un poco de código Darcs:

data UseCache = YesUseCache | NoUseCache 
    deriving (Eq) 

data DryRun = YesDryRun | NoDryRun 
    deriving (Eq) 

data Compression = NoCompression 
       | GzipCompression 
    deriving (Eq) 

¿Notó que estos tres tipos podrían Todos han sido Bool 's? ¿Por qué crees que los hackers de Darcs decidieron que deberían introducir este tipo de redundancia en su código? Como otro ejemplo, esta es una pieza de código que cambiamos hace unos años:

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

¿Por qué cree que decidimos que el segundo código fue una mejora con respecto a la primera?

Finalmente, aquí hay un poco de código de algunos de mis trabajos del día. Utiliza la sintaxis newtype que augustss mencionó,

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

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

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

Aquí se dará cuenta de que he hecho lo curioso de tomar un perfecto tipo Text y luego envolverlo en tres cosas diferentes. Las tres cosas no tienen ninguna característica nueva en comparación con el antiguo Text. Solo están allí para ser diferentes. Para ser sincero, no estoy del todo seguro de si fue una buena idea para mí hacer esto. Provisionalmente creo que fue porque manipulo muchos trozos de texto diferentes por muchas razones, pero el tiempo dirá.

¿Puedes ver a qué me refiero?