Хаскель расстраивает простую «среднюю» функцию

Question

Я играю с новичком на Haskell, и я хотел написать среднюю функцию. Казалось, самая простая вещь в мире, верно?

Неправильно.

Похоже, что система типов Haskell запрещает усреднению работать с общим числовым типом - я могу заставить его работать со списком интегралов или списком дробных чисел, но не обоими.

Я хочу:

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

Но я могу получить только:

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

или

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

а второй вроде работает. Пока я не попытаюсь передать переменную.

*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

По-видимому, Хаскелл действительно требователен к своим типам. В этом есть смысл. Но не тогда, когда они оба могут быть [Num]

Мне не хватает очевидного приложения RealFrac?

Есть ли способ привести Интегралы в дробные, которые не будут подавляться при получении дробного ввода?

Есть ли способ использовать Either и either для создания какой-либо полиморфной средней функции, которая будет работать с любым числовым массивом?

Запрещает ли система типов Haskell эту функцию когда-либо существовать?

Изучение Haskell похоже на изучение Calculus. Это действительно сложно и основано на множестве теорий, и иногда проблема настолько ошеломляюще сложна, что я даже не знаю достаточно, чтобы правильно сформулировать вопрос, поэтому любое понимание будет тепло принято.

(Кроме того, сноска: это основано на задаче домашней работы. Все согласны с тем, что на AverageFrac, приведенном выше, набираются полные баллы, но у меня есть подозрение, что есть способ заставить его работать как с интегральными, так и с дробными массивами)

Answer 1

Итак, в принципе вы ограничены типом (/):

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

Кстати, вы также хотите Data.List.genericLength

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

Так как насчет удаления fromIntegral для чего-то более общего:

import Data.List

average xs = realToFrac (sum xs) / genericLength xs

, который имеет только реальное ограничение (Int, Integer, Float, Double) ...

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

Так что это превратит любой Реал в любого Дробного.

И обратите внимание на все плакаты, попадающие в полиморфные числовые литералы в Хаскеле. 1 не целое число, это любое число.

Класс Real предоставляет только один метод: возможность превратить значение в классе Num в рациональное. Что именно то, что нам нужно здесь.

И, таким образом,

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

Донс очень хорошо ответил на вопрос, я подумал, что могу что-нибудь добавить.

При расчете среднего таким образом:

average xs = realToFrac (sum xs) / genericLength xs

То, что будет делать ваш код, - это дважды просмотреть список, один раз, чтобы вычислить сумму его элементов, и один раз, чтобы получить его длину. Насколько я знаю, GHC пока не может оптимизировать это и вычислить сумму и длину за один проход.

Даже новичку не больно думать об этом и о возможных решениях, например, средняя функция может быть написана с использованием сгиба, который вычисляет как сумму, так и длину; на 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

Функция выглядит не так элегантно, но производительность выше.

Дополнительная информация в блоге Dons:

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

Answer 3

Так как Донс проделал такую ​​хорошую работу, ответив на ваш вопрос, я буду работать над его вопросом ....

Например, в вашем вопросе, где вы впервые набираете среднее значение по заданному списку, получаете хороший ответ. Затем вы берете то, что похоже на тот же список , присваиваете его переменной, затем используете функцию переменная ..., которая затем взрывается.

Здесь вы столкнулись с настройкой в ​​компиляторе, называемой DMR: D прочитанная M ономорфная R эстракция. Когда вы передали список прямо в функцию, компилятор не сделал предположения о том, каким типом были числа, он просто определил, какие типы могут быть основаны на использовании, а затем выбрал один, когда больше не смог сузить поле. Это похоже на прямую противоположность печати по утке.

В любом случае, когда вы присваиваете список переменной, включается DMR. Так как вы поместили список в переменную, но без подсказок о том, как вы хотите его использовать, DMR заставил компилятор выбрать тип в данном случае он выбрал тот, который соответствовал форме и, казалось, подходил: Integer. Поскольку ваша функция не может использовать Integer в своей операции / (ей нужен тип в классе Fractional), это вызывает нарекания: в классе Fractional нет экземпляра Integer. В GHC есть параметры, которые можно настроить, чтобы он не приводил ваши значения в одну форму («мономорфная», получить?) До тех пор, пока это не понадобится, но делает сообщения об ошибках немного сложнее для выяснения.

Теперь, на другой ноте, у вас был ответ на ответ Дона, который привлек мое внимание:

Я был введен в заблуждение диаграммой на последней странице cs.ut.ee/~varmo/MFP2004/PreludeTour.pdf это показывает, что Floating НЕ наследует свойства от Real, и тогда я предположил, что у них не будет общих типов.

Haskell делает типы иначе, чем вы привыкли. Real и Floating являются классами типов, которые работают больше как интерфейсы, чем классы объектов. Они говорят вам, что вы можете сделать с типом, который находится в этом классе, но это не значит, что какой-то тип не может делать другие вещи, так же как наличие одного интерфейса означает, что класс (n OO-style) не может есть другие.

Изучение Haskell похоже на изучение Calculus

Я бы сказал, что изучение Haskell похоже на изучение шведского языка - есть много маленьких, простых вещей (букв, цифр), которые выглядят и работают одинаково, но есть также слова, которые выглядят так, как будто они означают одно, когда они на самом деле означает что-то еще. Но как только вы начнете бегло в этом разбираться, ваши обычные друзья будут удивлены тем, как вы можете извергать эти странные вещи, которые заставляют великолепных красавиц совершать удивительные трюки. Любопытно, что в Haskell с самого начала было много людей, которые также знают шведский язык. Может быть, эта метафора - больше, чем просто метафора ...

Answer 4

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

Answer 5

Да, система типов Хаскелла очень требовательна. Проблема здесь в типе fromIntegral:

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

fromIntegral будет только принимать Integral как, а не любой другой тип Num. (/), с другой стороны, принимает только дробные. Как вы можете заставить их работать вместе?

Хорошо, функция сумм - хорошее начало:

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

Sum берет список любого Num и возвращает Num.

Ваша следующая проблема - длина списка. Длина Int:

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

Вам нужно также преобразовать этот Int в Num. Это то, что делает из Интеграл.

Итак, теперь у вас есть функция, которая возвращает Num, и другая функция, которая возвращает Num. Существуют некоторые правила для раскрутки чисел , которые вы можете найти , но в основном на этом этапе вы можете идти:

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

Давайте попробуем:

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