2 % (c) The AQUA Project, Glasgow University, 1994-1996
5 \section[List]{Module @Lhar@}
9 elemIndex, elemIndices,
10 find, findIndex, findIndices,
11 nub, nubBy, delete, deleteBy, (\\), deleteFirstsBy,
13 intersperse, transpose, partition, group, groupBy,
14 inits, tails, isPrefixOf, isSuffixOf,
16 sort, sortBy, insertBy, maximumBy, minimumBy,
17 genericLength, genericTake, genericDrop,
18 genericSplitAt, genericIndex, genericReplicate,
19 zip4, zip5, zip6, zip7,
20 zipWith4, zipWith5, zipWith6, zipWith7,
21 unzip4, unzip5, unzip6, unzip7
26 import Maybe (listToMaybe)
31 %*********************************************************
33 \subsection{List functions}
35 %*********************************************************
38 elemIndex :: Eq a => a -> [a] -> Maybe Int
39 elemIndex x = findIndex (x==)
41 elemIndices :: Eq a => a -> [a] -> [Int]
42 elemIndices x = findIndices (x==)
44 find :: (a -> Bool) -> [a] -> Maybe a
45 find p = listToMaybe . filter p
47 findIndex :: (a -> Bool) -> [a] -> Maybe Int
48 findIndex p = listToMaybe . findIndices p
50 findIndices :: (a -> Bool) -> [a] -> [Int]
51 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
53 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
54 isPrefixOf [] _ = True
55 isPrefixOf _ [] = False
56 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
58 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
59 isSuffixOf x y = reverse x `isPrefixOf` reverse y
61 -- nub (meaning "essence") remove duplicate elements from its list argument.
62 nub :: (Eq a) => [a] -> [a]
63 #ifdef USE_REPORT_PRELUDE
70 nub' (x:xs) l = if x `elem` l then nub' xs l else x : nub' xs (x:l)
73 nubBy :: (a -> a -> Bool) -> [a] -> [a]
74 #ifdef USE_REPORT_PRELUDE
76 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
78 nubBy eq l = nubBy' l []
81 nubBy' (x:xs) l = if elemBy eq x l then nubBy' xs l else x : nubBy' xs (x:l)
84 -- delete x removes the first occurrence of x from its list argument.
85 delete :: (Eq a) => a -> [a] -> [a]
86 delete = deleteBy (==)
88 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
90 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
92 -- list difference (non-associative). In the result of xs \\ ys,
93 -- the first occurrence of each element of ys in turn (if any)
94 -- has been removed from xs. Thus, (xs ++ ys) \\ xs == ys.
95 (\\) :: (Eq a) => [a] -> [a] -> [a]
96 (\\) = foldl (flip delete)
98 -- List union, remove the elements of first list from second.
99 union :: (Eq a) => [a] -> [a] -> [a]
102 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
103 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) ys xs
105 intersect :: (Eq a) => [a] -> [a] -> [a]
106 intersect = intersectBy (==)
108 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
109 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
111 -- intersperse sep inserts sep between the elements of its list argument.
112 -- e.g. intersperse ',' "abcde" == "a,b,c,d,e"
113 intersperse :: a -> [a] -> [a]
114 intersperse sep [] = []
115 intersperse sep [x] = [x]
116 intersperse sep (x:xs) = x : sep : intersperse sep xs
118 transpose :: [[a]] -> [[a]]
120 (\xs xss -> zipWith (:) xs (xss ++ repeat []))
124 -- partition takes a predicate and a list and returns a pair of lists:
125 -- those elements of the argument list that do and do not satisfy the
126 -- predicate, respectively; i,e,,
127 -- partition p xs == (filter p xs, filter (not . p) xs).
128 partition :: (a -> Bool) -> [a] -> ([a],[a])
129 partition p xs = foldr select ([],[]) xs
130 where select x (ts,fs) | p x = (x:ts,fs)
131 | otherwise = (ts, x:fs)
136 mapAccumL :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
137 mapAccumL f s [] = (s, [])
138 mapAccumL f s (x:xs) = (s'',y:ys)
139 where (s', y ) = f s x
140 (s'',ys) = mapAccumL f s' xs
142 mapAccumR :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
143 mapAccumR f s [] = (s, [])
144 mapAccumR f s (x:xs) = (s'', y:ys)
145 where (s'',y ) = f s' x
146 (s', ys) = mapAccumR f s xs
147 sort :: (Ord a) => [a] -> [a]
148 sort = sortBy compare
150 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
151 sortBy cmp = foldr (insertBy cmp) []
153 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
154 insertBy cmp x [] = [x]
155 insertBy cmp x ys@(y:ys')
157 GT -> y : insertBy cmp x ys'
160 maximumBy :: (a -> a -> a) -> [a] -> a
161 maximumBy max [] = error "List.maximumBy: empty list"
162 maximumBy max xs = foldl1 max xs
164 minimumBy :: (a -> a -> a) -> [a] -> a
165 minimumBy min [] = error "List.minimumBy: empty list"
166 minimumBy min xs = foldl1 min xs
168 genericLength :: (Num i) => [b] -> i
170 genericLength (_:l) = 1 + genericLength l
172 genericTake :: (Integral i) => i -> [a] -> [a]
174 genericTake _ [] = []
175 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
176 genericTake _ _ = error "List.genericTake: negative argument"
178 genericDrop :: (Integral i) => i -> [a] -> [a]
179 genericDrop 0 xs = xs
180 genericDrop _ [] = []
181 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
182 genericDrop _ _ = error "List.genericDrop: negative argument"
184 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
185 genericSplitAt 0 xs = ([],xs)
186 genericSplitAt _ [] = ([],[])
187 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
188 (xs',xs'') = genericSplitAt (n-1) xs
189 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
192 genericIndex :: (Integral a) => [b] -> a -> b
193 genericIndex (x:_) 0 = x
194 genericIndex (_:xs) n
195 | n > 0 = genericIndex xs (n-1)
196 | otherwise = error "List.genericIndex: negative argument."
197 genericIndex _ _ = error "List.genericIndex: index too large."
199 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
200 zip4 = zipWith4 (,,,)
202 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
203 zip5 = zipWith5 (,,,,)
205 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
207 zip6 = zipWith6 (,,,,,)
209 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
210 [g] -> [(a,b,c,d,e,f,g)]
211 zip7 = zipWith7 (,,,,,,)
213 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
214 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
215 = z a b c d : zipWith4 z as bs cs ds
216 zipWith4 _ _ _ _ _ = []
218 zipWith5 :: (a->b->c->d->e->f) ->
219 [a]->[b]->[c]->[d]->[e]->[f]
220 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
221 = z a b c d e : zipWith5 z as bs cs ds es
222 zipWith5 _ _ _ _ _ _ = []
224 zipWith6 :: (a->b->c->d->e->f->g) ->
225 [a]->[b]->[c]->[d]->[e]->[f]->[g]
226 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
227 = z a b c d e f : zipWith6 z as bs cs ds es fs
228 zipWith6 _ _ _ _ _ _ _ = []
230 zipWith7 :: (a->b->c->d->e->f->g->h) ->
231 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
232 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
233 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
234 zipWith7 _ _ _ _ _ _ _ _ = []
236 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
237 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
238 (a:as,b:bs,c:cs,d:ds))
241 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
242 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
243 (a:as,b:bs,c:cs,d:ds,e:es))
246 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
247 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
248 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
251 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
252 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
253 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
254 ([],[],[],[],[],[],[])
258 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
259 deleteFirstsBy eq = foldl (flip (deleteBy eq))
261 -- elem, notElem, lookup, maximumBy and minimumBy are in PreludeList
262 elemBy, notElemBy :: (a -> a -> Bool) -> a -> [a] -> Bool
263 elemBy eq _ [] = False
264 elemBy eq x (y:ys) = x `eq` y || elemBy eq x ys
266 notElemBy eq x xs = not (elemBy eq x xs)
268 lookupBy :: (a -> a -> Bool) -> a -> [(a, b)] -> Maybe b
269 lookupBy eq key [] = Nothing
270 lookupBy eq key ((x,y):xys)
271 | key `eq` x = Just y
272 | otherwise = lookupBy eq key xys
275 -- sums and products give a list of running sums or products from
276 -- a list of numbers. e.g., sums [1,2,3] == [0,1,3,6]
277 sums, products :: (Num a) => [a] -> [a]
279 products = scanl (*) 1
281 genericReplicate :: (Integral i) => i -> a -> [a]
282 genericReplicate n x = genericTake n (repeat x)
284 -- group splits its list argument into a list of lists of equal, adjacent
286 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
287 group :: (Eq a) => [a] -> [[a]]
290 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
292 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
293 where (ys,zs) = span (eq x) xs
295 -- inits xs returns the list of initial segments of xs, shortest first.
296 -- e.g., inits "abc" == ["","a","ab","abc"]
297 inits :: [a] -> [[a]]
299 inits (x:xs) = [[]] ++ map (x:) (inits xs)
301 -- tails xs returns the list of all final segments of xs, longest first.
302 -- e.g., tails "abc" == ["abc", "bc", "c",""]
303 tails :: [a] -> [[a]]
305 tails xxs@(_:xs) = xxs : tails xs
307 {- Old stuff now not in List
309 elemIndexBy :: (a -> a -> Bool) -> [a] -> a -> Int
310 elemIndexBy eq [] x = error "List.elemIndexBy: empty list"
311 elemIndexBy eq (x:xs) x' = if x `eq` x' then 0 else 1 + elemIndexBy eq xs x'
313 -- subsequences xs returns the list of all subsequences of xs.
314 -- e.g., subsequences "abc" == ["","c","b","bc","a","ac","ab","abc"]
315 subsequences :: [a] -> [[a]]
316 subsequences [] = [[]]
317 subsequences (x:xs) = subsequences xs ++ map (x:) (subsequences xs)
319 -- permutations xs returns the list of all permutations of xs.
320 -- e.g., permutations "abc" == ["abc","bac","bca","acb","cab","cba"]
321 permutations :: [a] -> [[a]]
322 permutations [] = [[]]
323 permutations (x:xs) = [zs | ys <- permutations xs, zs <- interleave x ys ]
324 where interleave :: a -> [a] -> [[a]]
325 interleave x [] = [[x]]
326 interleave x (y:ys) = [x:y:ys] ++ map (y:) (interleave x ys)