tipos de Haskell frustrando una simple función 'promedio'

Question

Estoy jugando con el principiante Haskell, y quería escribir una función promedio. Parecía la cosa más simple del mundo, ¿verdad?

Wrong.

Parece que el sistema de tipos de Haskell prohíbe que el promedio trabaje en un tipo numérico genérico: puedo hacer que funcione en una lista de integrales, o una lista de fraccionales, pero no en ambos.

Quiero:

average :: (Num a, Fractional b) => [a] -> b 
average xs = ... 

Pero sólo se puede obtener:

averageInt :: (Integral a, Fractional b) => [a] -> b 
averageInt xs = fromIntegral (sum xs)/fromIntegral (length xs) 

o

averageFrac :: (Fractional a) => [a] -> a 
averageFrac xs = sum xs/fromIntegral (length xs) 

y la segunda parece funcionar. Hasta que intente pasar una variable.

*Main> averageFrac [1,2,3] 
2.0 
*Main> let x = [1,2,3] 
*Main> :t x 
x :: [Integer] 
*Main> averageFrac x 

<interactive>:1:0: 
    No instance for (Fractional Integer) 
     arising from a use of `averageFrac ' at <interactive>:1:0-8 
    Possible fix: add an instance declaration for (Fractional Integer) 
    In the expression: average x 
    In the definition of `it': it = averageFrac x 

Aparentemente, Haskell es muy exigente con sus tipos. Eso tiene sentido. Pero no cuando ambos podían ser [Num]

¿Me falta una aplicación obvia de RealFrac?

¿Hay alguna forma de forzar integrales en fracciones que no se ahogan cuando recibe una entrada fraccional?

¿Hay alguna manera de usar Either y either para hacer algún tipo de función promedio polimórfica que funcione en cualquier tipo de matriz numérica?

¿El sistema de tipo Haskell prohíbe abiertamente que esta función exista?

Aprender Haskell es como aprender Cálculo. Es realmente complicado y se basa en montañas de teoría, y algunas veces el problema es tan complejo que ni siquiera sé lo suficiente como para formular la pregunta correctamente, por lo que cualquier idea será cálidamente aceptada.

(También, nota al pie: esto se basa en un problema de tarea. Todos están de acuerdo en que el promedio de Frac, arriba, obtiene puntos completos, pero sospecho que hay una manera de hacerlo funcionar en arreglos integrales y fraccionarios)

Answer 1

tan fundamentalmente, estás limitado por el tipo de (/):

(/) :: (Fractional a) => a -> a -> a 

por cierto, también quiere Data.List.genericLength

genericLength :: (Num i) => [b] -> i 

Así

¿qué hay de la eliminación de la fromIntegral por algo más general:

import Data.List 

average xs = realToFrac (sum xs)/genericLength xs 

que sólo tiene una limitación real (Int, Integer, Float, Double) ...

average :: (Real a, Fractional b) => [a] -> b 

Así que va a tomar ninguna real en cualquier fraccionario

Y tenga en cuenta que todos los pósters quedan atrapados por los literales polimórficos numéricos en Haskell. 1 no es un número entero, es cualquier número.

La clase Real proporciona solo un método: la capacidad de convertir un valor en la clase Num en un racional. Que es exactamente lo que necesitamos aquí.

Y así,

Prelude> average ([1 .. 10] :: [Double]) 
5.5 
Prelude> average ([1 .. 10] :: [Int]) 
5.5 
Prelude> average ([1 .. 10] :: [Float]) 
5.5 
Prelude> average ([1 .. 10] :: [Data.Word.Word8]) 
5.5 

Answer 2

Sí, sistema de tipos de Haskell es muy exigente. El problema aquí es el tipo de fromIntegral:

Prelude> :t fromIntegral 
fromIntegral :: (Integral a, Num b) => a -> b 

fromIntegral se única aceptar una integral como, sin ningún otro tipo de Num. (/), por otro lado solo acepta fracciones. ¿Cómo haces para que los dos trabajen juntos?

Bueno, la función suma es un buen comienzo:

Prelude> :t sum 
sum :: (Num a) => [a] -> a 

Suma toma una lista de cualquier numérico y devuelve un Num.

Su próximo problema es la longitud de la lista. La longitud es un Int:

Prelude> :t length 
length :: [a] -> Int 

Necesita convertir ese Int en un Num también. Eso es lo que hace Integral.

Ahora tiene una función que devuelve un Num y otra función que devuelve un Num. Hay algunas reglas para el tipo de promoción de los números you can look up, pero, básicamente, en este punto ya está bueno para ir:

Prelude> let average xs = (sum xs)/(fromIntegral (length xs)) 
Prelude> :t average 
average :: (Fractional a) => [a] -> a 

Vamos a darle un periodo de prueba:

Prelude> average [1,2,3,4,5] 
3.0 
Prelude> average [1.2,3.4,5.6,7.8,9.0] 
5.4 
Prelude> average [1.2,3,4.5,6,7.8,9] 
5.25 

Answer 3

La pregunta ha sido muy bien respondido por Dons, pensé que podría agregar algo.

Al calcular el promedio de esta manera:

average xs = realToFrac (sum xs)/genericLength xs

Lo que el código va a hacer es atravesar la lista dos veces, una para calcular la suma de sus elementos, y una vez para obtener su longitud. Hasta donde sé, GHC no puede optimizar esto y calcular tanto la suma como la longitud en una sola pasada.

No hace daño, incluso como un principiante para pensar sobre ello y sobre posibles soluciones, por ejemplo, la función promedio puede escribirse utilizando un doblez que computa tanto la suma como la longitud; en ghci:

:set -XBangPatterns 

import Data.List 

let avg l=let (t,n) = foldl' (\(!b,!c) a -> (a+b,c+1)) (0,0) l in realToFrac(t)/realToFrac(n) 

avg ([1,2,3,4]::[Int]) 
2.5 
avg ([1,2,3,4]::[Double]) 
2.5 

La función no se ve tan elegante, pero el rendimiento es mejor.

Más información sobre Dons blog:

http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-high-altitude-for-low-level-performance/

Answer 4

Desde Dons ha hecho un buen trabajo al responder a su pregunta, voy a trabajar en cuestionar su pregunta ....

Por ejemplo , en su pregunta, dónde ejecuta por primera vez un promedio en una lista determinada, obteniendo una buena respuesta. Luego, tome lo que parece exactamente la misma lista, asígnelo a una variable, luego use la función de la variable ... que luego explota.

Qué le han acabado en que aquí hay una puesta a punto en el compilador, llamado el DMR: la D readed M onomorphic R estriction. Cuando pasaste la lista directamente a la función, el compilador no hizo suposiciones sobre qué tipo eran los números, solo dedujo qué tipos podría estar basados ​​en el uso, y luego eligió uno una vez que ya no podía restringir el campo. Es algo así como el lado opuesto al tipado de patos, allí.

De todos modos, cuando asignó la lista a una variable, se activó el DMR. Dado que ha puesto la lista en una variable, pero sin dar pistas sobre cómo desea usarla, el DMR hizo que el compilador eligiera tipo, en este caso, eligió uno que coincidía con el formulario y parecía encajar: Integer. Como su función no podría usar un entero en su operación / (necesita un tipo en la clase Fractional), es una gran queja: no hay instancia de Integer en la clase Fractional. Hay opciones que puede configurar en GHC para que no fuerce sus valores en una sola forma ("monomórfico", ¿entiendes?) Hasta que lo necesite, pero hace que los mensajes de error sean un poco más difíciles de adivinar.

Ahora, en otra nota, que tenía una respuesta a la respuesta Dons' que me llamó la atención:

que era errónea por el cuadro de la última página de cs.ut.ee/~varmo/MFP2004 /PreludeTour.pdf que muestra que Flotante NO hereda propiedades de Real, y luego asumí que no compartirían ningún tipo en común.

Haskell hace tipos diferentes de lo que está acostumbrado. Real y Floating son clases de tipos, que funcionan más como interfaces que clases de objetos. Te dicen lo que puedes hacer con un tipo que está en esa clase, pero eso no significa que un tipo no pueda hacer otras cosas, como tampoco tener una interfaz significa que una clase (estilo OO) no puede tener otros.

aprendizaje Haskell es como aprender Cálculo

yo diría aprendiendo Haskell es como aprender sueco - hay un montón de cosas simples, pequeños (letras, números) que se ven y funcionan de la misma, pero también hay palabras que parecen que deberían significar una cosa, cuando realmente significan algo más. Pero una vez que lo domines con fluidez, tus amigos habituales se sorprenderán de cómo puedes sacar estas extrañas cosas que hacen que las preciosas bellezas hagan trucos increíbles. Curiosamente, hay muchas personas involucradas en Haskell desde el principio, que también saben sueco. Tal vez esa metáfora es más que una mera metáfora ...

Answer 5

:m Data.List 
let list = [1..10] 
let average = div (sum list) (genericLength list) 
average