Функция Haskell - наибольшая

Question

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

Я новичок в Haskell, так что это моя попытка которой он не работает

largest :: [Int] -> Int 
largest [] = 0 
largest (head : tail) = if (head > tail) then head 
else (largest tail) 

Я понятия не имею, что это функция высшего порядка означает.

Некоторая помощь будет оценена по достоинству.

Answer 1

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

largest :: [a] -> (a -> a -> Ordering) -> a 
largest (x:xs) cmp = go x xs 
    where go largest []  = largest 
      go largest (x:xs) = case cmp largest x of 
      LT -> go x xs 
      _ -> go largest xs 

также, просто чтобы вы знаете, есть функция, чтобы сделать это для вас в Prelude под названием maximum. maximum [2,3,4,1] == 4

Answer 2

Чтобы исправить вашу попытку:

largest :: [Int] -> Int 
largest [] = 0 
largest (head : tail) = max head (largest tail) 

Обратите внимание, что это будет работать только для неотрицательных чисел (вы можете исправить это либо решив, что пустые списки не имеют максимум - как прелюдия'S maximum, или с помощью minBound для Int вместо 0, но это не сработало, например, для Integer).

Однако это все еще не использует функцию более высокого порядка. Подходящей функцией для такого рода проблем будет foldl (или лучше Data.List.foldl') или foldr, но я не хочу испортить веселье.

Answer 3

Чтобы завершить существующие ответы,

Первая проблема, которую нужно преодолеть, чтобы попытаться скомпилировать код, или, по крайней мере, понять сообщение об ошибке. Этот намек должен дать вам отличное руководство по проблеме, с которой вы столкнулись, и как ее изменить, чтобы иметь правильную версию (даже если вы не заполняете требования к функции высокого порядка, по крайней мере, у вас будет рабочий).

Для этого, давайте взглянем на тип подписи пункта шаблона, (руководитель: хвост),

Сначала для (:) функции, у нас есть,

(:) :: a -> [a] -> [a] 

Тогда мы получаем следующий вид для головы и хвоста, (которые являются аргументом из (:)),

• головка типа Int.
• хвост типа [Int].

Опять же, давайте посмотрим на тип подписи (>)

(>) :: Ord a => a -> a -> Bool 

Если опустить класс ограничения, чтобы сохранить его простым, мы имеем,

(>) :: a -> a -> Bool 

Или в ваш код есть,

.... 
if (head > tail) ... 
.... 

Что можно переписать, чтобы упростить римента, а

.... 
if ((>) head tail)) ... 
.... 

Используя все предыдущие замечания, вы должны быть в состоянии перестроить тип предоставляемой функции (>) и понять проблему.

Тогда вы можете исправить свой код и сделать это работает.
После того, как вы смогли взглянуть на high order function, а затем сделайте это правильно.

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

Сделать это работает,
сделать это правильно,
сделать, если быстро.

Answer 4

if (head > tail) 

Во-первых, вам не нужны скобки. Второе, и более серьезное, head является целым числом, но tail является списком целых чисел. Вы не можете сравнить эти две вещи.

largest (head : tail) = if (head > tail) then head 
else largest tail 

Это неправильный отступ. else должен иметь отступ по крайней мере до if. Вы можете поставить then и else на той же линии, или сделать что-то вроде

if head > tail 
    then head 
    else largest tail 

(опять же, вы на самом деле не нужны скобки - хотя они ничего не помешает.)

В качестве заключительной заметки существует предопределенная функция, называемая head, и одна называется tail, поэтому они не являются лучшим выбором имен переменных. Идиоматический выбор Haskell - x и xs (множественное число «x»). Вы увидите много кода, написанного следующим образом. Это также помогает напомнить вам, что x - вещь, а xs - это список вещей.