Поиск среднего элемента в списке стандартных ML

Question

Я пытаюсь найти средний элемент списка в SML без использования каких-либо предварительно реализованных функций в виде списка. Я могу использовать функцию, которая берет 2 одинаковых списка, рекурсивно вызывает себя, удаляя один элемент из одного списка и 2 элемента из другого, пока второй не станет пустым. Глава первого списка будет тогда средним элементом исходного списка. Я новичок в SML и не могу найти способ удалить первый элемент из списка или первые 2 элемента из списка. Любая помощь будет великолепна.

Answer 1

Вы можете использовать сопоставление с образцом , чтобы определить форму списков и назвать их компоненты:

fun middle xs = let
  fun middle_rec (_ :: [])      (x :: _)  = SOME x
    | middle_rec (_ :: _ :: []) (x :: _)  = SOME x
    | middle_rec (_ :: _ :: xs) (_ :: ys) = middle_rec xs ys
    | middle_rec _              _         = NONE
  in middle_rec xs xs
end

Вот некоторые примеры вывода из интерпретатора SML / NJ:

- middle ([] : int list);
val it = NONE : int list

- middle [1];
val it = SOME 1 : int list

- middle [1,2];
val it = SOME 1 : int list

- middle [1,2,3,4,5,6,7];
val it = SOME 4 : int list

- middle [1,2,3,4,5,6,7,8];
val it = SOME 4 : int list