8078d5603e081a22bf834696e189c649ea1705c2

1 {-

2 (c) The University of Glasgow 2006

3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998

5 \section[ListSetOps]{Set-like operations on lists}

6 -}

8 {-# LANGUAGE CPP #-}

13 -- Association lists

16 -- Duplicate handling

18 equivClasses,

20 -- Indexing

21 getNth

26 import GhcPrelude

28 import Outputable

29 import Util

38 xs !! n

41 -- (deleteBys eq xs ys) returns xs-ys, using the given equality function

42 -- Just like 'Data.List.delete' but with an equality function

45 {-

46 ************************************************************************

47 * *

48 Treating lists as sets

49 Assumes the lists contain no duplicates, but are unordered

50 * *

51 ************************************************************************

52 -}

55 -- | Assumes that the arguments contain no duplicates

57 -- We special case some reasonable common patterns.

58 unionLists xs [] = xs

66 unionLists xs ys

70 -- | Calculate the set difference of two lists. This is

71 -- /O((m + n) log n)/, where we subtract a list of /n/ elements

72 -- from a list of /m/ elements.

73 --

74 -- Extremely short cases are handled specially:

75 -- When /m/ or /n/ is 0, this takes /O(1)/ time. When /m/ is 1,

76 -- it takes /O(n)/ time.

78 -- There's no point building a set to perform just one lookup, so we handle

79 -- extremely short lists specially. It might actually be better to use

80 -- an O(m*n) algorithm when m is a little longer (perhaps up to 4 or even 5).

81 -- The tipping point will be somewhere in the area of where /m/ and /log n/

82 -- become comparable, but we probably don't want to work too hard on this.

87 -- Using an empty set or a singleton would also be silly, so let's not.

88 minusList xs [] = xs

90 -- When each list has at least two elements, we build a set from the

91 -- second argument, allowing us to filter the first argument fairly

92 -- efficiently.

94 where

97 {-

98 ************************************************************************

99 * *

100 \subsection[Utils-assoc]{Association lists}

101 * *

102 ************************************************************************

104 Inefficient finite maps based on association lists and equality.

105 -}

107 -- A finite mapping based on equality and association lists

118 | k `eq` key = v

121 assoc crash_msg list key = assocDefaultUsing (==) (panic ("Failed in assoc: " ++ crash_msg)) list key

123 assocUsing eq crash_msg list key = assocDefaultUsing eq (panic ("Failed in assoc: " ++ crash_msg)) list key

125 assocMaybe alist key

127 where

131 {-

132 ************************************************************************

133 * *

134 \subsection[Utils-dups]{Duplicate-handling}

135 * *

136 ************************************************************************

137 -}

142 where

154 equivClasses _ [] = []

157 where

164 -- from each group appears in the first result

166 removeDups _ [] = ([], [])

168 removeDups cmp xs

171 where

177 findDupsEq _ [] = []

182 -- | \( O(n) \). @'insertNoDup' x xs@ treats @xs@ as a set, inserting @x@ only

183 -- when an equal element couldn't be found in @xs@.

185 insertNoDup x set