Новичок в SML / NJ. Как найти наибольшее значение в списке

Question

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

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

fun listCompare [] = 0
  | listCompare [x] = x
  | listCompare (x::xs) = listCompare(xs)

Это разобьет список до последнего элемента, но как мне начать сравнение и составление списка обратно?

Answer 1

Вы можете сравнить первые два элемента данного списка и сохранить больший элемент в списке и удалить другой. Если в списке только один элемент, то у вас есть максимум. В функциональном псевдокоде для a) это выглядит примерно так:

lmax []  = error "empty list"
lmax [x] = x
lmax (x::y::xs) = 
  if x > y then lmax (x::xs)
  else          lmax (y::xs)

Для б) вы могли бы сначала перевернуть список.

Answer 2

Это то, что foldl (или же foldr) функция в библиотеке списка SML предназначена для:

foldl : ((`a * `b) -> `b) -> `b -> `a list -> `b

Вы можете просто добавить анонимную функцию для сравнения текущего элемента с аккумулятором:

fun lMax l =
    foldl (fn (x,y) => if x > y then x else y) (nth l 0) l

nth функция просто берет int list : l и int : 0 вернуть первый элемент в списке. Поскольку списки в SML записываются рекурсивно как: h :: tизвлечение первого элемента является O(1) операция, и используя foldl Функция значительно повышает элегантность кода. Весь смысл наличия функционального языка состоит в том, чтобы определить абстракции для передачи анонимных функций в качестве функций высшего порядка и повторно использовать определения абстрактного типа с конкретными функциями.