How to cast value in SML? Trying to take return type of S-Expression parser and convert to data structure

Question

I am using the S-Expression library included in SML/NJ. In my use case, my file containing the SExpressions will always be of type String List List List. The SExpParser.parse successfully parses my file. The problem is the return type of the parser is SExp.value List, where value is defined as

datatype value
      = SYMBOL of Atom.atom
      | BOOL of bool
      | INT of IntInf.int
      | FLOAT of real
      | STRING of string
      | QUOTE of value
      | LIST of value list

My function to convert the data into a graph is fun makeGraph (n:string list list list). Now, the problem is, naturally, the compiler yells at me because it cannot determine at compile time that the return type of the parser will actually be a string list list list. So, I have tried using pattern matching to determine the type, but I keep failing to get it to compile (something off of this idea).

Some things I have tried that have not worked:

fun convert (SExp.LIST ((SExp.LIST ((SExp.STRING s)::ss))::ls)) = ArrayGraph.makeGraph ls 
  | convert _ = raise Fail "convert"

fun convert values:SExp.value =
   case values of
      SExp.LIST ((SExp.LIST ((SExp.STRING s)::ss))::ls) => ArrayGraph.makeGraph ls 
    | _ => raise Fail "convert" 

fun convert values:SExp.value =
   case values of
      SExp.LIST(v) => map (fn x => convert x) v 
    | SExp.STRING(s) => s::nil
    | _ => raise Fail "convert"

I am really stumped on this problem and would appreciate any help. I also do not seem to find any examples of people using this library, so if you have any of those, I would appreciate a link. Thanks.

For reference, here is a link to the sml/nj s-expression code: https://github.com/smlnj/smlnj/blob/main/smlnj-lib/SExp/README

Answer 1

The first two can't work because ls is a SExp.value list, not a string list list.

The third can't work because s::nil is a string list, and if convert x is a string list list, then map (fn x => convert x) v is a string list list list.

Start at the bottom, with the strings, and work your way upwards over each nesting list.

Something like this should work:

fun to_string (SExp.STRING s) = s
  | to_string _ = raise Fail "to string"

fun to_string_list (SExp.LIST ss) = map to_string ss
  | to_string_list  _ = raise Fail "to string list"

fun to_string_list_list (SExp.LIST ss) = map to_string_list ss
  | to_string_list_list  _ = raise Fail "to string list list"

fun convert sexp = ArrayGraph.makeGraph (to_string_list_list sexp)

Answer 2

In SML, as in other typed functional languages, the types are your friend, not your enemy. If they seem like your enemy, you'll need to spend some more time learning the language and its normal usage. If you are familiar with a language A and you start to learn a language B, you will initially try to program in B as though it is A, and you will be frustrated.

It is good practice to document the type of any significant function or other value by "declaring" its type in a comment, as in

(* to_string : SExp.value -> string *)
fun to_string (SExp.STRING s) = s
  | to_string _ = raise Fail "to string"fun to_str

[Such predeclarations ought to be part of the language itself, and likely will be in the Successor ML language. ]

With more experience, you will be able to mentally type check your code as you write or read it, but such comments are very helpful. When I am trying to understand someone else's SML code, I start by adding such a "typing" comment at each declaration.

For further discussion, try standardml.zulipchat.com (you will need a Zulip account).