¿Por qué los tipos de datos algebraicos Haskell "están cerrados"?

Question

Corrígeme si me equivoco, pero parece que los tipos de datos algebraicos en Haskell son útiles en muchos de los casos en los que usarías clases y herencia en los lenguajes OO. Pero hay una gran diferencia: una vez que se declara un tipo de datos algebraicos, no se puede extender a otro lado. Está cerrado". En OO, puede extender clases ya definidas. Por ejemplo:

data Maybe a = Nothing | Just a 

No hay manera de que de alguna manera pueda agregar otra opción a este tipo más adelante sin modificar esta declaración. ¿Cuáles son los beneficios de este sistema? Parece que el modo OO sería mucho más extensible.

Answer 1

El hecho de que ADT esté cerrado hace que sea mucho más fácil escribir funciones totales. Estas son funciones que siempre producen un resultado, para todos los valores posibles de su tipo, ej.

maybeToList :: Maybe a -> [a] 
maybeToList Nothing = [] 
maybeToList (Just x) = [x] 

Si Maybe estaban abiertos, alguien podría añadir un constructor adicional y la función maybeToList rompería pronto.

En OO esto no es un problema, cuando se usa la herencia para extender un tipo, porque cuando se llama a una función para la que no existe una sobrecarga específica, puede simplemente usar la implementación para una superclase. Es decir, puede llamar al printPerson(Person p) muy bien con un objeto Student si Student es una subclase de Person.

En Haskell, normalmente usaría clases de encapsulado y tipo cuando necesita extender sus tipos. Por ejemplo:

class Eq a where 
    (==) :: a -> a -> Bool 

instance Eq Bool where 
    False == False = True 
    False == True = False 
    True == False = False 
    True == True = True 

instance Eq a => Eq [a] where 
    []  == []  = True 
    (x:xs) == (y:ys) = x == y && xs == ys 
    _  == _  = False 

Ahora, la función == está completamente abierta, se puede añadir sus propios tipos por lo que es una instancia de la clase Eq.

---

Tenga en cuenta que se ha trabajado en la idea de extensible datatypes, pero eso no es definitivamente parte de Haskell aún.

Answer 2

Bien, por "abrir", aquí significa que "se puede derivar de" y no abre en el sentido de Ruby y Smalltalk, donde se puede extender una clase con nuevos métodos en tiempo de ejecución, ¿verdad?

En cualquier caso, tenga en cuenta dos cosas: primero, en la mayoría de los lenguajes de OO que se basan principalmente en la herencia, hay una forma de declarar una clase para restringir su capacidad de heredarse. Java tiene "final", y hay hacks para esto en C++. Entonces, con eso, solo está haciendo una opción por defecto en otros lenguajes OO.

En segundo lugar, puede crear un nuevo tipo que utiliza el ADT cerrado y agrega otros métodos o implementaciones diferentes. Entonces no estás realmente restringido de esa manera. Nuevamente, parecen tener formalmente la misma fuerza; lo que puedes expresar en uno puede expresarse en el otro.

Lo cierto es que la programación funcional realmente es un paradigma diferente ("patrón"). Si lo hace con la expectativa de que debería ser como un lenguaje OO, se sorprenderá con regularidad.

Answer 3

Si se escribe una función como

maybeToList Nothing = [] 
maybeToList (Just x) = [x] 

entonces usted sabe que nunca va a producir un error de ejecución debido a que ha cubierto todos los casos. Esto deja de ser cierto tan pronto como el tipo Maybe sea extensible. En los casos en que necesite un tipo extensible (y son más raros de lo que cree), la solución canónica de Haskell es usar una clase de tipo.

Answer 4

En primer lugar, como contrapunto a la respuesta de Charlie, esto no es intrínseco a la programación funcional. OCaml tiene el concepto de open unions or polymorphic variants, que esencialmente hace lo que quiere.

En cuanto a qué, creo que esta elección se hizo para Haskell porque

• esto permite que los tipos sean previsibles - su son sólo un número finito de constructores para cada
• es fácil de definir su propio tipos.
• muchas funciones de Haskell son polimórficas, y las clases le permiten extender tipos personalizados para ajustarse a los parámetros de la función (piense en las interfaces de Java).

Así que si usted prefiere tener un tipo data Color r b g = Red r | Blue b | Green g, es fácil de hacer, y se puede fácilmente hacer que actúe como una mónada o un funtor o como otras funciones necesitan.

Answer 5

de verificación "Abrir los tipos de datos y funciones abiertas" http://lambda-the-ultimate.org/node/1453

En lenguajes orientados a objetos, es fácil de extender datos definiendo nuevos clases, pero es difícil añadir nuevas funciones. En funcionales idiomas, la situación se invierte: Añadir nuevas funciones no plantea problemas, pero datos que se extienden (añadiendo nuevos constructores de datos) requiere modificar código existente. El problema de admitir ambas direcciones de extensibilidad de se conoce como el problema de expresión . Presentamos los tipos de datos abiertos y las funciones abiertas como una solución liviana al problema de la expresión en el lenguaje Haskell. La idea es que los constructores de los tipos de datos abiertos, y las ecuaciones de las funciones abiertas pueden aparecer dispersos en un programa . En particular, pueden residir en diferentes módulos. La semántica prevista es la siguiente: el programa debe comportarse como si los tipos de datos y las funciones se cerraran, definidos en un solo lugar. El orden de las ecuaciones de función está determinado por la coincidencia de patrón de mejor ajuste , donde un patrón específico tiene prioridad sobre y no específico. Mostramos que nuestra solución es aplicable al problema de expresión , programación genérica y excepciones. Dibujamos dos implementaciones. Una simple, derivada de la semántica, y una basada en módulos mutuamente recursivos que permite la compilación por separado.

Answer 6

La respuesta tiene que ver con la de qué manera el código es fácil de extender, una tensión entre las clases y tipos de datos algebraicos que Phil Wadler apodado "el problema de la expresión":

• Con los datos algebraica tipos,

  • es muy barato añadir una nueva operación en cosas: sólo tiene que definen un nuevo functi en. Todas las funciones anteriores en esas cosas continúan sin cambios.

  • Es muy caro para añadir un nuevo tipo de cosas : usted tiene que añadir un nuevo constructor de un tipo de datos existente, y hay que editar y volver a compilar todas las funciones que utiliza ese tipo.

• Con clases,

  • Es muy barato añadir un nuevo tipo de cosas: sólo tiene que añadir una nueva subclase, y cuando sea necesario se definen métodos especializados, en ese clase, para todas las operaciones existentes. La superclase y todas las demás subclases continúan sin cambios.

  • Es muy caro para añadir una nueva operación en cosas: tienes que añadir una nueva declaración del método de la superclase y potencialmente agregar una definición del método para cada subclase existente. En la práctica, la carga varía según el método.

Por lo tanto, los tipos de datos algebraicos están cerradas debido a un tipo de cierre es compatible con ciertos tipos de evolución programa bien. Por ejemplo, si sus tipos de datos definen un idioma, es fácil agregar nuevos pasos de compilación sin invalidar los antiguos o cambiar los datos.

Es posible tener tipos de datos "abiertos", pero excepto en circunstancias cuidadosamente controladas, la verificación de tipos se vuelve difícil. Todd Millstein hizo un poco de very beautiful work en un diseño de lenguaje que admite tipos algebraicos abiertos y funciones extensibles, todo con un comprobador de tipos modular. Su lectura me pareció un gran placer de leer.

Answer 7

Otra forma intuitiva (más o menos) de mirar a tipos de datos y clases de tipos frente a clases orientadas a objetos es la siguiente:

Una clase Foo en un lenguaje OO representa tanto un tipo concreto Foo así como la clase de todos Foo -types: los que se derivan directa o indirectamente de Foo.

En lenguajes orientados a objetos, que acaba de pasar a implícitamente programa contra la clase de Foo -Tipos que le permite "extender" Foo .

Answer 8

Algunos excelentes respuestas en este (la verdad de edad) pregunta, pero me siento que tengo que tirar mis pocos centavos en.

No hay manera de que de alguna manera puedo añadir otra opción para este tipo después sin modificando esta declaración. ¿Cuáles son los beneficios de este sistema? Parece que el modo OO sería mucho más extensible.

La respuesta a esto, creo, es que el tipo de extensibilidad que las cantidades abiertas dan es no siempre es un plus, y que, en consecuencia, el hecho de que OO fuerzas esto en usted es una debilidad.

La ventaja de uniones cerradas es su exhaustividad: si ha arreglado todas las alternativas en tiempo de compilación, entonces puede estar seguro de que no habrá casos imprevistos que su código no pueda manejar. Esta es una propiedad valiosa en muchos dominios problemáticos, por ejemplo, en árboles sintácticos abstractos para idiomas. Si está escribiendo un compilador, las expresiones del lenguaje caen en un conjunto predefinido y cerrado de subcajas; usted hace no ¡quiera que las personas puedan agregar nuevas subcajas en tiempo de ejecución que su compilador no comprenda!

De hecho, los AST del compilador son uno de los ejemplos motivadores de la Banda de los Cuatro clásicos para Visitor Pattern, que es la contraparte de OOP a sumas cerradas y concordancia exhaustiva de patrones. Es instructivo reflexionar sobre el hecho de que los programadores de OO terminaron inventando un patrón para recuperar sumas cerradas.

Del mismo modo, los programadores procedurales y funcionales han inventado patrones para obtener el efecto de las sumas. El más simple es la codificación "registro de funciones", que corresponde a las interfaces OO. Un registro de funciones es, efectivamente, una tabla de envío . (¡Nótese que los programadores C han estado usando esta técnica durante siglos!) El truco es que a menudo hay una gran cantidad de funciones posibles de un tipo dado, a menudo infinitamente muchas. Entonces, si tiene un tipo de registro cuyos campos son funciones, entonces eso puede respaldar fácilmente un conjunto de alternativas astronómicamente grande o infinito. Y lo que es más, dado que los registros se crean en tiempo de ejecución y se pueden realizar de forma flexible en función de las condiciones de tiempo de ejecución, las alternativas son con límite de tiempo.

El comentario final me gustaría hacer es que, en mi mente, OO ha hecho demasiadas personas creen que la extensibilidad es sinónimo de el enlace en tiempo (por ejemplo, la posibilidad de añadir nuevos sub-casos a un tipo en tiempo de ejecución), cuando esto simplemente no es verdad en general. Encuadernación tardía es una técnica para la extensibilidad. Otra técnica es composición -construir objetos complejos a partir de un vocabulario fijo de bloques de construcción y reglas para ensamblarlos juntos. El vocabulario y las reglas son idealmente pequeños, pero diseñados para que tengan interacciones ricas que te permitan construir cosas muy complejas.

La programación funcional -y los sabores estáticos ML/Haskell en particular- han enfatizado durante mucho tiempo la composición sobre el encuadernado tardío. Pero en realidad, ambos tipos de técnicas existen en ambos paradigmas, y deberían estar en el juego de herramientas de un buen programador.

También vale la pena señalar que los lenguajes de programación en sí mismos son fundamentalmente ejemplos de composición. Un lenguaje de programación tiene una sintaxis finita, con suerte simple, que le permite combinar sus elementos para escribir cualquier programa posible. (Esto de hecho se remonta al ejemplo anterior de Compiladores/Patrón de visitante y lo motiva.)