Сравнение элементов списка в Haskell

Question

Я просто изучаю Haskell и как бы застрял. Я хотел бы сравнить элементы списка и измерить разницу между ними и вернуть самый высокий. К несчастью, я не знаю, как подойти к этой проблеме. Для обычного, я просто перебираю список и сравниваю соседей, но, похоже, это не путь в Хаскелл. Я уже пробовал использовать map, но, как я уже сказал, я действительно не знаю, как вы можете решить эту проблему. Буду благодарен за любые советы!

С наилучшими пожеланиями

Edit: Моя идея состоит в том, чтобы первый пронестись все пары, как этот pairs a = zip a (tail a). Тогда я хотел бы получить все различия (возможно, с map?), А затем просто выбрал самый высокий. Я просто не могу обработать синтаксис Haskell.

Answer 1

Я не знаю, что вы имеете в виду под «измерить» несоответствие между элементами списка, но если вы хотите, чтобы вычислить «большой» элемент в списке, вы будете использовать встроенный в maximum функции:

maximum :: Ord a => [a] -> a 

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

Если вы хотите получить разницу между максимальным значением и минимальным значением, вы можете использовать аналогичную функцию minimum, а затем просто вычесть два. Конечно, может быть немного более быстрое решение, в котором вы только проходите список один раз, или вы можете отсортировать список, а затем взять первый и последний элементы, но для большинства случаев делать diff xs = maximum xs - minimum xs достаточно быстро и имеет смысл для кого-то другого.

---

Итак, вы хотите вычислить разницу между последовательными элементами, а не вычислять минимум и максимум каждого элемента. Вам не нужно индексировать напрямую, а использовать удобную функцию под названием zipWith. Он берет двоичную операцию и два списка, и «застегивает» их вместе, используя эту двоичную операцию. Так что-то вроде

zipWith (+) [1, 2, 3] [4, 5, 6] = [1 + 4, 2 + 5, 3 + 6] = [5, 7, 9] 

Это очень удобно, потому что, если один из списков заканчивается рано, он просто останавливается на достигнутом. Таким образом, вы могли бы сделать что-то вроде

diff xs = zipWith (-) xs ??? 

Но как мы компенсируем список на 1? Ну, простой (и безопасный) способ - использовать drop 1.Вы можете использовать tail, но это будет сгенерировано сообщение об ошибке и сбою программы, если xs является пустой список, но drop не

diff xs = zipWith (-) xs $ drop 1 xs 

Так пример будет

diff [1, 2, 3, 4] = zipWith (-) [1, 2, 3, 4] $ drop 1 [1, 2, 3, 4] 
        = zipWith (-) [1, 2, 3, 4] [2, 3, 4] 
        = [1 - 2, 2 - 3, 3 - 4] 
        = [-1, -1, -1] 

Эта функция возвращает положительные и отрицательные значения, и мы заинтересованы только в величине, поэтому мы можем использовать abs функцию:

maxDiff xs = ??? $ map abs $ diff xs 

И затем используя функцию, указанную выше:

maxDiff xs = maximum $ map abs $ diff xs 

И все готово! Если вы хотите быть фантазии, вы могли бы даже написать в точке, свободной нотации

maxDiff = maximum . map abs . diff 

Теперь, это будет на самом деле вызовет ошибку на пустой список, потому что maximum [] выдает ошибку, но я дам вам выяснить способ решения этого.

Answer 2

Как было упомянуто bheklilr, maximum - это быстрое и простое решение.

Если вам нужен какой-то фон, вот немного. То, что мы пытаемся сделать, это взять список значений и свести его к одному значению. Это известно как сгиб и возможно с (среди прочих) функцией foldl, которая имеет подпись foldl :: (a -> b -> a) -> a -> [b] -> a.

Раздел (a -> b -> a)foldl - это функция, которая принимает два значения и возвращает один из первых типов. В нашем случае, это должна быть наша функция сравнения:

myMax :: Ord a => a -> a -> a 
myMax x y | x > y  = x 
      | otherwise = y 

(обратите внимание, что Ord a требуется, чтобы мы могли сравнить наши ценности).

Таким образом, мы можем сказать,

-- This doesn't work! 

myMaximum :: Ord a => [a] -> a 
myMaximum list = foldl myMax _ list 

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

myMaximum :: Ord a => [a] -> a 
myMaximum list = foldl1 myMax list 

или в формате pointfree,

myMaximum :: Ord a => [a] -> a 
myMaximum = foldl1 myMax 

Если вы посмотрите на в Data.List фактической definition of maximum, вы увидите, что он использует тот же метод.

Answer 3

map отображает функцию над списком. Он преобразует каждый thing1 в список до thing2.

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

diffs :: (Num a) => [a] -> [a] 
diffs [] = [] 
diffs [x] = [] 
diffs (x1:x2:xs) = abs(x1-x2) : (diffs$x2:xs) 

mnd :: (Num a, Ord a) => [a] -> a 
mnd [] = 0 
mnd [x] = 0 
mnd xs = maximum$diffs xs 

Так diffs принимает каждый элемент один список за один раз и получает абсолютную разницу между ним и его соседом, то ставит, что в передней части списка создает у него идет вдоль (оператор : ставит индивид элемент в начале списка).

mnd - это всего лишь обертка вокруг maximum$diffs xs, которая останавливает исключения.