Нахождение минимум двух значений
Ваше выражение if y < z then y else z имеет встроенное имя Int.min (y, z).
Работа с пустыми списками
Вы обрабатываете пустой список как minlist nil = nil, что означает, что «наименьшее целое из пустого списка int - это пустой список». Но пустой список не является int и поэтому не может быть элементом в списке int или возвращаемым значением для функции, которая в противном случае возвращает наименьшие целые числа.
Как также говорит molbdnilo, вы можете либо жить с предупреждением компиляции (и рискнуть, если во время выполнения возникнет исключение Match, если вы когда-нибудь передадите функции пустой список), либо вызвать конкретное исключение, такое как Empty, когда учитывая пустой список. Ни то, ни другое не хорошо, но последнее, по крайней мере, проясняет проблему.
Запись этого без foldr может выглядеть так:
fun minimum [] = raise Empty
| minimum [x] = x
| minimum (x::xs) = Int.min (x, minimum xs)
Преобразование рекурсивной функции в сгиб
Учитывая некоторую рекурсивную функцию foo, которая зависит от некоторой функции bar и некоторого значения по умолчанию acc:
fun foo [] = acc
| foo (x::xs) = bar (x, foo xs)
вы можете заметить сходство между minimum и foo:
acc равно x, минимальное значение bar - это Int.min.
Это попытка обобщить схему рекурсии minimum.
С учетом функции foldr:
fun foldr f e [] = e
| foldr f e (x::xs) = f (x, foldr f e xs);
вы можете заметить то же сходство:
f равно bar, но преобразовано в параметр e равно acc, но преобразовано в параметр
Единственная вещь из minimum, которая не соответствует этой общей схеме рекурсии, - это обработка пустого списка. Так что вы все равно должны сделать это отдельно от foldr:
fun minimum [] = ...
| minimum (x::xs) = foldr ...
Но остальное похоже.
Типы возврата с учетом ошибок
Третьим вариантом будет изменение сигнатуры типа функции на
val minimum : int list -> int option
, что, возможно, не разрешено вашим текущим упражнением.
Запись этого без foldr может выглядеть так:
fun minimum [] = NONE
| minimum [x] = SOME x
| minimum (x::xs) =
case minimum xs of
NONE => SOME x
| SOME y => SOME (Int.min (x, y))
или еще лучше:
fun minimum [] = NONE
| minimum [x] = SOME x
| minimum (x::xs) = Option.map (fn y => Int.min (x, y)) (minimum xs)
Преобразование этой функции для использования foldr - это тот же процесс, но с другим f.
Хвостовая рекурсия
Функция minimum без складывания (повторяется сверху):
fun minimum [] = raise Empty
| minimum [x] = x
| minimum (x::xs) = Int.min (x, minimum xs)
проблема в том, что он в основном использует стековую память .
Это можно проиллюстрировать, оценив функцию вручную:
minimum [1,2,3,4,5]
~> Int.min (1, minimum [2,3,4,5])
~> Int.min (1, Int.min (2, minimum [3,4,5]))
~> Int.min (1, Int.min (2, Int.min (3, minimum [4,5])))
~> Int.min (1, Int.min (2, Int.min (3, Int.min (4, minimum [5]))))
~> Int.min (1, Int.min (2, Int.min (3, Int.min (4, 5))))
~> Int.min (1, Int.min (2, Int.min (3, 4)))
~> Int.min (1, Int.min (2, 3))
~> Int.min (1, 2)
~> 1
Поскольку внешний Int.min не может быть вычислен до возвращения рекурсивного вызова, объем стековой памяти, используемой для вычисления функции, увеличивается пропорционально длине списка.
Вы можете избежать этого, используя набирающий аргумент:
fun minimum [] = raise Empty
| minimum (y::ys) =
let fun helper [] acc = acc
| helper (x::xs) acc = helper xs (Int.min (x, acc))
in helper ys y end
Оценка этой функции вручную:
minimum [1,2,3,4,5]
~> helper [2,3,4,5] 1
~> helper [3,4,5] (Int.min (2, 1))
~> helper [3,4,5] 1
~> helper [4,5] (Int.min (3, 1))
~> helper [4,5] 1
~> helper [5] (Int.min (4, 1))
~> helper [5] 1
~> helper [] (Int.min (5, 1))
~> helper [] 1
~> 1
Поскольку Int.min является коммутативным, вы также можете решить это упражнение с помощью foldl вместо foldr точно так же, как вы делали это выше, и у вас был бы хвост-рекурсивный вариант, использующий меньше пространство стека.