Reversing a list in SML

Question

fun reverse ( [] ) = ( [] )
  | reverse (x::xs) = reverse (xs) :: [x]

why my this function of reversing a list is not working

Answer 1

Your function has type 'a list -> 'a list. :: has type 'a -> 'a list -> 'a list. Thus you can't pass the result of calling reverse as the first argument to ::.

You could use @ as suggested by JRose because that has type 'a list -> 'a list -> 'a list and will concatenate the two lists but that is inefficient compared to ::. @ is O(n). Using it makes reverse have O(n^2) runtime efficiency.

Instead, let's use a tail-recursive helper function to build up an accumulator list in reverse order using ::, then return that. Because :: is O(1), this has O(n) runtime efficiency which is much better than O(n^2).

fun reverse lst = 
  let
    fun aux [] acc = acc
      | aux (x::xs) acc = aux xs (x :: acc)
  in
    aux lst []
  end

Consider reversing [1, 2, 3]:

reverse [1, 2, 3]
aux [1, 2, 3] []
aux [2, 3] [1]
aux [3] [2, 1]
aux [] [3, 2, 1]
[3, 2, 1]

Further reading on the efficiency of @ and ::. The link talks about OCaml, but the core principles are the same in SML.