sml map and structure using recursion

747 views Asked by At

ML module with invisible and visible components to delete the first and last columns of a matrix. The matrix is stored as a list of lists as shown below:

|4|5|6|7| |8|9|10|11| |12|13|14|15| => is 4x4 array

The matrix above will be stored as val mat=[[4,5,6,7],[8,9,10,11],[12,13,14,15]];

I need use map function.

Sample Run:

  • val mat=[[4,5,6,7],[8,9,10,11],[12,13,14,15]];
  • S.reduce(mat);

val it = [[5,6],[9,10],[13,14]] : int list list


But I try in different way like:

fun reduce(x,y,z,t)=(y,z);
val mat = [(4,5,6,7),(8,9,10,11),(12,13,14,15)];
map reduce(mat);

Output :

- val reduce = fn : 'a * 'b * 'c * 'd -> 'b * 'c                                                                                                                                   
val mat = [(4,5,6,7),(8,9,10,11),(12,13,14,15)] : (int * int * int * int) list                                                                                                     
val it = [(5,6),(9,10),(13,14)] : (int * int) list

How to find correct answer?

1

There are 1 answers

0
molbdnilo On

This is easier if you delete at one end first and then the other.

Removing the first column is easy; it's simply applying List.tl to each row:

- val mat=[[4,5,6,7],[8,9,10,11],[12,13,14,15]];
val mat = [[4,5,6,7],[8,9,10,11],[12,13,14,15]] : int list list
- map tl mat;
val it = [[5,6,7],[9,10,11],[13,14,15]] : int list list

There's no library function that returns every element except the last, but it's reasonably straightforward to write:

fun except_last [] = []
  | except_last [x] = []
  | except_last (x::xs) = x :: (except_last xs); 

(The case for the empty list is questionable; you probably want to treat it as an error. It's good enough for illustration purposes though...)

- map except_last mat;
val it = [[4,5,6],[8,9,10],[12,13,14]] : int list list

And then you combine the two functions:

- fun reduce_row xs = except_last (tl xs);
val reduce_row = fn : 'a list -> 'a list
- fun reduce m = map reduce_row m;
val reduce = fn : 'a list list -> 'a list list
- reduce mat;
val it = [[5,6],[9,10],[13,14]] : int list list

An alternative implementation, which is quite inefficient but pleasantly symmetric, is to remove the last column by reversing the row, removing the first element, and then reversing it back:

- map (tl o rev o tl o rev) mat;
val it = [[5,6],[9,10],[13,14]] : int list list

(Nobody in their right mind would write this in actual software, but it looks nice.)