'SML finding the middle of a list

I am new to SML and am trying to create a function middle(lst) of type 'a list -> 'a which returns the middle element of a given list. I want to be able to do this without any pre-implemented functions of the form List.xyz...

I have found a way to do this, but I am using tl, which I believe is part of that pre-implemented list structure.

(* helper for middle *)
fun divvy(first,second) =
  if null(tl second) orelse null(tl(tl(second))) then hd first
  else divvy(tl first, tl(tl(second)));

(* get middle element in list *)
fun middle([a]) = a
  | middle(lst) = divvy(lst,lst);

Is there a way to do this without using pre-implemented functions?

listfunctionimplementationsmlsmlnj


Solution 1:[1]

Use pattern matching for the helper as well.

fun divvy (x::_, [_]) = x
  | divvy (x::_, [_,_]) = x
  | divvy (_::xs, _::_::ys) = divvy (xs, ys)

Solution 2:[2]

The same program written with pattern-match constructs...

val middle =
  fn []  => NONE
   | [x] => SOME x
   | lst => 
       let 
         fun pick _ [] = NONE
           | pick [] _ = NONE
           | pick (x::_) [e1] = SOME x
           | pick (x::_) [e1, e2] = SOME x
           | pick (_::ys) (p::q::rs) = pick ys rs
       in  
         pick lst lst
       end;

Run The Snippet Below to see the Results

evalCode();
<pre id="code">
val middle =
  fn [] => NONE
  | [x] => SOME x
  | lst => 
       let 
        fun pick _ [] = NONE
        | pick [] _ = NONE
        | pick (x::_) [e1] = SOME x
        | pick (x::_) [e1, e2] = SOME x
        | pick (_::ys) (p::q::rs) = pick ys rs
      in  
       pick lst lst
      end;
</pre>

<pre class="sml-input">
middle [];
</pre>

<pre class="sml-input">
middle [1];
</pre>

<pre class="sml-input">
middle [1, 2];
</pre>

<pre class="sml-input">
middle [1, 2, 3];
</pre>

<pre class="sml-input">
middle [1, 2, 3, 4];
</pre>

<pre class="sml-input">
middle [1, 2, 3, 4, 5];
</pre>
<script src="https://unpkg.com/@sosml/interpreter@^1.5.0/build/interpreter.min.js"></script>
<script>
  function evalCode() {
    try {
      let initialState = Interpreter.getFirstState();
      const code = document.getElementById('code');
      const inputs = document.querySelectorAll(".sml-input");

      let interpretationResult = Interpreter.interpret(code.innerText, initialState);
      console.log(interpretationResult.state.toString({
        stopId: initialState.id + 1
      }));

      inputs && inputs.length && inputs.forEach(input => {
        interpretationResult = Interpreter.interpret(input.innerText, interpretationResult.state);
        console.log(interpretationResult.state.toString());
      });
    } catch (error) {
      console.error(error.name, "\n", error.message);
    }
  }
</script>

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 molbdnilo
Solution 2 Chris

Related Questions