Some sml codes but i don't know how that work

fun map f nil = nil
 | map f (hd::tl) = f(hd) :: map f tl;


fun everywhere e nil = [[e]]
  | everywhere e (y::ys) =
    (e::y::ys) :: (map (fn u => y::ys) (everywhere e ys));

I don't know how those sml codes work.

I know map function.

But about everywhere code, I don't know how much I think about that.

Please let me know

Thank you

Solution

First, I guess "everywhere" should be fixed to get the behavior expected from its name:

fun everywhere e nil = [[e]]
  | everywhere e (y::ys) =
    (e::y::ys) :: (map (fn u => y::u) (everywhere e ys));

This modified version provides a list of list. For example,

- everywhere 4 [1,2,3] ;
val it = [[4,1,2,3],[1,4,2,3],[1,2,4,3],[1,2,3,4]] : int list list

So, You may know that "everywhere e xs" enumerates all possible lists which are made by inserting item "e" into somewhere of the original list xs.

Then, how can you enumerate the insertion? It is divided into two cases:

insert at the top: [1,2,3] -> [4, 1,2,3]
insert between the first and the second or later: [1, 4 ,2,3], [1,2, 4 ,3],...

Case 1 is realized by just (e::y::ys).

Case 2 is further split into two steps:

A) get all possibilities of insertion of "e" to the sub list "ys" of the second and the following items: [4, 2, 3], [2, 4, 3], ...
B) add the first item "y" of the original list into EACH of the outcome of step A: 1 :: [4,2,3], 1::[2,4,3], ...

Step 2A can be done by calling "everywhere" itself with the sub list as an argument. Then, appending item "y" into each of (everywhere e ys), you have done Step 2B. For this (doing the same thing for items), you can use "map".