How do I create a flatlist function in ML?

I am given an exercise that asks me to write a function flatlist that takes a list of lists and "flattens" it by returning the concatenation of all the lists in the original list.

For example:

flatlist([1,2], [6,7], [9]) = [1,2,6,7,9]

The code below is what I tried

fun flatlist([]) = []
  | flatlist(a::rest) = (a::rest);

I don't get an error message when writing the function, but I'm having issues when I try the function in the REPL and apply the function in the example.

Solution

The function you're asked to write is often called concat and happens to exist in the standard library under the name List.concat. Still, it's a good exercise to write such a recursive function. And your function does indeed type-check and compile, except there's a subtle flaw you haven't discovered yet.

Something about syntax

To begin with, I might format your first attempt a little differently with regards to whitespace and parentheses:

(* Before *)
fun flatlist([]) = []
  | flatlist(a::rest) = (a::rest);

(* After *)
fun flatlist [] = []
  | flatlist (xs :: xss) = xs :: xss

The points that come across here are:

Since the first element is a list itself, I like to give it a plural name, xs, and since the rest is a list of lists of things, I like to give it a double-plural name. But xs :: rest would also be fine. Just so we don't confuse the reader with x, which is an good name for a singular, arbitrary value.
The parenthesis around the [] pattern is not necessary because [] is a single combinator and so needs no disambiguation. However, the pattern xs :: xss does needs a parenthesis around it, because it contains an infix pattern constructor which takes multiple arguments. If we left it out, like so:
```
fun flatlist [] = []
  | flatlist xs :: xss = xs :: xss
```
we'd get the following warning (in Moscow ML):
```
! Toplevel input:
!   | flatlist xs :: xss = xs :: xss
!                 ^^
! Ill-placed infix in a fun clause
```
The parenthesis around the xs :: xss function body, on the other hand, doesn't need a parenthesis because the function body is syntactically reserved for a single expression, and xs :: xss. There's no disambiguation necessary here.
The ending ; is also not strictly necessary, unless you copy-paste this function into a REPL rather than put it in a file. So as long as your functions are so short you're just copy-pasting them into the REPL to try them out, having the ; is fine. When you start to build larger functions and you execute a whole file at once, you might as well leave them out.

The main take-away here, which is also related to the problem you're having with applying this function to a value, probably comes from your experience with programming languages for which function application looks like f(x) where the parenthesis means "what came just before is the function name, and what came in between is its argument(s).

SML functions are different: Function application, in its simplest form, looks like f x. Parentheses are needed to disambiguate, for example, f (x + 2) from (f x) + 2, but they're not needed to signify that this is function application. The space between the function name and the value takes care of that.

Analysing your initial solution

The first problem you're experiencing is passing a list of lists to the function. In your example, what you're actually doing is passing a 3-tuple, (x,y,z) with x, y and z being lists. The type for this value is int list * int list * int list and not int list list, which your function flatlist expects. This is because parentheses in SML, when there are commas in them, are used to express tuples rather than "arguments to a function".

Trying a list of list of integers, this instead gives:

- flatlist [[1,2], [6,7], [9]];
> val it = [[1, 2], [6, 7], [9]] : int list list

Tada! Wait.

Let's evaluate your first attempt at flatlist by hand by reducing a part of the expression at a time to see what's going on. Here I'm deriving the function call one line at a time with ⇒ meaning "reduces to":

  flatlist [[1,2], [6,7], [9]]          (* x = [1,2], xs = [[6,7], [9]] *)
⇒ [1,2] :: flatlist [[6,7], [9]]        (* x = [6,7], xs = [[9]] *)
⇒ [1,2] :: [6,7] :: flatlist [[9]]      (* x = [9], xs = [] *)
⇒ [1,2] :: [6,7] :: [9] :: flatlist []  (* base case *)
⇒ [1,2] :: [6,7] :: [9] :: []           (* just another way to write *)
⇒ [[1,2], [6,7], [9]]

So your current flatlist is a very complicated identity function for lists.

Hints for a correct solution

So you have basic recursion right, but the operation you need to perform at each recursive state is a little off. It isn't just xs :: xss as the function body, since that will produce the exact same output as input. You have to somehow join the elements of the list xs with the elements of the next list, recursively for all lists in xss.

Hint: The @ operator (pronounced "append").