CODEWITHSUNDEEP
listfunctional-programmingsmlml
mattC
mattC

Reputation: 373

Standard ML: Searching through a list of lists

I wrote this function to determine whether a given element is stored in a list of list of tuples, however at the moment it only searches the first list. How would I go about searching the rest of the lists?

fun findItem (name : command, ((x,y)::firstlist)::tail : (command*command) list list) = 
    if x = name then true else findItem(name, firstlist::tail)
    | findItem(name, [[]]) = false

Upvotes: 2

Views: 335

Answers (2)

Andreas Rossberg
Andreas Rossberg

Reputation: 36088

To complement molbdnilo's answer, here is how I would implement it. Using the standard List.exists library function it becomes a one-liner:

fun findItem (x, ll) = List.exists (List.exists (fn (y,_) => x = y)) ll

Upvotes: 3

molbdnilo
molbdnilo

Reputation: 66371

You would recurse over the rest of the lists (you need three cases):

fun findItem (name, ((x,_)::firstlist)::tail) = x = name orelse findItem(name, firstlist::tail)
  | findItem (name, []::tail) = findItem (name, tail) 
  | findItem(name, []) = false

But it's much easier on the eye if you first write a function that searches through a list and then use that in another function:

fun findItemHelper (_, []) = false
  | findItemHelper (name, (n', _)::ns) = name = n' orelse findItemHelper (name, ns)

fun findItem (_, []) = false
  | findItem (name, n::ns) = findItemHelper (name, n) orelse findItem (name, ns)

These are exactly the same except for the part before orelse, so we can abstract that out with a predicate function:

fun find (_, []) = false
  | find (found, x::xs) = (found x) orelse find (found, xs)

and use it:

fun findItemHelper (name, ns) = find (fn (n, _) => name = n, ns)

fun findItem (name, nss) = find (fn ns => findItemHelper (name, ns), nss)

Upvotes: 4

Related Questions