I am trying to write a function in SML where there are two lists being passed into a function, and if both lists contain the same number (or multiple of the same number) those numbers are added to a new function.
fun shared([], []) = []
let
val list = []
in
shared(x::xs, y) = if x = y then x::list else shared(xs,y)
end
my thought process is that if x and y are equal then x will be added to the list which will contain all of the numbers that are shared in both of the original lists.
Edit: New code
fun append([], L) = L
| append(x::rest, L) = x::append(rest, L);
fun shared([], y) =
let
val list = []
in
| shared(y, x::xs) = if y = x then append(list, x)
else shared(y,xs)
end;
I do not think using the | here is legal in the in statement, but I don't know how to run through the list recursively without it.
if both lists contain the same number (or multiple of the same number) [...]
You assume that the input lists may contain duplicates, but you don't say if the result list should contain duplicates, and if so, what their multiplicity should be. Your code suggests a left-bias: That duplicates in xs should be repeated as many times as they occur in xs, regardless of how many times duplicates occur in ys; this seems unintended and undesired.
If you want duplicates to occur more than once, you should probably stick to the multiset intersection definition of multiplicity.
In the answer below I'll assume that you only want numbers to appear in the result once, even if they occur multiple times in either input list. Ideally in this case, though, you use a data type for sets that don't allow duplicates.
I'll start by finding the set intersection between two lists:
(* Remove duplicates in ''a list. O(n^2) *)
fun nub [] = []
| nub (x::xs) = x :: nub (List.filter (fn y => x <> y) xs)
(* Determine membership of x in ys. O(n) *)
fun isElem (x, ys) = List.exists (fn y => x = y) ys
(* Find intersection of xs, ys, remove duplicates. O(n^2) *)
fun intersect (xs, ys) = nub (List.filter (fn x => isElem (x, ys)) xs)
Here's an example of using this:
- intersect ([0,0,1,1,2,2,3,4], [1,1,2,3,3,5,6,6]);
> val it = [1, 2, 3] : int list
[...] those numbers are added to a new function
I'm not sure exactly what is meant here. You don't add numbers and functions together, and functions don't have mutable state to which things can be added. Perhaps you mean that if the intersection is non-empty, a function is applied to this non-empty result?
That could look like:
fun sum xs = foldl op+ 0 xs
fun printIntersectSum (xs, ys) =
case intersect (xs, ys) of
[] => print "Nothing to see; move along!\n"
| res => print ("Sum of intersection: " ^ Int.toString (sum res) ^ "\n")
And here's an example of using this:
- printIntersectSum ([0,0,1,1,2,2,3,4], [1,1,2,3,3,5,6,6]);
The sum of the intersection is: 6
> val it = () : unit