Exponenciação em Haskell

91

Alguém pode me dizer por que o Prelúdio de Haskell define duas funções separadas para exponenciação (ou seja, ^e **)? Achei que o sistema de tipos deveria eliminar esse tipo de duplicação.

Prelude> 2^2
4
Prelude> 4**0.5
2.0
haskell exponent exponentiation pássaro do céu
fonte

Respostas:

130

Na verdade, existem três operadores de exponenciação: (^), (^^)e (**). ^é exponenciação integral não negativa, ^^é exponenciação inteira e **é exponenciação de ponto flutuante:

(^) :: (Num a, Integral b) => a -> b -> a
(^^) :: (Fractional a, Integral b) => a -> b -> a
(**) :: Floating a => a -> a -> a

A razão é a segurança de tipo: resultados de operações numéricas geralmente têm o mesmo tipo que o (s) argumento (s) de entrada. Mas você não pode elevar um Inta uma potência de ponto flutuante e obter um resultado do tipo Int. E então o sistema de tipos impede que você faça isso: (1::Int) ** 0.5produz um erro de tipo. O mesmo vale para (1::Int) ^^ (-1).

Outra forma de colocar isso: Numtipos são fechados em ^(eles não precisam ter um inverso multiplicativo), Fractionaltipos são fechados em ^^, Floatingtipos são fechados em **. Como não há Fractionalinstância para Int, você não pode elevá-lo a uma potência negativa.

Idealmente, o segundo argumento de ^seria estaticamente restrito para ser não negativo (atualmente, 1 ^ (-2)lança uma exceção de tempo de execução). Mas não há nenhum tipo para números naturais no Prelude.

Mikhail Glushenkov
fonte
31

O sistema de tipos de Haskell não é poderoso o suficiente para expressar os três operadores de exponenciação como um. O que você realmente deseja é algo assim:

class Exp a b where (^) :: a -> b -> a
instance (Num a,        Integral b) => Exp a b where ... -- current ^
instance (Fractional a, Integral b) => Exp a b where ... -- current ^^
instance (Floating a,   Floating b) => Exp a b where ... -- current **

Isso realmente não funciona mesmo se você ativar a extensão de classe de tipo multiparâmetro, porque a seleção de instância precisa ser mais inteligente do que o permitido atualmente por Haskell.

agosto
fonte
4
A afirmação sobre isso não ser implementável ainda é verdadeira? IIRC, haskell tem uma opção para o segundo parâmetro de uma classe de tipo multiparâmetro a ser determinado estritamente pelo primeiro parâmetro. Existe outro problema além deste que não pode ser resolvido?
RussellStewart
2
@singular Ainda é verdade. O primeiro argumento não determina o segundo, por exemplo, você deseja que o expoente seja ambos Inte Integer. Para poder ter essas três declarações de instância, a resolução da instância precisa usar backtracking, e nenhum compilador Haskell implementa isso.
agosto
7
O argumento do "sistema de tipos não é poderoso o suficiente" ainda se mantém em março de 2015?
Erik Kaplun
3
Você certamente não pode escrever da maneira que sugiro, mas pode haver uma maneira de codificá-lo.
agosto
2
@ErikAllik provavelmente sim para Haskell padrão, já que nenhum novo Relatório Haskell foi lançado desde 2010.
Martin Capodici
10

Não define dois operadores - define três! Do relatório:

Existem três operações de exponenciação de dois argumentos: ( ^) aumenta qualquer número para uma potência inteira não negativa, ( ^^) aumenta um número fracionário para qualquer potência inteira e ( **) leva dois argumentos de ponto flutuante. O valor de x^0ou x^^0é 1 para qualquer x, incluindo zero; 0**yé indefinido.

Isso significa que há três algoritmos diferentes, dois dos quais fornecem resultados exatos ( ^e ^^), enquanto **fornece resultados aproximados. Ao escolher qual operador usar, você escolhe qual algoritmo invocar.

Gabe
fonte
4

^requer que seu segundo argumento seja um Integral. Se não me engano, a implementação pode ser mais eficiente se você souber que está trabalhando com um expoente integral. Além disso, se você quiser algo como 2 ^ (1.234), mesmo que sua base seja uma integral, 2, seu resultado obviamente será fracionário. Você tem mais opções para ter um controle mais rígido sobre quais tipos entram e saem de sua função de exponenciação.

O sistema de tipos de Haskell não tem o mesmo objetivo de outros sistemas de tipos, como C's, Python's ou Lisp's. A digitação em pato é (quase) o oposto da mentalidade Haskell.

Dan Burton
fonte
4
Não concordo totalmente que a mentalidade do tipo Haskell seja o oposto da digitação do pato. As classes de tipo Haskell são muito parecidas com a digitação de pato. class Duck a where quack :: a -> Quackdefine o que esperamos de um pato e, em seguida, cada instância especifica algo que pode se comportar como um pato.
agosto
9
@augustss, vejo de onde você está vindo. Mas o lema informal por trás da digitação do pato é "se ele se parece com um pato, age como um pato e grasna como um pato, então é um pato". Em Haskell, não é um pato, a menos que seja declarado uma instância de Duck.
Dan Burton de
1
Isso é verdade, mas é o que eu esperava de Haskell. Você pode fazer o que quiser com um pato, mas tem que ser explícito sobre isso. Não queremos confundir algo que não pedimos para ser um pato.
agosto
Há uma diferença mais específica entre a maneira Haskell de fazer as coisas e a digitação lenta. Sim, você pode dar a classe Pato a qualquer tipo, mas não é um Pato. É capaz de grasnar, claro, mas ainda é, concretamente, qualquer tipo que seja. Você ainda não pode ter uma lista de patos. Uma função que aceita uma lista de patos e misturar e combinar vários tipos de classe de pato não funcionará. Nesse sentido, Haskell não permite que você diga apenas "Se grasna como um pato, então é um pato". Em Haskell, todos os seus patos devem ser Quackers do mesmo tipo. Isso é bem diferente da digitação de pato.
mmachenry 01 de
Você pode ter uma lista de patos mistos, mas você precisa da extensão da Quantificação Existencial.
Bolpat de