Quais são os usos dos tipos de dados algébricos?

15

Estou lendo sobre Tipos de dados algébricos (graças a Richard Minerich eu encontrei este excelente explicação do conceito). Embora eu ache que entendo a noção de tipos de soma e tipos de produto etc., o que não entendo é como os Tipos de Dados Algébricos são úteis além da especificação da correspondência de padrões. Que outras coisas podem ser feitas com a correspondência de padrões da ADT?

EDIT: Eu não estou perguntando o que um desenvolvedor pode fazer com o ADT que não pode ser feito com objetos. Eu estou perguntando se há outras operações que os ADTs permitem; Por exemplo, alguém pode fazer um raciocínio adicional sobre os tipos envolvidos se os ADTs são empregados? Os ADTs facilitam algum tipo de análise de tipo que não seria possível sem eles?

    
por Onorio Catenacci 05.05.2011 / 16:10
fonte

2 respostas

10

Tipos de dados algébricos são distintos na medida em que podem ser construídos a partir de vários tipos de "coisas". Por exemplo, uma árvore pode conter nada (vazio), uma folha ou um nó.

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

Como um nó é composto de duas árvores, os tipos de dados algébricos podem ser recursivos.

A correspondência de padrões permite que os tipos de dados algébricos sejam desconstruídos de forma a manter a segurança de tipos. Considere a seguinte implementação de profundidade e seu equivalente no pseudocódigo:

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

comparado a:

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)

Isto tem a desvantagem de o programador ter que lembrar do caso Vazio antes da Folha, para que o campo1 não seja acessado em uma árvore Vazia. Da mesma forma, o caso Folha deve ser declarado antes do caso Nó, para que o campo2 não seja acessado na Folha. Assim, a segurança do tipo não é mantida pela linguagem, mas impõe carga cognitiva adicional ao programador. A propósito, estou pegando esses exemplos diretamente das páginas da Wikipedia.

É claro que uma linguagem de caracteres de tipo de pato poderia fazer algo assim:

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

Assim, os tipos de dados algébricos podem não ser estritamente melhores que seus equivalentes de OOP, mas fornecem um conjunto diferente de tensões para trabalhar com a construção de software.

    
por 05.05.2011 / 17:49
fonte
9

Não estou tão certo de que a explicação seja excelente .

Tipos de dados algébricos são usados para criar estruturas de dados, como listas e árvores.

Por exemplo, as árvores de análise são facilmente representadas com estruturas de dados algébricos.

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>
                | ...

Na verdade, não seria necessário muito mais para representar a linguagem C.

Mas, na verdade, você pode fazer TUDO com os tipos de dados algébricos. Lisp prova, você pode fazer tudo com pares e os ADTs simplesmente fornecem um modo mais granular e seguro para essa abordagem.

Naturalmente, se você perguntar "O que você pode fazer com ADTs, que você não pode fazer com objetos?", a resposta é "nada". Apenas algumas vezes (na maioria das vezes) você descobrirá que as soluções em ADTs são significativamente menos detalhadas, enquanto aquelas baseadas em objetos são indiscutivelmente mais flexíveis. Então, para colocá-lo em uma árvore de análise representada com ADTs:

If(Call(Ident('likes_ADTs'),[Ident('you')]),
   Call(Ident('use_ADTs'),[Ident('you')]),
   Call(Ident('use_no_ADTs'),[Ident('you')]))
    
por 05.05.2011 / 16:46
fonte