Por que Haskell é incapaz de evitar avaliações repetidas sem a restrição de monomorfismo?

14

Acabei de terminar learnyouahaskell no outro dia e estava tentando entender a restrição de monomorfismo, conforme descrito no Wiki de Haskell . Acho que entendo como o MR pode impedir avaliações repetidas, mas não estou conseguindo entender por que essas avaliações repetidas não podem ser evitadas por meios muito mais diretos.

O exemplo específico que tenho em mente é o usado pelo wiki:

f xs = (len,len)
  where
    len = genericLength xs

Onde genericLength é do tipo Num a => [b] -> a.

Obviamente, genericLength xssó precisa ser computado uma vez para avaliar (len,len), pois é a mesma função com os mesmos argumentos. E não precisamos ver nenhuma invocação fpara saber disso.Então, por que Haskell não pode fazer essa otimização sem introduzir uma regra como a MR?

A discussão nessa página da wiki me diz que tem algo a ver com o fato de Numser uma classe de tipo e não de concreto, mas mesmo assim, não deveria ser óbvio no tempo de compilação que uma função pura retornaria o mesmo valor - - e, portanto, o mesmo tipo concreto de Num - quando dados os mesmos argumentos duas vezes?

Ixrec
fonte

Respostas:

11

É o mesmo nome da função, com os mesmos argumentos, mas tipos e implementações de retorno potencialmente diferentes, porque é polimórfico. Isso significa que, se for chamado em um contexto que espera um (Int, MyWeirdCustomNumType)tipo de retorno, ele deve ser avaliado duas vezes, porque a implementação de (+)in Inté completamente diferente da implementação de(+) in MyWeirdCustomNumType. Você precisa executar código fisicamente diferente em algum momento.

É por isso que importa que Num seja uma classe de tipo. Isso significa que você tem implementações diferentes para diferentes tipos. Isso também significa que, se festiver em uma biblioteca, ele não sabe em tempo de compilação sobre todas as combinações de tipos que talvez precise retornar.

Portanto, sim, você precisa ver as chamadas fpara saber quais tipos de retorno usar. Na maioria das vezes, você espera que eles sejam os mesmos, e é por isso que eles colocam a restrição de monomorfismo por padrão. Pode ser desativado nas raras ocasiões em que você não o faz. Na prática, os programadores não costumam deixar esse tipo de situação à inferência de tipos.

Karl Bielefeldt
fonte
Eu não tinha considerado a possibilidade de f [] :: (Int, Float). Agora faz todo o sentido. Obrigado.
Ixrec
1
It's the same function name, with the same arguments, but potentially different return types and implementations, because it's polymorphic.Eu acho que a melhor maneira de ver é que a instância da classe de tipo é efetivamente um argumento extra genericLengthe o compilador não está convencido de que é o mesmo argumento nas duas chamadas.
Doval
Pergunta lateral rápida. Se MonomorphismRestriction estiver desativado, mas mais tarde você fez algo como: a = uncurry (==) $ f [1, 2, 3]Seria capaz de otimizar o site de chamada para verificar apenas a duração de [1, 2, 3]uma vez? Se sim, então estou realmente confuso sobre o que a restrição de monomorfismo está realmente comprando para você, se não, por que não?
ponto