2 % (c) The AQUA Project, Glasgow University, 1994-1996
5 \section[List]{Module @Lhar@}
9 delete, deleteBy, (\\), deleteFirsts, deleteFirstsBy,
10 elemBy, notElemBy, lookupBy, maximumBy, minimumBy,
11 nub, nubBy, partition, sums, products, transpose,
12 zip4, zip5, zip6, zip7,
13 zipWith4, zipWith5, zipWith6, zipWith7,
14 unzip4, unzip5, unzip6, unzip7,
15 genericLength, genericDrop, genericTake, genericSplitAt,
17 elemIndex, elemIndexBy, intersperse, group, groupBy,
19 inits, tails, subsequences, permutations,
26 %*********************************************************
28 \subsection{List functions}
30 %*********************************************************
33 -- delete x removes the first occurrence of x from its list argument.
34 delete :: (Eq a) => a -> [a] -> [a]
35 delete = deleteBy (==)
37 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
39 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
41 -- list difference (non-associative). In the result of xs \\ ys,
42 -- the first occurrence of each element of ys in turn (if any)
43 -- has been removed from xs. Thus, (xs ++ ys) \\ xs == ys.
44 (\\) :: (Eq a) => [a] -> [a] -> [a]
45 (\\) = foldl (flip delete)
47 -- Alternate name for \\
48 deleteFirsts :: (Eq a) => [a] -> [a] -> [a]
51 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
52 deleteFirstsBy eq = foldl (flip (deleteBy eq))
54 -- elem, notElem, lookup, maximumBy and minimumBy are in PreludeList
55 elemBy, notElemBy :: (a -> a -> Bool) -> a -> [a] -> Bool
56 elemBy eq _ [] = False
57 elemBy eq x (y:ys) = x `eq` y || elemBy eq x ys
59 notElemBy eq x xs = not (elemBy eq x xs)
61 lookupBy :: (a -> a -> Bool) -> a -> [(a, b)] -> Maybe b
62 lookupBy eq key [] = Nothing
63 lookupBy eq key ((x,y):xys)
65 | otherwise = lookupBy eq key xys
67 maximumBy :: (a -> a -> a) -> [a] -> a
68 maximumBy max [] = error "List.maximumBy: empty list"
69 maximumBy max xs = foldl1 max xs
71 minimumBy :: (a -> a -> a) -> [a] -> a
72 minimumBy min [] = error "List.minimumBy: empty list"
73 minimumBy min xs = foldl1 min xs
75 -- nub (meaning "essence") remove duplicate elements from its list argument.
76 nub :: (Eq a) => [a] -> [a]
79 nubBy :: (a -> a -> Bool) -> [a] -> [a]
81 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
83 -- partition takes a predicate and a list and returns a pair of lists:
84 -- those elements of the argument list that do and do not satisfy the
85 -- predicate, respectively; i,e,,
86 -- partition p xs == (filter p xs, filter (not . p) xs).
87 partition :: (a -> Bool) -> [a] -> ([a],[a])
88 partition p xs = foldr select ([],[]) xs
89 where select x (ts,fs) | p x = (x:ts,fs)
90 | otherwise = (ts, x:fs)
92 -- sums and products give a list of running sums or products from
93 -- a list of numbers. e.g., sums [1,2,3] == [0,1,3,6]
94 sums, products :: (Num a) => [a] -> [a]
96 products = scanl (*) 1
98 transpose :: [[a]] -> [[a]]
100 (\xs xss -> zipWith (:) xs (xss ++ repeat []))
103 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
104 zip4 = zipWith4 (,,,)
106 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
107 zip5 = zipWith5 (,,,,)
109 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
111 zip6 = zipWith6 (,,,,,)
113 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
114 [g] -> [(a,b,c,d,e,f,g)]
115 zip7 = zipWith7 (,,,,,,)
117 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
118 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
119 = z a b c d : zipWith4 z as bs cs ds
120 zipWith4 _ _ _ _ _ = []
122 zipWith5 :: (a->b->c->d->e->f) ->
123 [a]->[b]->[c]->[d]->[e]->[f]
124 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
125 = z a b c d e : zipWith5 z as bs cs ds es
126 zipWith5 _ _ _ _ _ _ = []
128 zipWith6 :: (a->b->c->d->e->f->g) ->
129 [a]->[b]->[c]->[d]->[e]->[f]->[g]
130 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
131 = z a b c d e f : zipWith6 z as bs cs ds es fs
132 zipWith6 _ _ _ _ _ _ _ = []
134 zipWith7 :: (a->b->c->d->e->f->g->h) ->
135 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
136 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
137 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
138 zipWith7 _ _ _ _ _ _ _ _ = []
140 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
141 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
142 (a:as,b:bs,c:cs,d:ds))
145 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
146 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
147 (a:as,b:bs,c:cs,d:ds,e:es))
150 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
151 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
152 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
155 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
156 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
157 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
158 ([],[],[],[],[],[],[])
160 genericLength :: (Num i) => [b] -> i
162 genericLength (_:l) = 1 + genericLength l
164 genericDrop :: (Integral i) => i -> [a] -> [a]
165 genericDrop 0 xs = xs
166 genericDrop _ [] = []
167 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
168 genericDrop _ _ = error "List.genericDrop: negative argument"
170 genericTake :: (Integral i) => i -> [a] -> [a]
172 genericTake _ [] = []
173 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
174 genericTake _ _ = error "List.genericTake: negative argument"
176 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
177 genericSplitAt 0 xs = ([],xs)
178 genericSplitAt _ [] = ([],[])
179 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
180 (xs',xs'') = genericSplitAt (n-1) xs
181 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
183 genericReplicate :: (Integral i) => i -> a -> [a]
184 genericReplicate n x = genericTake n (repeat x)
186 -- l !! (elemIndex l x) == x if x `elem` l
187 elemIndex :: Eq a => [a] -> a -> Int
188 elemIndex = elemIndexBy (==)
190 elemIndexBy :: (a -> a -> Bool) -> [a] -> a -> Int
191 elemIndexBy eq [] x = error "List.elemIndexBy: empty list"
192 elemIndexBy eq (x:xs) x' = if x `eq` x' then 0 else 1 + elemIndexBy eq xs x'
194 -- group splits its list argument into a list of lists of equal, adjacent
196 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
197 group :: (Eq a) => [a] -> [[a]]
200 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
202 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
203 where (ys,zs) = span (eq x) xs
206 mapAccumL :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
207 mapAccumL f s [] = (s, [])
208 mapAccumL f s (x:xs) = (s'',y:ys)
209 where (s', y ) = f s x
210 (s'',ys) = mapAccumL f s' xs
212 mapAccumR :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
213 mapAccumR f s [] = (s, [])
214 mapAccumR f s (x:xs) = (s'', y:ys)
215 where (s'',y ) = f s' x
216 (s', ys) = mapAccumR f s xs
218 -- intersperse sep inserts sep between the elements of its list argument.
219 -- e.g. intersperse ',' "abcde" == "a,b,c,d,e"
220 intersperse :: a -> [a] -> [a]
221 intersperse sep [] = []
222 intersperse sep [x] = [x]
223 intersperse sep (x:xs) = x : sep : intersperse sep xs
225 -- inits xs returns the list of initial segments of xs, shortest first.
226 -- e.g., inits "abc" == ["","a","ab","abc"]
227 inits :: [a] -> [[a]]
229 inits (x:xs) = [[]] ++ map (x:) (inits xs)
231 -- tails xs returns the list of all final segments of xs, longest first.
232 -- e.g., tails "abc" == ["abc", "bc", "c",""]
233 tails :: [a] -> [[a]]
235 tails xxs@(_:xs) = xxs : tails xs
237 -- subsequences xs returns the list of all subsequences of xs.
238 -- e.g., subsequences "abc" == ["","c","b","bc","a","ac","ab","abc"]
239 subsequences :: [a] -> [[a]]
240 subsequences [] = [[]]
241 subsequences (x:xs) = subsequences xs ++ map (x:) (subsequences xs)
243 -- permutations xs returns the list of all permutations of xs.
244 -- e.g., permutations "abc" == ["abc","bac","bca","acb","cab","cba"]
245 permutations :: [a] -> [[a]]
246 permutations [] = [[]]
247 permutations (x:xs) = [zs | ys <- permutations xs, zs <- interleave x ys ]
248 where interleave :: a -> [a] -> [[a]]
249 interleave x [] = [[x]]
250 interleave x (y:ys) = [x:y:ys] ++ map (y:) (interleave x ys)
252 union :: (Eq a) => [a] -> [a] -> [a]
253 union xs ys = xs ++ (ys \\ xs)
255 intersect :: (Eq a) => [a] -> [a] -> [a]
256 intersect xs ys = [x | x <- xs, x `elem` ys]