Standard ML: Recherche dans une liste de listes

Question

J'ai écrit cette fonction pour déterminer si un élément donné est stocké dans une liste de tuples, mais pour l'instant il ne recherche que la première liste. Comment irais-je chercher le reste des listes?

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 

Answer 1

Vous récursivité sur le reste des listes (vous avez besoin de trois cas):

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

Mais il est beaucoup plus facile sur l'oeil si vous écrivez d'abord une fonction qui effectue une recherche dans une liste, puis l'utiliser dans une autre fonction:

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) 

ce sont exactement les mêmes, sauf pour la partie avant orelse, afin que nous puissions abstraite avec une fonction sous-jacente:

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

et de l'utiliser:

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

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

Answer 2

Pour compléter la réponse de molbdnilo, voici comment je le mettre en œuvre. En utilisant la fonction de bibliothèque List.exists standard, il devient un un-liner:

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