flatten a datatype list on SML getting problem

Question

I have a question on my homework, the question is

There is datatype is used:

datatype 'a llist = LList of 'a llist list| Elem of 'a;

A nested list consists of an element of a polymorphic type, or a list of nested lists. The following are some examples:

Elem(1);
LList [];
LList([Elem(1), LList([Elem(2), LList([Elem 1, Elem(3)]), Elem(4)])]);

Write a function flatten that takes a nested list as input and returns a flat list of all elements in the nested list. Note that the elements in the resulting list are in the same order as in the nested list.

- flatten;
val flatten = fn : 'a llist -> 'a list

Examples:

- flatten(Elem(3));
val it = [3] : int list
- flatten(LList([]));
val it = [] : ?.X1 list
- flatten(LList([Elem(1),LList([Elem(2),LList([]),Elem(3)]),Elem(4)]
));
val it = [1,2,3,4] : int list

But my code is

fun flatten Elem x = [x] | LList x = (List.concat (map (fn a => flatten(a)) x));

with problem

- fun flatten Elem x = [x] | LList x = (List.concat (map (fn a => flatten(a)) x));
stdIn:13.1-17.71 Error: clauses do not all have same function name

stdIn:13.1-17.71 Error: clauses do not all have same number of patterns

stdIn:17.4-17.8 Error: data constructor Elem used without argument in pattern

stdIn:13.1-17.71 Error: types of rules do not agree [tycon mismatch]
  earlier rule(s): 'Z * 'Y -> 'Y list
  this rule: 'X list -> 'W list
  in rule:
    x => List.concat ((map (fn a => flatten a)) x)

stdIn:13.1-17.71 Error: right-hand-side of clause does not agree with function result type [tycon mismatch]
  expression:  'Z -> 'Z list
  result type:  'Y list
  in declaration:
    flatten =
      (fn arg =>
            (fn arg =>
                  (case (arg,arg)
                  of (_,x) => x :: nil
                   | x => List.concat ((map <exp>) x))))

I don't know what is the problem on my code.

Answer 1

There are a few syntax issues in your code.

Otherwise the logic is fine.

Here is a corrected version:

fun flatten (Elem x) = [x]
  | flatten (LList x) = (List.concat (map (fn a => flatten(a)) x));

Answer 2

Since quoify provided a complete solution, here is a solution that uses explicit recursion rather than library functions, as well as a tidied up version of quoify's concat-map solution:

fun flatten (Elem x) = [x]
  | flatten (LList []) = []
  | flatten (LList (LL::LLs)) = flatten LL @ flatten (LList LLs)

Here LL is an 'a llist being the first sub-branch, and LLs is an 'a llist list, being the remaining sub-branches. The type name 'a llist may confuse a little, since it resembles a list when it is a tree. So you can think of LL as a tree, and LLs as a list of trees.

The basic approach is to pattern match on trees with one element, trees with zero sub-branches, and trees with one or more sub-branches. And turning this into a solution that uses list combinators like map and concat, you can identify the recursion scheme: Instead of splitting recursion into "empty" / "non-empty" patterns, give the entire task of recursion to map:

(* BROKEN *)
fun flatten (Elem x) = [x]
  | flatten (LList ts) = map flatten ts

The problem the compiler gives us is:

! Toplevel input:
!   | flatten (LList ts) = map flatten ts;
!                          ^^^^^^^^^^^^^^
! Type clash: expression of type
!   'a list list
! cannot have type
!   'a list
! because of circularity

So since flatten returns an 'a list, then map flatten must necessarily return an 'a list list, since it takes multiple trees and produces a flattened list for each. But an 'a list list is close enough to an 'a list that we can simply join the inner lists into one big list using List.concat:

fun flatten (Elem x) = [x]
  | flatten (LList ts) = List.concat (List.map flatten ts)

You can also create a helper function for this particular combination:

fun concatMap f = List.concat o List.map f
fun flatten (Elem x) = [x]
  | flatten (LList ts) = concatMap flatten ts