How do I append a record triple to a list in sml

Question

fun same_string(s1 : string, s2 : string) =
  s1 = s2
         
fun all_except_option(str, []) = NONE
  | all_except_option(str, x::xs) =
    case same_string(x, str) of
        true  => SOME xs
      | false => 
          let 
            fun build_list(x::xs, str) =
              case all_except_option(str, xs) of
                 NONE => NONE
               | SOME y => SOME(x::y)
          in
            build_list(x::xs, str)
          end

fun get_substitutions2(xss, str) =
  let 
    fun sub([], acc) = acc
      | sub(ys::yss, acc) =
        case all_except_option(str, ys) of
            NONE   => sub(yss, acc)
          | SOME y => sub(yss, y@acc)
  in
    sub(xss, [])
  end

fun similar_names(xss, []) = Empty
  | similar_names(xss, r : {first:string, middle:string, last:string}) = 
    let 
      fun helper (x::xs, acc) =
        case x of
            [] => acc
          | {first=a, middle=b, last=c} => helper(xs, {x, b, c} @ acc)
    in
      case get_substitutions2(xss,a) of
          NONE   => NONE
        | SOME y => helper(y, [])     
    end

- foo.sml:32.45 Error: syntax error: inserting  VAL
- foo.sml:33.5-33.7 Error: syntax error: replacing  IN with  EQUALOP
- foo.sml:38.5 Error: syntax error found at END

I am having trouble with the last function similar_names. I can't figure out how to either append or cons a record triple to a list. The function is supposed to take in a string list list and a record triple. It uses get_substitutions2 to go through the string list list with the first name of record as the string which uses all_except_option to find strings in string list list that match the first name. similar_names should output a record triple list as follows:

- val similar_names = fn : string list list * {first:string, last:string, middle:string}
-> {first:string, last:string, middle:string} list

Sample input (from comment by OP):

similar_names(
  [["Fred", "Fredrick"], 
   ["Elizabeth", "Betty"],
   ["Freddie", "Fred", "F"]], 
  {first="Fred", middle="W", last="Smith"}
)

With expected ooutput:

[{first="Fred", last="Smith", middle="W"}, 
 {first="Fredrick", last="Smith", middle="W"}, 
 {first="Freddie", last="Smith", middle="W"}, 
 {first="F", last="Smith", middle="W"}]

Answer 1

There are two ways in SML to add something to a list. We can concatenate two lists with @ or we can add an element to the beginning of a list with ::.

An aside on runtime complexity. The former has a runtime complexity linear to the length of the first list. The second always runs in constant time. As such, using @ within a recursively called function is usually discouraged as it yield a function that scales very poorly with the size of its data.

Your code shows generally an over-complication of thought. One of the keys to writing a computer program is breaking problems down and finding their base components, making those work, and then putting it back together.

If we look at what you need to accomplish, you have a list of lists which forms essentially an equivalence dictionary. You then have a list of name "triples" containing a first name, middle name and last name. We need to map each name to a list of names with equivalent first names.

First task is for a given name, to find all equivalents.

fun listEquivs(equivDict, name : string) =
  List.concat (List.filter (fn names => List.exists (fn n => n = name) names) equivDict);

We filter out the list of lists of equivalent names based on whether it contains the name we're looking for. We then "flatten" that list down into just a list rather than a lists of lists.

Checking this on your data for "Fred" gives us:

["Fred", "Fredrick", "Freddie", "Fred", "F"]

Almost. But we have two occurrences of "Fred", which you clearly saw and were trying to address. Instead of taking your approach, let's break the problem down. You basically just need a list of unique elements. This will actually solve the problem better because it will deal with repeats of any equivalent names.

As a first step we can get a sorted list of equivalent names.

List.sort String.compare (listEquivs(similarNames, "Fred"))

Returns:

["F", "Fred", "Fred", "Freddie", "Fredrick"]

Now, to find a list with only unique names. Fortunately finding unique values in a sorted list is straightforward.

fun unique([]) = []
  | unique([x]) = [x]
  | unique(a::(tl as b::_)) = 
    if a = b then unique(tl)
    else a::unique(tl);

Now:

unique(List.sort String.compare (listEquivs(similarNames, "Fred")));

Gives us:

["F", "Fred", "Freddie", "Fredrick"]

Having done this, we can now write a straightforward function:

fun equivalentNames(names, equivDict) = 
  List.concat (List.map 
    (fn {first=f, middle=m, last=l} =>
       let 
         val equivs = unique(List.sort String.compare (listEquivs(similarNames, f)))
       in
         List.map (fn e => {first=e, middle=m, last=l}) equivs
       end)
    names);

Now:

equivalentNames([{first="Fred", middle="W", last="Smith"}], similarNames);

Yields:

[{first = "F",        last = "Smith", middle = "W"}, 
 {first = "Fred",     last = "Smith", middle = "W"}, 
 {first = "Freddie",  last = "Smith", middle = "W"}, 
 {first = "Fredrick", last = "Smith", middle = "W"}]

Smaller functions used:

• List.filter
• List.exists
• List.concat
• List.map
• List.sort
• String.compare

Understand how these work, and you can use them to write programs with far greater ease.

As an example, a simple implementation of map.

fun map _ [] = []
  | map f (x::xs) = f x :: map f xs

Mapping any function onto an empty list gives us an empty list. This forms a base case for recursion. Otherwise we tack the result of applying the function f onto the front of the list formed by mapping f to the tail of the list.

E.g.

map (fn x => x + 1) [1, 2, 3, 4]
(1 + 1) :: map (fn x => x + 1) [2, 3, 4]
(1 + 1) :: (2 + 1) :: map (fn x => x + 1) [3, 4]
(1 + 1) :: (2 + 1) :: (3 + 1) :: map (fn x => x + 1) [4]
(1 + 1) :: (2 + 1) :: (3 + 1) :: (4 + 1) :: map (fn x => x + 1) []
(1 + 1) :: (2 + 1) :: (3 + 1) :: (4 + 1) :: []
[2, 3, 4, 5]