ist es union und intersect Haskell-Prelude Umsetzung?

Gibt es in der Standard-Prelude-Funktionen, die die Verwirklichung der union und den Schnittpunkt der Sätze ?

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

Wenn Nein, kann jemand gesagt, wenn meine Umsetzung ist effizient, (machen Sie gute Verwendung von Faulheit und prelude-Funktion)

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]
InformationsquelleAutor Fopa Léon Constantin | 2011-05-13
  1. 14

    Gibt es union und intersect Funktionen, die auf Listen in den standard-Bibliotheken, die sich in Data.List aber nicht in der Prelude selbst.

    So weit wie Effizienz geht, werde ich "Nein" zu sagen zu allen oben genannten, beide Ihre und die standard-Bibliothek. Es gibt wirklich keine Möglichkeit, entweder immer sein kann, effiziente Operationen auf einer Liste mit nur einem Eq Einschränkung. Das heißt, Sie können immer noch die Umsetzung in Data.List informativ-finden Sie unter den obigen links, die ich habe, wies direkt auf die relevante Quelle.

    Bearbeiten -- Wie ein kurzer Nachtrag zum Wohle der Nachwelt, sicher sein, um zu sehen, Don ' s Antwort für das, was Sie eigentlich wollen für diesen Zweck zu benutzen, anstatt die engere Frage "haben diese Funktionen überhaupt existieren".

    InformationsquelleAutor C. A. McCann
  2. 14

    Der Basis-Bibliothek bietet eine Liste von Versionen, als camccann Punkte aus. Wenn Sie etwas wollen ein bisschen mehr effizient, betrachten Daten.Set, die bietet:

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

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

    mit Komplexität O(n+m).

    • Und beachten Sie, dass eine Ord Einschränkung und eine Daten-Struktur mit der versteckten Darstellung, wie Set ist so generisch, wie Sie wirklich erhalten können, während mit jeder Art von vernünftiger Effizienz. Fast alles andere ist entweder zu sehr ineffizient sein oder mehr auf das beschränkt, was es speichern kann.
    InformationsquelleAutor Don Stewart
  3. 0

    Werden Sie oft feststellen, Implementierungen, was Sie brauchen, indem Sie nach den Signaturen. Nur lassen Sie Ihre geben Sie die Signatur in Hoogle ( haskell.org/hoogle/... ).

    InformationsquelleAutor Ярослав Рахматуллин
Schreibe einen Kommentar