¿Cuáles son los usos de los tipos de datos algebraicos?

15

Estoy leyendo sobre Tipos de datos algebraicos (gracias a Richard Minerich encontré esto explicación excelente del concepto). Si bien creo que entiendo la noción de tipos de suma y tipos de productos, etc., lo que no entiendo es cómo los tipos de datos algebraicos son útiles más allá de especificar la coincidencia de patrones. ¿Qué otras cosas se pueden hacer con ADT más allá de la coincidencia de patrones?

EDITAR: no estoy preguntando qué puede hacer un desarrollador con ADT que no se puede hacer con objetos. Estoy preguntando si hay otras operaciones permitidas por ADT; por ejemplo, ¿se puede hacer un razonamiento adicional sobre los tipos involucrados si se emplean ADT? ¿Facilitan ADT algún tipo de análisis de tipo que no sería posible sin ellos?

    
pregunta Onorio Catenacci 05.05.2011 - 16:10
fuente

2 respuestas

10

Los tipos de datos algebraicos son distintos porque pueden construirse a partir de varios tipos de "cosas". Por ejemplo, un árbol puede contener nada (vacío), una hoja o un nodo.

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

Dado que un Nodo se compone de dos Árboles, los tipos de datos algebraicos pueden ser recursivos.

La coincidencia de patrones permite que los tipos de datos algebraicos se descompongan de una manera que mantenga la seguridad de tipos. Considere la siguiente implementación de profundidad y su pseudocódigo equivalente:

depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)

comparado con:

switch on (data.constructor)
  case Empty:
    return 0
  case Leaf:
    return 1
  case Node:
    let l = data.field1
    let r = data.field2
    return 1 + max (depth l) (depth r)

Esto tiene la desventaja de que el programador debe recordar que se debe colocar Vacío antes de Hoja para que no se acceda a campo1 en un árbol Vacío. Del mismo modo, el caso Leaf se debe declarar antes del caso Node para que no se acceda a field2 en Leaf. Por lo tanto, el lenguaje no mantiene el tipo de seguridad, sino que impone una carga cognitiva adicional al programador. Por cierto, estoy captando estos ejemplos directamente de las páginas de wikipedia.

Por supuesto, un idioma que escribe pato podría hacer algo como esto:

class Empty
  def depth
    0
  end
end

class Leaf
  def depth
    1
  end
end

class Node
  attr_accessor :field1, :field2

  def depth
    1 + [field1.depth, field2.depth].max
  end
end

Por lo tanto, los tipos de datos algebraicos pueden no ser estrictamente mejores que su equivalente de POO, pero proporcionan un conjunto diferente de tensiones con las que trabajar cuando se construye un software.

    
respondido por el Rein Henrichs 05.05.2011 - 17:49
fuente
9

No estoy tan seguro de que la explicación sea tan excelente

Los tipos de datos algebraicos se utilizan para crear estructuras de datos, como listas y árboles.

Por ejemplo, los árboles de análisis se representan fácilmente con estructuras de datos algebraicos.

data BinOperator = Add
                 | Subtr
                 | Div
                 | Mult
                 | Mod
                 | Eq
                 | NotEq
                 | GreaterThan
                 | LogicAnd
                 | LogicOr
                 | BitAnd
                 | BitOr
                 | ...

data UnOperator = Negate
                | Not
                | Increment
                | Decrement
                | Complement
                | Ref
                | DeRef


data Expression = Empty
                | IntConst Int
                | FloatConst Float
                | StringConst String
                | Ident String
                | BinOp BinOperator Expression Expression
                | UnOp UnOperator Expression Bool //prefix or not
                | If Expression Expression Expression
                | While Expression Expression Bool //while vs. do while
                | Block List<Expression>
                | Call Expression List<Expression>
                | ...

En realidad, no se necesitaría mucho más para representar el lenguaje C

.

Pero realmente, puedes hacer TODO con tipos de datos algebraicos. Lisp demuestra que puede hacer todo con pares y ADT, simplemente proporcione una forma más granular y segura para este enfoque.

Por supuesto, si preguntas, "¿Qué puedes hacer con los TDA, que no puedes hacer con los objetos?", la respuesta es "nada". Solo en ocasiones (en su mayoría) encontrará que las soluciones en los ADT son significativamente menos detalladas, mientras que las basadas en objetos son posiblemente más flexibles. Así que para ponerlo en un árbol de análisis representado con ADTs:

If(Call(Ident('likes_ADTs'),[Ident('you')]),
   Call(Ident('use_ADTs'),[Ident('you')]),
   Call(Ident('use_no_ADTs'),[Ident('you')]))
    
respondido por el back2dos 05.05.2011 - 16:46
fuente

Lea otras preguntas en las etiquetas