gistfile1.sml

datatype Sexp = Satom of string | Scons of Sexp * Sexp | Snil

(* returns a string representation of an Sexp *)
fun showSexp s =
    let
        (* if fresh, Sexp is the head of a new list, not an inner cons cell *)
        fun showSexp' Snil _ = "nil"
          | showSexp' (Satom a) fresh =
            if not fresh
            then ". " ^ a (* dotted tail notation *)
            else a
          | showSexp' (Scons (h, t)) fresh =
            let val head = showSexp' h true
                val inner = if t = Snil then head else head ^ " " ^ showSexp' t false
            in if fresh
               then "(" ^ inner ^ ")"
               else inner
            end
    in
        showSexp' s true
    end

fun dotted Snil = false
  | dotted (Satom _) = false
  | dotted (Scons (_, (Satom _))) = true
  | dotted (Scons _) = false

exception DottedError

fun reverse s =
    let
        fun reverse' (Scons (h, t)) acc = reverse' t (Scons (h, acc))
          | reverse' Snil acc = acc
          | reverse' _ acc = raise DottedError
    in
        reverse' s Snil
    end