{-
(c) The University of Glasgow 2006
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998
\section[ListSetOps]{Set-like operations on lists}
-}{-# LANGUAGE CPP #-}moduleListSetOps(unionLists ,minusList ,deleteBys ,-- Association listsAssoc ,assoc ,assocMaybe ,assocUsing ,assocDefault ,assocDefaultUsing ,-- Duplicate handlinghasNoDups ,removeDups ,findDupsEq ,equivClasses ,-- IndexinggetNth )where#include "HsVersions.h"
importGhcPrelude importOutputable importUtil importData.ListimportqualifiedData.List.NonEmptyasNEimportData.List.NonEmpty(NonEmpty(..))importqualifiedData.SetasSgetNth::Outputable a =>[a ]->Int->a getNth xs n =ASSERT2(xs `lengthExceeds`n ,ppr n $$ pprxs)xs !!n deleteBys::(a ->a ->Bool)->[a ]->[a ]->[a ]-- (deleteBys eq xs ys) returns xs-ys, using the given equality function-- Just like 'Data.List.delete' but with an equality functiondeleteBys eq xs ys =foldl'(flip(deleteByeq ))xs ys {-
************************************************************************
* *
 Treating lists as sets
 Assumes the lists contain no duplicates, but are unordered
* *
************************************************************************
-}unionLists::(Outputable a ,Eqa )=>[a ]->[a ]->[a ]-- Assumes that the arguments contain no duplicatesunionLists xs ys =WARN(lengthExceedsxs 100|| lengthExceedsys 100,pprxs$$pprys)[x |x <-xs ,isn'tIn "unionLists"x ys ]++ys -- | Calculate the set difference of two lists. This is-- /O((m + n) log n)/, where we subtract a list of /n/ elements-- from a list of /m/ elements.---- Extremely short cases are handled specially:-- When /m/ or /n/ is 0, this takes /O(1)/ time. When /m/ is 1,-- it takes /O(n)/ time.minusList::Orda =>[a ]->[a ]->[a ]-- There's no point building a set to perform just one lookup, so we handle-- extremely short lists specially. It might actually be better to use-- an O(m*n) algorithm when m is a little longer (perhaps up to 4 or even 5).-- The tipping point will be somewhere in the area of where /m/ and /log n/-- become comparable, but we probably don't want to work too hard on this.minusList []_=[]minusListxs @[x ]ys |x `elem`ys =[]|otherwise=xs -- Using an empty set or a singleton would also be silly, so let's not.minusListxs []=xs minusListxs [y ]=filter(/=y )xs -- When each list has at least two elements, we build a set from the-- second argument, allowing us to filter the first argument fairly-- efficiently.minusListxs ys =filter(`S.notMember`yss )xs whereyss =S.fromListys {-
************************************************************************
* *
\subsection[Utils-assoc]{Association lists}
* *
************************************************************************
Inefficient finite maps based on association lists and equality.
-}-- A finite mapping based on equality and association liststypeAssoc a b =[(a ,b )]assoc::(Eqa )=>String->Assoc a b ->a ->b assocDefault::(Eqa )=>b ->Assoc a b ->a ->b assocUsing::(a ->a ->Bool)->String->Assoc a b ->a ->b assocMaybe::(Eqa )=>Assoc a b ->a ->Maybeb assocDefaultUsing::(a ->a ->Bool)->b ->Assoc a b ->a ->b assocDefaultUsing _deflt []_=deflt assocDefaultUsingeq deflt ((k ,v ):rest )key |k `eq `key =v |otherwise=assocDefaultUsing eq deflt rest key assoc crash_msg list key =assocDefaultUsing (==)(panic ("Failed in assoc: "++crash_msg ))list key assocDefault deflt list key =assocDefaultUsing (==)deflt list key assocUsing eq crash_msg list key =assocDefaultUsing eq (panic ("Failed in assoc: "++crash_msg ))list key assocMaybe alist key =lookup alist wherelookup []=Nothinglookup((tv ,ty ):rest )=ifkey ==tv thenJustty elselookup rest {-
************************************************************************
* *
\subsection[Utils-dups]{Duplicate-handling}
* *
************************************************************************
-}hasNoDups::(Eqa )=>[a ]->BoolhasNoDups xs =f []xs wheref _[]=Truefseen_so_far (x :xs )=ifx `is_elem `seen_so_far thenFalseelsef (x :seen_so_far )xs is_elem =isIn "hasNoDups"equivClasses::(a ->a ->Ordering)-- Comparison->[a ]->[NonEmptya ]equivClasses _[]=[]equivClasses_[stuff ]=[stuff :|[]]equivClassescmp items =NE.groupByeq (sortBycmp items )whereeq a b =casecmp a b of{EQ->True;_->False}removeDups::(a ->a ->Ordering)-- Comparison function->[a ]->([a ],-- List with no duplicates[NonEmptya ])-- List of duplicate groups. One representative-- from each group appears in the first resultremoveDups _[]=([],[])removeDups_[x ]=([x ],[])removeDupscmp xs =case(mapAccumRcollect_dups [](equivClasses cmp xs ))of{(dups ,xs' )->(xs' ,dups )}wherecollect_dups::[NonEmptya ]->NonEmptya ->([NonEmptya ],a )collect_dups dups_so_far (x :|[])=(dups_so_far ,x )collect_dupsdups_so_far dups @(x :|_)=(dups :dups_so_far ,x )findDupsEq::(a ->a ->Bool)->[a ]->[NonEmptya ]findDupsEq _[]=[]findDupsEqeq (x :xs )|nulleq_xs =findDupsEq eq xs |otherwise=(x :|eq_xs ):findDupsEq eq neq_xs where(eq_xs ,neq_xs )=partition(eq x )xs