Функция Haskell — самая большая

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

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

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

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

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


person codeeeeeNOT    schedule 08.03.2013    source источник


Ответы (4)


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

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

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

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

person Landei    schedule 08.03.2013

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

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

person cdk    schedule 08.03.2013

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

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

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

Сначала для функции (:) мы имеем,

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

Затем мы выводим следующий тип для head и tail (которые являются аргументами (:)),

  • head имеет тип Int.
  • хвост имеет тип [Int].

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

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

Если мы опустим класс ограничений, то для простоты получим:

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

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

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

Который можно переписать, опять же для упрощения, как

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

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

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

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

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

person zurgl    schedule 08.03.2013

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 — это список вещей.

person MathematicalOrchid    schedule 09.03.2013
comment
ideone.com/3veT8I показывает else слева от if, но все работает нормально. - person Will Ness; 16.03.2013