0300b1bc433d38e7fd61c5fde7c22a0d99849eb5
[haskell-report.git] / report / lib-code / List.hs
1 module List (
2 elemIndex, elemIndices,
3 find, findIndex, findIndices,
4 nub, nubBy, delete, deleteBy, (\\), deleteFirstsBy,
5 union, unionBy, intersect, intersectBy,
6 intersperse, transpose, partition, group, groupBy,
7 inits, tails, isPrefixOf, isSuffixOf,
8 mapAccumL, mapAccumR,
9 sort, sortBy, insert, insertBy, maximumBy, minimumBy,
10 genericLength, genericTake, genericDrop,
11 genericSplitAt, genericIndex, genericReplicate,
12 zip4, zip5, zip6, zip7,
13 zipWith4, zipWith5, zipWith6, zipWith7,
14 unzip4, unzip5, unzip6, unzip7, unfoldr,
15
16 -- ...and what the Prelude exports
17 -- []((:), []), -- This is built-in syntax
18 map, (++), concat, filter,
19 head, last, tail, init, null, length, (!!),
20 foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,
21 iterate, repeat, replicate, cycle,
22 take, drop, splitAt, takeWhile, dropWhile, span, break,
23 lines, words, unlines, unwords, reverse, and, or,
24 any, all, elem, notElem, lookup,
25 sum, product, maximum, minimum, concatMap,
26 zip, zip3, zipWith, zipWith3, unzip, unzip3
27 ) where
28
29 import Maybe( listToMaybe )
30
31 infix 5 \\
32
33 elemIndex :: Eq a => a -> [a] -> Maybe Int
34 elemIndex x = findIndex (x ==)
35
36 elemIndices :: Eq a => a -> [a] -> [Int]
37 elemIndices x = findIndices (x ==)
38
39 find :: (a -> Bool) -> [a] -> Maybe a
40 find p = listToMaybe . filter p
41
42 findIndex :: (a -> Bool) -> [a] -> Maybe Int
43 findIndex p = listToMaybe . findIndices p
44
45 findIndices :: (a -> Bool) -> [a] -> [Int]
46 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x ]
47
48 nub :: Eq a => [a] -> [a]
49 nub = nubBy (==)
50
51 nubBy :: (a -> a -> Bool) -> [a] -> [a]
52 nubBy eq [] = []
53 nubBy eq (x:xs) = x : nubBy eq (filter (\y -> not (eq x y)) xs)
54
55 delete :: Eq a => a -> [a] -> [a]
56 delete = deleteBy (==)
57
58 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
59 deleteBy eq x [] = []
60 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
61
62 (\\) :: Eq a => [a] -> [a] -> [a]
63 (\\) = foldl (flip delete)
64
65 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
66 deleteFirstsBy eq = foldl (flip (deleteBy eq))
67
68 union :: Eq a => [a] -> [a] -> [a]
69 union = unionBy (==)
70
71 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
72 unionBy eq xs ys = xs ++ deleteFirstsBy eq (nubBy eq ys) xs
73
74 intersect :: Eq a => [a] -> [a] -> [a]
75 intersect = intersectBy (==)
76
77 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
78 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
79
80 intersperse :: a -> [a] -> [a]
81 intersperse sep [] = []
82 intersperse sep [x] = [x]
83 intersperse sep (x:xs) = x : sep : intersperse sep xs
84
85 -- transpose is lazy in both rows and columns,
86 -- and works for non-rectangular 'matrices'
87 -- For example, transpose [[1,2],[3,4,5],[]] = [[1,3],[2,4],[5]]
88 -- Note that [h | (h:t) <- xss] is not the same as (map head xss)
89 -- because the former discards empty sublists inside xss
90 transpose :: [[a]] -> [[a]]
91 transpose [] = []
92 transpose ([] : xss) = transpose xss
93 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) :
94 transpose (xs : [t | (h:t) <- xss])
95
96 partition :: (a -> Bool) -> [a] -> ([a],[a])
97 partition p xs = (filter p xs, filter (not . p) xs)
98
99 -- group splits its list argument into a list of lists of equal, adjacent
100 -- elements. e.g.,
101 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
102 group :: Eq a => [a] -> [[a]]
103 group = groupBy (==)
104
105 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
106 groupBy eq [] = []
107 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
108 where (ys,zs) = span (eq x) xs
109
110 -- inits xs returns the list of initial segments of xs, shortest first.
111 -- e.g., inits "abc" == ["","a","ab","abc"]
112 inits :: [a] -> [[a]]
113 inits [] = [[]]
114 inits (x:xs) = [[]] ++ map (x:) (inits xs)
115
116 -- tails xs returns the list of all final segments of xs, longest first.
117 -- e.g., tails "abc" == ["abc", "bc", "c",""]
118 tails :: [a] -> [[a]]
119 tails [] = [[]]
120 tails xxs@(_:xs) = xxs : tails xs
121
122 isPrefixOf :: Eq a => [a] -> [a] -> Bool
123 isPrefixOf [] _ = True
124 isPrefixOf _ [] = False
125 isPrefixOf (x:xs) (y:ys) = x == y && isPrefixOf xs ys
126
127 isSuffixOf :: Eq a => [a] -> [a] -> Bool
128 isSuffixOf x y = reverse x `isPrefixOf` reverse y
129
130 mapAccumL :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
131 mapAccumL f s [] = (s, [])
132 mapAccumL f s (x:xs) = (s'',y:ys)
133 where (s', y ) = f s x
134 (s'',ys) = mapAccumL f s' xs
135
136 mapAccumR :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
137 mapAccumR f s [] = (s, [])
138 mapAccumR f s (x:xs) = (s'', y:ys)
139 where (s'',y ) = f s' x
140 (s', ys) = mapAccumR f s xs
141
142 unfoldr :: (b -> Maybe (a,b)) -> b -> [a]
143 unfoldr f b = case f b of
144 Nothing -> []
145 Just (a,b) -> a : unfoldr f b
146
147 sort :: (Ord a) => [a] -> [a]
148 sort = sortBy compare
149
150 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
151 sortBy cmp = foldr (insertBy cmp) []
152
153 insert :: (Ord a) => a -> [a] -> [a]
154 insert = insertBy compare
155
156 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
157 insertBy cmp x [] = [x]
158 insertBy cmp x ys@(y:ys')
159 = case cmp x y of
160 GT -> y : insertBy cmp x ys'
161 _ -> x : ys
162
163 maximumBy :: (a -> a -> Ordering) -> [a] -> a
164 maximumBy cmp [] = error "List.maximumBy: empty list"
165 maximumBy cmp xs = foldl1 max xs
166 where
167 max x y = case cmp x y of
168 GT -> x
169 _ -> y
170
171 minimumBy :: (a -> a -> Ordering) -> [a] -> a
172 minimumBy cmp [] = error "List.minimumBy: empty list"
173 minimumBy cmp xs = foldl1 min xs
174 where
175 min x y = case cmp x y of
176 GT -> y
177 _ -> x
178
179 genericLength :: (Integral a) => [b] -> a
180 genericLength [] = 0
181 genericLength (x:xs) = 1 + genericLength xs
182
183 genericTake :: (Integral a) => a -> [b] -> [b]
184 genericTake _ [] = []
185 genericTake 0 _ = []
186 genericTake n (x:xs)
187 | n > 0 = x : genericTake (n-1) xs
188 | otherwise = error "List.genericTake: negative argument"
189
190 genericDrop :: (Integral a) => a -> [b] -> [b]
191 genericDrop 0 xs = xs
192 genericDrop _ [] = []
193 genericDrop n (_:xs)
194 | n > 0 = genericDrop (n-1) xs
195 | otherwise = error "List.genericDrop: negative argument"
196
197 genericSplitAt :: (Integral a) => a -> [b] -> ([b],[b])
198 genericSplitAt 0 xs = ([],xs)
199 genericSplitAt _ [] = ([],[])
200 genericSplitAt n (x:xs)
201 | n > 0 = (x:xs',xs'')
202 | otherwise = error "List.genericSplitAt: negative argument"
203 where (xs',xs'') = genericSplitAt (n-1) xs
204
205 genericIndex :: (Integral a) => [b] -> a -> b
206 genericIndex (x:_) 0 = x
207 genericIndex (_:xs) n
208 | n > 0 = genericIndex xs (n-1)
209 | otherwise = error "List.genericIndex: negative argument"
210 genericIndex _ _ = error "List.genericIndex: index too large"
211
212 genericReplicate :: (Integral a) => a -> b -> [b]
213 genericReplicate n x = genericTake n (repeat x)
214
215 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
216 zip4 = zipWith4 (,,,)
217
218 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
219 zip5 = zipWith5 (,,,,)
220
221 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
222 [(a,b,c,d,e,f)]
223 zip6 = zipWith6 (,,,,,)
224
225 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
226 [g] -> [(a,b,c,d,e,f,g)]
227 zip7 = zipWith7 (,,,,,,)
228
229 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
230 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
231 = z a b c d : zipWith4 z as bs cs ds
232 zipWith4 _ _ _ _ _ = []
233
234 zipWith5 :: (a->b->c->d->e->f) ->
235 [a]->[b]->[c]->[d]->[e]->[f]
236 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
237 = z a b c d e : zipWith5 z as bs cs ds es
238 zipWith5 _ _ _ _ _ _ = []
239
240 zipWith6 :: (a->b->c->d->e->f->g) ->
241 [a]->[b]->[c]->[d]->[e]->[f]->[g]
242 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
243 = z a b c d e f : zipWith6 z as bs cs ds es fs
244 zipWith6 _ _ _ _ _ _ _ = []
245
246 zipWith7 :: (a->b->c->d->e->f->g->h) ->
247 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
248 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
249 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
250 zipWith7 _ _ _ _ _ _ _ _ = []
251
252 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
253 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
254 (a:as,b:bs,c:cs,d:ds))
255 ([],[],[],[])
256
257 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
258 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
259 (a:as,b:bs,c:cs,d:ds,e:es))
260 ([],[],[],[],[])
261
262 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
263 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
264 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
265 ([],[],[],[],[],[])
266
267 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
268 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
269 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
270 ([],[],[],[],[],[],[])