Por que Bounded não é uma subclasse de Enum em Haskell

9

Parece que qualquer instância vinculada deve ter uma implementação sã do Enum. Pessoalmente, não consigo pensar em um contra-exemplo, embora, se alguém criar um que não seja patológico, entenderei por que não é esse o caso.

Ao executar :inas duas classes de tipos, parece que a única exceção atualmente na biblioteca padrão é para tuplas, que são limitadas, mas não enums. No entanto, qualquer tupla limitada também deve ser enumerável de maneira sã, simplesmente incrementando o último elemento e, em seguida, contornando quando se trata de maxBound.

Essa alteração provavelmente envolveria também a adição predBe / nextBou algo parecido a Bounded, para uma maneira segura / em loop de percorrer os valores de Enum. Nesse caso, toEnum 0 :: (...)seria igual a(toEnum 0, toEnum 0, ...) :: (...)

ponto e vírgula
fonte
3
Não é possível responder a isso com autoridade, mas considere o intervalo de todos os números reais entre 0 e 1. Ele possui limites inferiores e superiores claros, mas possui incontáveis ​​membros infinitos.
Doval
@Doval é um ponto justo. No entanto, o mesmo poderia ser dito sobre todos os números reais em geral (incontáveis ​​membros infinitos), mas Double/ Floate todos os tipos similares implementados de Enumqualquer maneira, eles apenas produzem succ = (+ 1)e fromEnum = truncate. O jeito de Haskell, na verdade, faz sentido do ponto de vista da praticidade, caso contrário [0, 0,5 ..] e similares não funcionariam, então parece que Haskell não se preocupa com a responsabilidade quando se trata de Enums.
ponto
11
Eu não estava ciente de que succé (+1). Isso é estranho, porque Doublee Floatnão tem precisão infinita e, portanto, é enumerável - succpoderia ter sido definido como +1 ULP .
Doval 30/03
2
@ Doval Acho que a razão disso foi porque a equipe principal da Haskell queria [1 ..] significar a mesma coisa com Doubles que significa com Ints.
ponto
@semicolon dobros e flutuadores não são números reais (por exemplo, não é possível armazenar o PI em um dobro sem perder alguma precisão), portanto eles são enumeráveis
jk.

Respostas:

8

Um exemplo prático que eu gosto vem do mundo das linguagens de programação: o conjunto de tipos em um sistema OO é limitado e discreto, mas não enumerável, e parcialmente ordenado, mas não totalmente ordenado.

A ordem parcial em questão é a relação de subtipagem <:. O limite superior seria então o tipo superior (que C # chama objecte Scala chama Any), e o limite inferior seria o tipo inferior (Scala Nothing; C # / Java não tem equivalente para falar).

No entanto, não há como enumerar todos os tipos no sistema de tipos, portanto você não pode escrever um instance Enum Type. Isso deve ficar claro: os usuários podem escrever seus próprios tipos, para que não haja como saber com antecedência. Você pode enumerar todos os tipos em qualquer programa, mas não em todo o sistema.

Da mesma forma, (de acordo com uma certa definição razoável de subtipagem), <:é reflexivo, transitivo e anti-simétrico, mas não total . Existem pares de tipos que não são relacionados <:. ( Cate Dogsão ambos subtipos de Animal, mas nenhum é um subtipo do outro.)


Suponha que estamos escrevendo um compilador para uma linguagem OO simples. Aqui está a representação dos tipos em nosso sistema:

data Type = Bottom | Class { name :: String, parent :: Type } | Top

E a definição da relação de subtipagem:

(<:) :: Type -> Type -> Bool
Bottom <: _ = True
Class _ _ <: Bottom = False
Class n t <: s@(Class m _)
    | n == m = True  -- you can't have different classes with the same name in this hypothetical language
    | otherwise = t <: s  -- try to find s in the parents of this class
Class _ _ <: Top = True
Top <: Top = True
Top <: _ = False

Isso também nos dá uma relação de super tipagem.

(>:) :: Type -> Type -> Bool
t >: s = s <: t

Você também pode encontrar o limite superior mínimo de dois tipos,

lub :: Type -> Type -> Type
lub Bottom s = s
lub t Bottom = t
lub t@(Class _ p) s@(Class _ q) =
    | t >: s = t
    | t <: s = s
    | p >: s = p
    | t <: q = q
    | otherwise = lub p q
lub Top _ = Top
lub _ Top = Top

Exercício: mostre que Typeforma um poset completo delimitado de duas maneiras, abaixo <:e abaixo >:.

Benjamin Hodgson
fonte
Awesome thanks! Isso responde minha pergunta completamente e também responde à minha pergunta de acompanhamento sobre Ord. Eq teria problemas semelhantes? Onde um tipo não equável pode ter um maxBound ou um minBound. Nesse caso, Cat == Dog deve retornar falso, pois são classes diferentes, ou seria indecidível por causa da posição da árvore nem colocar acima ou abaixo do outro?
ponto
Um pedido implica uma igualdade - basta definir x == y = x <= y && y <= x. Se eu estivesse projetando uma Posetclasse, teria class Eq a => Poset a. Um rápido Google confirma que outras pessoas tiveram a mesma ideia .
Benjamin Hodgson
Desculpe, minha pergunta foi ambígua. O que eu quis dizer foi se Bounded implicava Eq, mesmo que isso não implique Ord.
ponto
@semicolon Novamente, não há relação entre as duas classes. Considere data Bound a = Min | Val a | Maxqual aumenta um tipo acom +∞e -∞elementos. Por construção Bound apode ser feita sempre uma instância Bounded, mas ele só estaria equatable se o tipo subjacente aé
Benjamin Hodgson
tudo bem justo o suficiente. Eu acho que um exemplo poderia ser funções que recebem e retornam valores do tipo Double, onde const (1/0)é maxBounde const (negate 1/0)é, minBoundmas \x -> 1 - xe \x -> x - 1são incomparáveis.
ponto
4

É porque as operações são independentes, portanto, vinculá-las a um relacionamento de subclasse não compram nada para você. Digamos que você desejasse criar um tipo personalizado implementado Bounded, talvez Doublesrestrito entre um máximo e um mínimo, mas você não precisou de nenhuma das Enumoperações. Se Boundedfosse uma subclasse, você teria que implementar todas as Enumfunções de qualquer maneira, apenas para compilar.

Realmente não importa se existe uma implementação razoável para Enum, ou qualquer outro número de classes de tipo. Se você realmente não precisa, não deve ser forçado a implementá-lo.

Compare isso com dizer, Orde Eq. Lá, as Ordoperações dependem Eqdelas, portanto, faz sentido exigir que a subclasse evite duplicação e garanta consistência.

Karl Bielefeldt
fonte
11
Nesses casos, faz parte da definição. Todas as mônadas também são aplicadoras e funcionadoras por definição, portanto você não pode cumprir o "contrato" da mônada sem cumprir as outras. Não estou familiarizado o suficiente com a matemática para saber se essa é uma relação fundamental ou uma definição imposta, mas de qualquer forma, estamos presos a ela agora.
Karl Bielefeldt
6
@semicolon A documentaçãoBounded diz "Ord não é uma superclasse de Bounded, pois tipos que não são totalmente ordenados também podem ter limites superior e inferior".
Benjamin Hodgson
11
@BenjaminHodgson Nem sequer pensou em tipos parcialmente pedidos. +1 para um exemplo não patológico e para citar a documentação.
Doval 30/03
11
@semicolon Um exemplo de pedido parcial do mundo dos computadores pode estar subtipando em idiomas OO. Escrever <:para é um subtipo de , ∀ T S. T <: S ∨ S <: Tnão é válido (por exemplo, int !<: bool ∧ bool !<: int). Você provavelmente enfrentaria isso se estivesse escrevendo um compilador.
Benjamin Hodgson
11
@BenjaminHodgson ah ok. Assim, por exemplo, se A é uma superclasse de B e C e D é uma subclasse de B e C, então B e C são incomparáveis, mas A e D são máx / min?
ponto