¿hay una unión e intersección con la implementación de Haskell Prelude?

Question

¿Hay en las funciones Preludio estándar que implementan la unión y la intersección de conjuntos?

union  :: (Eq a) => [a] -> [a] -> [a] 
intersect :: (Eq a) => [a] -> [a] -> [a] 

Si no, puede que alguien puede decir si mi aplicación es eficiente, (hacer un buen uso de la pereza y la función preludio)

unionSet :: (Eq a) => [a] -> [a] -> [a] 
unionSet as bs = foldl (\xs y -> if elem y xs then xs else xs ++ [y]) as bs 

intersectSet :: (Eq a) => [a] -> [a] -> [a] 
intersectSet as bs = let ns = [ a | a <- as, elem a bs] in [ b | b <- bs, elem b ns] 

Answer 1

Hay union y intersect funciones sobre listas en las bibliotecas estándar, ubicado en Data.List pero no en el Prelude.

En lo que respecta a la eficiencia, voy a decir "no" a todo lo anterior, tanto el suyo como el de la biblioteca estándar. Realmente no hay forma de que alguna vez puedan ser operaciones eficientes en una lista con solo una restricción Eq. Dicho esto, aún puede encontrar la implementación en Data.List informativa: consulte los enlaces anteriores, que he señalado directamente a la fuente correspondiente.

Editar - Como breve adenda por el bien de la posteridad, asegúrese de ver la respuesta de Don para lo que desea utilizar para este propósito, en lugar de la cuestión más estrecha de "sí existen estas funciones en todas".

Answer 2

La biblioteca base proporciona versiones de lista, como lo señala Camccann. Si quieres algo un poco más eficiente, considere Data.Set, que dispone:

union :: Ord a => Set a -> Set a -> Set a 

intersection :: Ord a => Set a -> Set a -> Set a 

con la complejidad O (n + m).

Answer 3

A menudo encontrará implementaciones de lo que necesita al buscar las firmas. Simplemente suelte su firma de tipo en Hoogle ( haskell.org/hoogle/…).