在标准ML列表中查找中间元素

Question

我试图在SML中找到列表的中间元素，而不使用任何形式为List.what的预先实现的功能。我可以使用一个函数，该函数接受2个相同的列表，然后递归调用自身，从一个列表中删除一个项目，从另一个列表中删除2个项目，直到第二个列表为空。然后，第一个列表的头将是原始列表的中间元素。我是SML的新手，无法找到从列表中删除第一项或从列表中删除前2项的方法。任何帮助都会很棒。

Answer 1

您可以自己编写受限库函数。这是一种解决方案：

fun length xs = let
  fun length_rec []        n = n
    | length_rec (_ :: xs) n = length_rec xs (n + 1)
  in length_rec xs 0
end

fun nth xs n = let
  fun nth_rec []        _ = NONE
    | nth_rec (x :: _)  0 = SOME x
    | nth_rec (_ :: xs) n = nth_rec xs (n - 1)
  in if n < 0 then NONE else nth_rec xs n
end

let middle xs = nth xs ((length xs - 1) div 2)

计算列表的长度需要另外遍历。这是一些示例输出：

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

- middle [1,2,3,4];
val it = SOME 2 : int option

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