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 -}

56 -- Assumes that the arguments contain no duplicates

57 unionLists xs ys

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

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

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

64 --

65 -- Extremely short cases are handled specially:

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

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

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

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

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

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

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

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

79 minusList xs [] = xs

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

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

83 -- efficiently.

85 where

88 {-

89 ************************************************************************

90 * *

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

92 * *

93 ************************************************************************

95 Inefficient finite maps based on association lists and equality.

96 -}

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

109 | k `eq` key = v

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

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

116 assocMaybe alist key

118 where

122 {-

123 ************************************************************************

124 * *

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

126 * *

127 ************************************************************************

128 -}

133 where

145 equivClasses _ [] = []

148 where

155 -- from each group appears in the first result

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

159 removeDups cmp xs

162 where

168 findDupsEq _ [] = []