Хорошо, это домашнее задание, но домашнее задание может быть очень сложным, когда вы должны делать это на Хаскелле.Я постараюсь шаг за шагом объяснить, как вы можете это сделать.
Полезно знать
Во-первых, Haskell функционален.Вы можете найти различные определения «функционала», но в основном вы можете думать о нем как о свойстве языка: все постоянно (без побочных эффектов).
Во-вторых, вы можете запустить REPL , набрав ghci в терминале:
jferard@jferard-Z170XP-SLI:~$ ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/ :? for help
Prelude> :set +m -- enable parsing of multiline commands
Prelude> -- type the expression you want to evaluate here
Рекурсия
Как рассчитать сумму элементов списка?На императивном языке вы будете делать что-то подобное (например, Python):
s = 0
for every x in xs:
s <- s + x
Но s не является константой.Он обновляется на каждой итерации, пока мы не получим сумму.Можем ли мы переформулировать алгоритм, чтобы избежать этой мутации?К счастью да.Вот ключевая идея:
sum [x] = x
sum [x1, ..., xn] = x1 + sum [x2, ..., xn]
С небольшим воображением, вы можете сказать, что sum [] = 0.Таким образом, мы можем написать это на Хаскеле:
sum [] = 0
sum (x:xs) = x + sum xs
-- sum [1, 2, 3, 5] == 11
(x:xs) означает: x (head), за которым следует список xs (tail).Если вы поняли это, вы знаете, как мы можем избежать побочных эффектов во многих ситуациях: просто вызовите другую функцию, чтобы выполнить оставшуюся часть работы.(Примечание: если вы знаете о стеке, вы можете представить, что происходит под капотом.)
Теперь, как вы вычисляете длину списка?На Python-подобном языке вы бы сделали что-то вроде (забудьте len(..)):
l = 0
for every x in xs:
l <- l + 1
Опять же, с рекурсивным определением, у вас есть:
length [] = 0
length (x:xs) = 1 + length xs
-- len [1, 2, 3, 5] == 4
Folds
Вычисление суммы и длины настолько распространено, что они являются встроенными функциями в Haskell.Но есть кое-что более важное: если вы внимательно изучите две функции, вы заметите следующую схему:
f [] = <initial value>
f (x:xs) = g(f xs, x)
Для sum начальное значение равно 0 и g(f xs, x) = x + f xs.Для length начальное значение составляет 0 и g(f xs, x) = 1 + f xs.Этот шаблон настолько распространен, что в Haskell есть встроенная функция (на самом деле несколько встроенных функций): foldl.foldl принимает функцию, начальное значение и список и возвращает функцию, неоднократно примененную к предыдущему результату и текущему элементу, пока список не будет использован.Вы можете думать о функции как о теле цикла:
sum xs = foldl (+) 0 xs
(Примечание по поводу каррификации: 1. Возможно, вы когда-нибудь узнаете, что функции Haskell всегда принимают один аргумент, но здесь дело не в этом2. Вы можете удалить xs с обеих сторон: sum = foldl (+) 0)
Prelude> foldl (+) 0 [1,2,3,5]
11 -- (((0+1)+2)+3)+5
С помощью scanl вы можете каким-то образом отладить foldl:
Prelude> scanl (+) 0 [1,2,3,5]
[0,1,3,6,11]
length более сложная задача, поскольку у вас нет встроенной функции g(f xs, x) = 1 + f xs.Вы можете использовать лямбда-функцию : \acc x -> 1 + acc, где acc - текущее значение:
length xs = foldl (\acc x -> 1 + acc) 0 xs
Ваш вопрос
Среднее
Давайтепопробуйте написать average со встроенными функциями sum и length:
Prelude> average xs = sum xs / length xs
<interactive>:1:14: error:
• Could not deduce (Fractional Int) arising from a use of ‘/’
...
Что это значит?Я не буду вдаваться в подробности, но вы должны знать, что Хаскелл очень строг с числами.Вы не можете разделить два целых числа и ожидать результата с плавающей запятой без небольшой работы.
Prelude> :t (/)
(/) :: Fractional a => a -> a -> a
Это означает, что / займет Fractional с.Таким образом, работа заключается в следующем: приведение целых чисел к Fractional с.
average xs = fromIntegral (sum xs) / fromIntegral (length xs)
-- average [1, 2, 3, 5] == 2.75
Количество значений, превышающих среднее
Теперь число значений, превышающее среднее.В языке, подобном Python, вы напишите:
c = 0
for every x in xs:
if x > avg:
c <- c + 1
Давайте попробуем рекурсивный метод:
gtAvg [] = 0
gtAvg (x:xs) = (if x>avg then 1) + sum xs -- WRONG
Вы видите, что чего-то не хватает.В императивной версии, если x <= avg, мы просто ничего не делаем (и, следовательно, не обновляем значение).Здесь мы должны что-то вернуть:
gtAvg [] = 0
gtAvg (x:xs) = (if x>avg then 1 else 0) + gtAvg xs
Но откуда берется значение avg?Нам нужно предварительно вычислить это.Давайте определим функцию, которая принимает avg в качестве аргумента:
gtAvg' [] _ = 0
gtAvg' (x:xs) avg = (if fromIntegral x>avg then 1 else 0) + gtAvg' xs avg
-- gtAvg' [1, 2, 3, 5] (average [1, 2, 3, 5]) == 2
А затем:
gtAvg xs = gtAvg' xs (average xs)
-- gtAvg [1, 2, 3, 5] == 2
Очевидно, это проще с foldl:
gtAvg xs = foldl (\acc x -> if fromIntegral x>average xs then acc+1 else acc) 0 xs
Подробнее (карта, фильтр и понимание списка)
Когда мы разберемся с основами Haskell, вам может понадобиться еще три конструкции.
Filter
First, filter:
Prelude> filter (>2.75) [1, 2, 3, 5]
[3.0,5.0]
Если вы возьмете длину этого списка, вы получите число элементов больше среднего:
gtAvg xs = length $ filter (\x -> fromIntegral x >average xs) xs
(Или с набором функций: length $ filter ((> average xs).fromIntegral) xs) Не беспокойтесьзнак $: это означает, что правая часть выражения (filter...) представляет собой один блок, как если бы это было в скобках.
Карта
Во-вторых, применяется mapфункция для каждого элемента списка и возвращает список отображенных элементов.Например, если вы хотите использовать квадраты элементов списка:
Prelude> sum $ map (**2) [1, 2, 3, 5]
39.0
Вы можете использовать его так:
gtAvg xs = length $ filter (>average xs) $ map fromIntegral xs
Он преобразует элементы в Fractional, затемприменяет фильтр.
Понимание списка
В-третьих, вы можете иметь filter и map с пониманием списка:
gtAvg xs = length [x | x<-xs, fromIntegral x>average xs]
Я оставил многовещи в стороне и, вероятно, приблизились, но теперь у вас должны быть базовые знания, чтобы ответить на ваш вопрос.