CODEWITHSUNDEEP
listsmlsmlnj
GeoGeorge
GeoGeorge

Reputation: 19

SML: Comparing every element of two lists without storing state info?

I have an SML assignment, and the general idea is that I shouldn't store state info, should not used built in library functions, etc and just solve in a functional way. Not sure how to do it:

The question requires comparing every element of two lists together:

input

list1: [(3,3,5),(5,4,7),(2,3,4)]; list2: [3, 6];

output

newList: [(3,3,5), (2,3,5)]

Essentially, when the second element in list1's tuple arg matches an item in list 2, then I should add the list1 item to the new output list.

The way I went about implementing it:

fun thing(x, y) = 
   if null x then []
   else if #2 (hd x) = (hd y) then hd x @ thing(tl x, y)
   else thing(tl x, y);

Obviously the issue with this is that I lose state information: how would you match every element in list1 against every element in list2?

Upvotes: 0

Views: 275

Answers (1)

sshine
sshine

Reputation: 16125

when the second element in list1's tuple arg matches an item in list 2,
then I should add the list1 item to the new output list.

fun thing(x, y) = 
  if null x then []
  else if #2 (hd x) = (hd y) then hd x @ thing(tl x, y)
  else thing(tl x, y);

Instead of if null x then ..., hd x and tl x, use pattern matching:

fun thing ([], _) = ...
  | thing ((x,y,z)::haystack, needles) = ...

To find out if y is a member of needles, build a membership function:

fun elem (p, []) = false
  | elem (p, q::qs) = p = q orelse elem (p, qs)

Check if elem (y, needles) to determine whether to include (x,y,z) as part of your result.

Apply thing recursively to haystack and needles.

Compose the recursive result using the :: (cons) operator rather than @ (append).

Here's how one could solve this exercise with library functions:

fun curry f x y = f (x, y)
fun thing (haystack, needles) =
    List.filter (fn (x,y,z) =>
      List.exists (curry op= y) needles) haystack

Upvotes: 1

Related Questions