Does SML supports the nested list?

Question

the Nested List can exist in Scheme, but is it legal to use nested-list in SML? or we can only use simple list in SML?

and if legal,

1) how to check wether the two input list have the same list structure. algorithm the atoms in the list are not equal.

2) Whatever the deep of the input list, how to delete all the atoms in the nested-list that equals to the input value: a. should use the original list and not create a new list.

Answer 1

There's no problem in having nested lists in Standard ML. For an example:

val foo = [ [1, 2, 3], [4, 5], [6] ]

is an example of an int list list, i.e., a list of lists of integers.

As for your additional questions.

1

If by same structure you mean whether the sublists contain the same number of elements, i.e, you want

val bar = [ [34, 4, 6], [2, 78], [22] ]
val baz = [ [1], [4, 6, 2], [3, 6] ]

val cmp_foo_bar = structureEq (foo, bar) (* gives true, since the lengths of the sublists match up *)
val cmp_foo_baz = structureEq (foo, baz) (* gives false, since they don't *)

Then you can simply make a recursive function on the lists, that compares the length of each sublist in turn.

Note, if the lists are nested more than once, you'll need a function for each level. (i.e., one for 'a list lists, one for 'a list list lists, etc.

2

You cannot make a function that "however deep the input list" does something to the elements in the list. The type system will not let you do this. This is similar to how you cannot make the following list:

val illegal_list = [ [1, 2], [ [1, 4], [2, 3] ] ]

This is due to a list only being allowed to contain one type of elements, so if you have an 'a list list, each element in the list must be an 'a list. You cannot have 'as directly.

You'll have to settle on how nested the lists are, and make a function specific to that depth.

Answer 2

There is no problem with nesting lists in SML, e.g. [[1, 2], [3, 4]] works just fine.

However, I suspect you actually mean something more general, namely the ability to nest "lists" in heterogeneous ways: [[1, [3]], 2]. This is not legal as such in SML. However, this is because such a thing is not really a list, it is a tree.

You can define trees easily as well, but you need a more general type definition than the one for list:

datatype 'a tree = L of 'a | T of 'a tree list

Then T[T[L 1, T[L 3]], L 2] is a representation of the "list" above. A function for computing the depth (or height) of such a tree looks like

fun depth (L _)  = 0
  | depth (T ts) = 1 + max (List.map depth ts)

where max needs to be defined in the obvious manner.