Map-Function for User-defined Generic Lists

Question

I'm trying to define a new polymorphic type generic_list with two value constructors: List and Seq, and add the function map_function (proc, items) that maps proc over all items.

Here is what I have so far:

datatype 'a seq = Nil | Cons of 'a * (unit -> 'a seq);
datatype 'a generic_list = List of 'a list | Seq of 'a seq;

How can I build the map_function when I have the following requirements:

• Signature: generic_map (proc, items)
• Purpose: Same as map defined in class, but items can be either a regular list or a lazy list.
• Type: fn: ('a -> 'b) * 'a generic_list -> 'b generic_list

• Examples:

  generic_map (fn x => x + 10, List [1, 2, 3]);
  val it = List [12,13,14]: int generic_list
  
  generic_map (fn x => x + 10, Seq (Cons (1, fn () => Cons(2, fn () => Cons (3, fn () => Nil)))));
  val it = Seq (Cons (11, fn)): int generic_list
  

Answer 1

I'm guessing by map defined in class you mean the map function for lists from the Standard ML Basis Library? Anyway, you have a data type with two constructors, one for Lists and one for Seqs, thus at the top-level, your function should just distinguish those two cases, i.e.,

fun generic_map (f, List xs) = List (...) (*map f over xs*)
  | generic_map (f, Seq s)   = Seq (...) (*map f over s*)

For the first case you get what you need almost for free by using List.map. The only remaining thing is to define a map-function for lazy lists. Its shape will be something like:

fun map_seq (f, Nil) = ... (*map f over the empty sequence*)
  | map_seq (f, Cons (x, s)) = ... (*map f over x and the remaining sequence s*)

Remark: Since it is part of your specification, you might not be allowed to change it -- and maybe it is more a matter of taste -- but I find your type for lazy lists a bit odd, because the tail of a lazy list, in your case, does not have the same type as a lazy list (i.e., the head of a list is not accessed lazily). In similar situations I would rather use

datatype 'a cell = Nil | Cons of 'a * (unit -> 'a cell);
type 'a seq = (unit -> 'a cell);

or

datatype 'a seq = Seq of unit -> ('a * 'a seq) option;

where the empty sequence is encoded by Seq (fn () => NONE).