Reversing a list in SML-CodePudding

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

why my this function of reversing a list is not working

CodePudding user response：

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 ::.

Instead, let's use a tail-recursive helper function to build up an accumulator list in reverse order using ::, then return that.

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]

CodePudding user response：

You should use @ list combination rather than :: list construction.

fun reverse(nil) = nil
  | reverse(x::xs) = reverse(xs) @ [x];

reverse [1,2,3]

Output:

[3,2,1]