Сравнить значения в списке

Question

Попытка осмыслить, как я сравнил бы несколько значений в списке, чтобы найти наибольшее значение, без использования изменяемых переменных.

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

max = 0;
for i in list
  if i > max
    max = i

Теперь, в функциональном программировании, если бы у меня был список, например [1;2;3] Как мне обойти проблему использования переменной max?

Answer 1

Простым ответом будет использование let maxValue = List.max theList.

Если вы хотите «свернуть свои собственные» без использования явно изменяемой переменной, очевидным способом является использование рекурсивной функции.Лично я бы определил это так:

let listMax theList = 
    let rec maxHelper remainingList maxSoFar = 
        match remainingList with
        | [] -> maxSoFar
        | h :: t -> 
                      if h > maxSoFar then
                          maxHelper t h
                      else
                          maxHelper t maxSoFar

    maxHelper theList (List.head theList)

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

В качестве альтернативы, этотакже может быть сделано довольно легко с помощью вызова List.fold.Например,

List.fold (fun (nextElem, maxSoFar) -> 
    if nextElem > maxSoFar then nextElem else maxSoFar) (List.head theList) theList

То же самое условие о том, что он не был проверен, применимо и к этому.

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

List.fold (fun (nextElem, maxSoFar) -> 
        if comparatorFunction nextElem maxSoFar then nextElem else maxSoFar)
        (List.head theList) theList