Convert datatype to string (SML)

Question

I have a function that returns a (char * int) list list, like [[(#"D", 3)], [(#"F", 7)]], and now I'm wondering if it's posssible to convert this to a string, so that I can use I/O and read it to another file?

Answer 1

First of all, I assume you meant a value like [[(#"D", 3)], [(#"F", 7)]] (note the extra parens) since SML requires parentheses around tuple construction. OCaml uses a slightly different syntax, and allows just commas, like a, b, to construct tuples. I mention this because what follows is totally specific to Standard ML, and doesn't apply to OCaml, because I believe that in OCaml your best bet is an entirely different approach, which I don't know much about (macros, i.e. ocamlp4/5). So I assume that was just a typo and that you're interested in Standard ML.

Now, unfortunately there is no general toString function in Standard ML. Something like that would have to have some kind special support in the language and implementation, since it's not possible to write a function with the type 'a -> string. You basically have to write your own toString : t -> string for each type t.

As you can imagine, this gets tedious fast. I've spent a little time researching the options (for this and other boilerplate functions like compare : 't * 't -> order) and there is one very interesting technique outlined in the paper "Generics for the working ML'er" (http://dl.acm.org/citation.cfm?id=1292547) but it's pretty advanced and I could never actually get the code to compile (that said the paper is very interesting) The full generics library described in that paper is in the MLton lib repo (https://github.com/MLton/mltonlib/tree/master/com/ssh/generic/unstable). Maybe you'll have better luck?

Here's a slightly lighter weight approach that is less powerful but easier to understand, IMHO. I wrote this after reading that paper and struggling to get it to work. The idea is to write building blocks for toString functions (called show in this case) and compose them with other functions for your own types.

structure Show =
   struct
      (* Show.t is the type of toString functions *)
      type 'a t = 'a -> string

      val int: int t = Int.toString

      val char: char t = Char.toString

      val list: 'a t -> 'a list t =
       fn show => fn xs => "[" ^ concat (ExtList.interleave (map show xs) ",") ^ "]"

      val pair: 'a t * 'b t -> ('a * 'b) t =
       fn (showa,showb) => fn (a,b) => "(" ^ showa a ^ "," ^ showb b ^ ")"

      (* ... *)
   end

Since your type doesn't actually have any user defined datatypes, it's very easy to write the toString function using this structure:

local
   open Show
in
   val show : (char * int) list list -> string = list (list (pair (char, int)))
end

- show [[(#"D", 3)], [(#"F", 7)]] ;
val it = "[[(D,3)],[(F,7)]]" : string

What I like about this is that the composed functions read like the type turned inside out. It's a quite an elegant style, which I cannot take credit for as I took it from the generics paper linked above.

The rest of the code for Show (and a related module Eq for equality comparison) is here: https://github.com/spacemanaki/lib.sml