Как работает эта рекурсивная функция ocaml?

Question

Я довольно новичок в ocaml, и мне сложно с этим func

Я знаю, что он делает, но не КАК! При заданном списке он возвращает минимальное значение списка, а остальную часть списка - в виде пары.

sepmin [2; 1; 3; 4] == (1, [2; 3; 4])

вал sepmin: 'список ->' а * «список

# let rec sepmin = function 
[h] -> h, [] 
|h::t -> let h1, t1 = sepmin t in 
    min h h1, (max h h1)::t1;; 

Могли бы вы, ребята, помочь мне с рекурсивной частью tt

Answer 1

Во-первых, он рекурсивно применяется к хвосту списка. Скажем, он возвращает h1 и t1, которые являются минимумом хвоста и всех остальных элементов хвоста. Затем этот элемент, h, сравнивается с h1. Если он меньше h1, тогда возвращается пара (h, h1::t1); в противном случае возвращается пара (h1, h::t1). Так как функция вызывается рекурсивно, то, вероятно, одна из этих пар возвращается к предыдущей точке рекурсии (и ее первый элемент снова сравнивается с заголовком этой точки). Насколько я вижу, функция не заботится о первоначальном порядке элементов, т. Е. Для списка [1; 4; 2; 5; 6] он должен возвращать (1, [2; 4; 5; 6]), 2 и 4 переупорядочиваются в результате.

Answer 2

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

Тривиальный случай для этой функции представляет собой список одного элемента. В этом случае ответ очевиден.

Для получения более длинного списка вы можете использовать свою рекурсивную силу, чтобы получить правильный ответ для хвоста списка (который является более коротким списком, поэтому рекурсия будет работать по предположению). Как только вы узнаете ответ для хвоста списка, вы можете построить правильный ответ для полного списка: максимальный размер заголовка списка и ответ для хвоста - общий максимум. Вам нужно добавить меньшее из этих двух значений обратно в список.