Finding middle element in a Standard ML list

Question

I am trying to find the middle element of a list in SML without using any pre implemented functions of the form List.whatever. I can use a function that takes 2 of the same lists, recursively calls itself, removing one item from one list and 2 items from the other until the second is empty. The head of the first list would then be the middle element of the original list. I am new to SML and cannot find a way to remove the first item from a list or the first 2 items from a list. Any help would be great.

danportin danportin · Accepted Answer · 2020-01-27T06:41:29

You can use pattern matching to determine the shape of the lists and name their components:

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

Here is some example output from the SML/NJ interpreter:

- 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

Finding middle element in a Standard ML list

1 Answers