Add Data.Semigroup and Data.List.NonEmpty (re #10365)
[ghc.git] / libraries / base / Data / List / NonEmpty.hs
1 {-# LANGUAGE DeriveDataTypeable #-}
2 {-# LANGUAGE DeriveGeneric #-}
3 {-# LANGUAGE Trustworthy #-} -- can't use Safe due to IsList instance
4 {-# LANGUAGE TypeFamilies #-}
5
6 -----------------------------------------------------------------------------
7 -- |
8 -- Module : Data.List.NonEmpty
9 -- Copyright : (C) 2011-2015 Edward Kmett,
10 -- (C) 2010 Tony Morris, Oliver Taylor, Eelis van der Weegen
11 -- License : BSD-style (see the file LICENSE)
12 --
13 -- Maintainer : libraries@haskell.org
14 -- Stability : provisional
15 -- Portability : portable
16 --
17 -- A 'NonEmpty' list is one which always has at least one element, but
18 -- is otherwise identical to the traditional list type in complexity
19 -- and in terms of API. You will almost certainly want to import this
20 -- module @qualified@.
21 --
22 -- @since 4.8.2.0
23 ----------------------------------------------------------------------------
24
25 module Data.List.NonEmpty (
26 -- * The type of non-empty streams
27 NonEmpty(..)
28
29 -- * Non-empty stream transformations
30 , map -- :: (a -> b) -> NonEmpty a -> NonEmpty b
31 , intersperse -- :: a -> NonEmpty a -> NonEmpty a
32 , scanl -- :: Foldable f => (b -> a -> b) -> b -> f a -> NonEmpty b
33 , scanr -- :: Foldable f => (a -> b -> b) -> b -> f a -> NonEmpty b
34 , scanl1 -- :: (a -> a -> a) -> NonEmpty a -> NonEmpty a
35 , scanr1 -- :: (a -> a -> a) -> NonEmpty a -> NonEmpty a
36 , transpose -- :: NonEmpty (NonEmpty a) -> NonEmpty (NonEmpty a)
37 , sortBy -- :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
38 , sortWith -- :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a
39 -- * Basic functions
40 , length -- :: NonEmpty a -> Int
41 , head -- :: NonEmpty a -> a
42 , tail -- :: NonEmpty a -> [a]
43 , last -- :: NonEmpty a -> a
44 , init -- :: NonEmpty a -> [a]
45 , (<|), cons -- :: a -> NonEmpty a -> NonEmpty a
46 , uncons -- :: NonEmpty a -> (a, Maybe (NonEmpty a))
47 , unfoldr -- :: (a -> (b, Maybe a)) -> a -> NonEmpty b
48 , sort -- :: NonEmpty a -> NonEmpty a
49 , reverse -- :: NonEmpty a -> NonEmpty a
50 , inits -- :: Foldable f => f a -> NonEmpty a
51 , tails -- :: Foldable f => f a -> NonEmpty a
52 -- * Building streams
53 , iterate -- :: (a -> a) -> a -> NonEmpty a
54 , repeat -- :: a -> NonEmpty a
55 , cycle -- :: NonEmpty a -> NonEmpty a
56 , unfold -- :: (a -> (b, Maybe a) -> a -> NonEmpty b
57 , insert -- :: (Foldable f, Ord a) => a -> f a -> NonEmpty a
58 , some1 -- :: Alternative f => f a -> f (NonEmpty a)
59 -- * Extracting sublists
60 , take -- :: Int -> NonEmpty a -> [a]
61 , drop -- :: Int -> NonEmpty a -> [a]
62 , splitAt -- :: Int -> NonEmpty a -> ([a], [a])
63 , takeWhile -- :: Int -> NonEmpty a -> [a]
64 , dropWhile -- :: Int -> NonEmpty a -> [a]
65 , span -- :: Int -> NonEmpty a -> ([a],[a])
66 , break -- :: Int -> NonEmpty a -> ([a],[a])
67 , filter -- :: (a -> Bool) -> NonEmpty a -> [a]
68 , partition -- :: (a -> Bool) -> NonEmpty a -> ([a],[a])
69 , group -- :: Foldable f => Eq a => f a -> [NonEmpty a]
70 , groupBy -- :: Foldable f => (a -> a -> Bool) -> f a -> [NonEmpty a]
71 , groupWith -- :: (Foldable f, Eq b) => (a -> b) -> f a -> [NonEmpty a]
72 , groupAllWith -- :: (Foldable f, Ord b) => (a -> b) -> f a -> [NonEmpty a]
73 , group1 -- :: Eq a => NonEmpty a -> NonEmpty (NonEmpty a)
74 , groupBy1 -- :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)
75 , groupWith1 -- :: (Foldable f, Eq b) => (a -> b) -> f a -> NonEmpty (NonEmpty a)
76 , groupAllWith1 -- :: (Foldable f, Ord b) => (a -> b) -> f a -> NonEmpty (NonEmpty a)
77 -- * Sublist predicates
78 , isPrefixOf -- :: Foldable f => f a -> NonEmpty a -> Bool
79 -- * \"Set\" operations
80 , nub -- :: Eq a => NonEmpty a -> NonEmpty a
81 , nubBy -- :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty a
82 -- * Indexing streams
83 , (!!) -- :: NonEmpty a -> Int -> a
84 -- * Zipping and unzipping streams
85 , zip -- :: NonEmpty a -> NonEmpty b -> NonEmpty (a,b)
86 , zipWith -- :: (a -> b -> c) -> NonEmpty a -> NonEmpty b -> NonEmpty c
87 , unzip -- :: NonEmpty (a, b) -> (NonEmpty a, NonEmpty b)
88 -- * Functions on streams of characters
89 , words -- :: NonEmpty Char -> NonEmpty String
90 , unwords -- :: NonEmpty String -> NonEmpty Char
91 , lines -- :: NonEmpty Char -> NonEmpty String
92 , unlines -- :: NonEmpty String -> NonEmpty Char
93 -- * Converting to and from a list
94 , fromList -- :: [a] -> NonEmpty a
95 , toList -- :: NonEmpty a -> [a]
96 , nonEmpty -- :: [a] -> Maybe (NonEmpty a)
97 , xor -- :: NonEmpty a -> Bool
98 ) where
99
100
101 import Prelude hiding (break, cycle, drop, dropWhile,
102 filter, foldl, foldr, head, init, iterate,
103 last, length, lines, map, repeat, reverse,
104 scanl, scanl1, scanr, scanr1, span,
105 splitAt, tail, take, takeWhile, unlines,
106 unwords, unzip, words, zip, zipWith, (!!))
107 import qualified Prelude
108
109 import Control.Applicative (Alternative, many)
110 import Control.Monad (ap)
111 import Control.Monad.Fix
112 import Control.Monad.Zip (MonadZip(..))
113 import Data.Data (Data)
114 import Data.Foldable hiding (length, toList)
115 import qualified Data.Foldable as Foldable
116 import Data.Function (on)
117 import qualified Data.List as List
118 import Data.Ord (comparing)
119 import qualified GHC.Exts as Exts (IsList(..))
120 import GHC.Generics (Generic, Generic1)
121
122 infixr 5 :|, <|
123
124 -- | Non-empty (and non-strict) list type.
125 --
126 -- @since 4.8.2.0
127 data NonEmpty a = a :| [a]
128 deriving ( Eq, Ord, Show, Read, Data, Generic, Generic1 )
129
130 instance Exts.IsList (NonEmpty a) where
131 type Item (NonEmpty a) = a
132 fromList = fromList
133 toList = toList
134
135 instance MonadFix NonEmpty where
136 mfix f = case fix (f . head) of
137 ~(x :| _) -> x :| mfix (tail . f)
138
139 instance MonadZip NonEmpty where
140 mzip = zip
141 mzipWith = zipWith
142 munzip = unzip
143
144 -- | Number of elements in 'NonEmpty' list.
145 length :: NonEmpty a -> Int
146 length (_ :| xs) = 1 + Prelude.length xs
147
148 -- | Compute n-ary logic exclusive OR operation on 'NonEmpty' list.
149 xor :: NonEmpty Bool -> Bool
150 xor (x :| xs) = foldr xor' x xs
151 where xor' True y = not y
152 xor' False y = y
153
154 -- | 'unfold' produces a new stream by repeatedly applying the unfolding
155 -- function to the seed value to produce an element of type @b@ and a new
156 -- seed value. When the unfolding function returns 'Nothing' instead of
157 -- a new seed value, the stream ends.
158 unfold :: (a -> (b, Maybe a)) -> a -> NonEmpty b
159 unfold f a = case f a of
160 (b, Nothing) -> b :| []
161 (b, Just c) -> b <| unfold f c
162
163 -- | 'nonEmpty' efficiently turns a normal list into a 'NonEmpty' stream,
164 -- producing 'Nothing' if the input is empty.
165 nonEmpty :: [a] -> Maybe (NonEmpty a)
166 nonEmpty [] = Nothing
167 nonEmpty (a:as) = Just (a :| as)
168
169 -- | 'uncons' produces the first element of the stream, and a stream of the
170 -- remaining elements, if any.
171 uncons :: NonEmpty a -> (a, Maybe (NonEmpty a))
172 uncons ~(a :| as) = (a, nonEmpty as)
173
174 -- | The 'unfoldr' function is analogous to "Data.List"'s
175 -- 'Data.List.unfoldr' operation.
176 unfoldr :: (a -> (b, Maybe a)) -> a -> NonEmpty b
177 unfoldr f a = case f a of
178 (b, mc) -> b :| maybe [] go mc
179 where
180 go c = case f c of
181 (d, me) -> d : maybe [] go me
182
183 instance Functor NonEmpty where
184 fmap f ~(a :| as) = f a :| fmap f as
185 b <$ ~(_ :| as) = b :| (b <$ as)
186
187 instance Applicative NonEmpty where
188 pure a = a :| []
189 (<*>) = ap
190
191 instance Monad NonEmpty where
192 return a = a :| []
193 ~(a :| as) >>= f = b :| (bs ++ bs')
194 where b :| bs = f a
195 bs' = as >>= toList . f
196
197 instance Traversable NonEmpty where
198 traverse f ~(a :| as) = (:|) <$> f a <*> traverse f as
199
200 instance Foldable NonEmpty where
201 foldr f z ~(a :| as) = f a (foldr f z as)
202 foldl f z ~(a :| as) = foldl f (f z a) as
203 foldl1 f ~(a :| as) = foldl f a as
204 foldMap f ~(a :| as) = f a `mappend` foldMap f as
205 fold ~(m :| ms) = m `mappend` fold ms
206
207 -- | Extract the first element of the stream.
208 head :: NonEmpty a -> a
209 head ~(a :| _) = a
210
211 -- | Extract the possibly-empty tail of the stream.
212 tail :: NonEmpty a -> [a]
213 tail ~(_ :| as) = as
214
215 -- | Extract the last element of the stream.
216 last :: NonEmpty a -> a
217 last ~(a :| as) = List.last (a : as)
218
219 -- | Extract everything except the last element of the stream.
220 init :: NonEmpty a -> [a]
221 init ~(a :| as) = List.init (a : as)
222
223 -- | Prepend an element to the stream.
224 (<|) :: a -> NonEmpty a -> NonEmpty a
225 a <| ~(b :| bs) = a :| b : bs
226
227 -- | Synonym for '<|'.
228 cons :: a -> NonEmpty a -> NonEmpty a
229 cons = (<|)
230
231 -- | Sort a stream.
232 sort :: Ord a => NonEmpty a -> NonEmpty a
233 sort = lift List.sort
234
235 -- | Converts a normal list to a 'NonEmpty' stream.
236 --
237 -- Raises an error if given an empty list.
238 fromList :: [a] -> NonEmpty a
239 fromList (a:as) = a :| as
240 fromList [] = error "NonEmpty.fromList: empty list"
241
242 -- | Convert a stream to a normal list efficiently.
243 toList :: NonEmpty a -> [a]
244 toList ~(a :| as) = a : as
245
246 -- | Lift list operations to work on a 'NonEmpty' stream.
247 --
248 -- /Beware/: If the provided function returns an empty list,
249 -- this will raise an error.
250 lift :: Foldable f => ([a] -> [b]) -> f a -> NonEmpty b
251 lift f = fromList . f . Foldable.toList
252
253 -- | Map a function over a 'NonEmpty' stream.
254 map :: (a -> b) -> NonEmpty a -> NonEmpty b
255 map f ~(a :| as) = f a :| fmap f as
256
257 -- | The 'inits' function takes a stream @xs@ and returns all the
258 -- finite prefixes of @xs@.
259 inits :: Foldable f => f a -> NonEmpty [a]
260 inits = fromList . List.inits . Foldable.toList
261
262 -- | The 'tails' function takes a stream @xs@ and returns all the
263 -- suffixes of @xs@.
264 tails :: Foldable f => f a -> NonEmpty [a]
265 tails = fromList . List.tails . Foldable.toList
266
267 -- | @'insert' x xs@ inserts @x@ into the last position in @xs@ where it
268 -- is still less than or equal to the next element. In particular, if the
269 -- list is sorted beforehand, the result will also be sorted.
270 insert :: (Foldable f, Ord a) => a -> f a -> NonEmpty a
271 insert a = fromList . List.insert a . Foldable.toList
272
273 -- | @'some1' x@ sequences @x@ one or more times.
274 some1 :: Alternative f => f a -> f (NonEmpty a)
275 some1 x = (:|) <$> x <*> many x
276
277 -- | 'scanl' is similar to 'foldl', but returns a stream of successive
278 -- reduced values from the left:
279 --
280 -- > scanl f z [x1, x2, ...] == z :| [z `f` x1, (z `f` x1) `f` x2, ...]
281 --
282 -- Note that
283 --
284 -- > last (scanl f z xs) == foldl f z xs.
285 scanl :: Foldable f => (b -> a -> b) -> b -> f a -> NonEmpty b
286 scanl f z = fromList . List.scanl f z . Foldable.toList
287
288 -- | 'scanr' is the right-to-left dual of 'scanl'.
289 -- Note that
290 --
291 -- > head (scanr f z xs) == foldr f z xs.
292 scanr :: Foldable f => (a -> b -> b) -> b -> f a -> NonEmpty b
293 scanr f z = fromList . List.scanr f z . Foldable.toList
294
295 -- | 'scanl1' is a variant of 'scanl' that has no starting value argument:
296 --
297 -- > scanl1 f [x1, x2, ...] == x1 :| [x1 `f` x2, x1 `f` (x2 `f` x3), ...]
298 scanl1 :: (a -> a -> a) -> NonEmpty a -> NonEmpty a
299 scanl1 f ~(a :| as) = fromList (List.scanl f a as)
300
301 -- | 'scanr1' is a variant of 'scanr' that has no starting value argument.
302 scanr1 :: (a -> a -> a) -> NonEmpty a -> NonEmpty a
303 scanr1 f ~(a :| as) = fromList (List.scanr1 f (a:as))
304
305 -- | 'intersperse x xs' alternates elements of the list with copies of @x@.
306 --
307 -- > intersperse 0 (1 :| [2,3]) == 1 :| [0,2,0,3]
308 intersperse :: a -> NonEmpty a -> NonEmpty a
309 intersperse a ~(b :| bs) = b :| case bs of
310 [] -> []
311 _ -> a : List.intersperse a bs
312
313 -- | @'iterate' f x@ produces the infinite sequence
314 -- of repeated applications of @f@ to @x@.
315 --
316 -- > iterate f x = x :| [f x, f (f x), ..]
317 iterate :: (a -> a) -> a -> NonEmpty a
318 iterate f a = a :| List.iterate f (f a)
319
320 -- | @'cycle' xs@ returns the infinite repetition of @xs@:
321 --
322 -- > cycle [1,2,3] = 1 :| [2,3,1,2,3,...]
323 cycle :: NonEmpty a -> NonEmpty a
324 cycle = fromList . List.cycle . toList
325
326 -- | 'reverse' a finite NonEmpty stream.
327 reverse :: NonEmpty a -> NonEmpty a
328 reverse = lift List.reverse
329
330 -- | @'repeat' x@ returns a constant stream, where all elements are
331 -- equal to @x@.
332 repeat :: a -> NonEmpty a
333 repeat a = a :| List.repeat a
334
335 -- | @'take' n xs@ returns the first @n@ elements of @xs@.
336 take :: Int -> NonEmpty a -> [a]
337 take n = List.take n . toList
338
339 -- | @'drop' n xs@ drops the first @n@ elements off the front of
340 -- the sequence @xs@.
341 drop :: Int -> NonEmpty a -> [a]
342 drop n = List.drop n . toList
343
344 -- | @'splitAt' n xs@ returns a pair consisting of the prefix of @xs@
345 -- of length @n@ and the remaining stream immediately following this prefix.
346 --
347 -- > 'splitAt' n xs == ('take' n xs, 'drop' n xs)
348 -- > xs == ys ++ zs where (ys, zs) = 'splitAt' n xs
349 splitAt :: Int -> NonEmpty a -> ([a],[a])
350 splitAt n = List.splitAt n . toList
351
352 -- | @'takeWhile' p xs@ returns the longest prefix of the stream
353 -- @xs@ for which the predicate @p@ holds.
354 takeWhile :: (a -> Bool) -> NonEmpty a -> [a]
355 takeWhile p = List.takeWhile p . toList
356
357 -- | @'dropWhile' p xs@ returns the suffix remaining after
358 -- @'takeWhile' p xs@.
359 dropWhile :: (a -> Bool) -> NonEmpty a -> [a]
360 dropWhile p = List.dropWhile p . toList
361
362 -- | @'span' p xs@ returns the longest prefix of @xs@ that satisfies
363 -- @p@, together with the remainder of the stream.
364 --
365 -- > 'span' p xs == ('takeWhile' p xs, 'dropWhile' p xs)
366 -- > xs == ys ++ zs where (ys, zs) = 'span' p xs
367 span :: (a -> Bool) -> NonEmpty a -> ([a], [a])
368 span p = List.span p . toList
369
370 -- | The @'break' p@ function is equivalent to @'span' (not . p)@.
371 break :: (a -> Bool) -> NonEmpty a -> ([a], [a])
372 break p = span (not . p)
373
374 -- | @'filter' p xs@ removes any elements from @xs@ that do not satisfy @p@.
375 filter :: (a -> Bool) -> NonEmpty a -> [a]
376 filter p = List.filter p . toList
377
378 -- | The 'partition' function takes a predicate @p@ and a stream
379 -- @xs@, and returns a pair of lists. The first list corresponds to the
380 -- elements of @xs@ for which @p@ holds; the second corresponds to the
381 -- elements of @xs@ for which @p@ does not hold.
382 --
383 -- > 'partition' p xs = ('filter' p xs, 'filter' (not . p) xs)
384 partition :: (a -> Bool) -> NonEmpty a -> ([a], [a])
385 partition p = List.partition p . toList
386
387 -- | The 'group' function takes a stream and returns a list of
388 -- streams such that flattening the resulting list is equal to the
389 -- argument. Moreover, each stream in the resulting list
390 -- contains only equal elements. For example, in list notation:
391 --
392 -- > 'group' $ 'cycle' "Mississippi"
393 -- > = "M" : "i" : "ss" : "i" : "ss" : "i" : "pp" : "i" : "M" : "i" : ...
394 group :: (Foldable f, Eq a) => f a -> [NonEmpty a]
395 group = groupBy (==)
396
397 -- | 'groupBy' operates like 'group', but uses the provided equality
398 -- predicate instead of `==`.
399 groupBy :: Foldable f => (a -> a -> Bool) -> f a -> [NonEmpty a]
400 groupBy eq0 = go eq0 . Foldable.toList
401 where
402 go _ [] = []
403 go eq (x : xs) = (x :| ys) : groupBy eq zs
404 where (ys, zs) = List.span (eq x) xs
405
406 -- | 'groupWith' operates like 'group', but uses the provided projection when
407 -- comparing for equality
408 groupWith :: (Foldable f, Eq b) => (a -> b) -> f a -> [NonEmpty a]
409 groupWith f = groupBy ((==) `on` f)
410
411 -- | 'groupAllWith' operates like 'groupWith', but sorts the list
412 -- first so that each equivalence class has, at most, one list in the
413 -- output
414 groupAllWith :: (Ord b) => (a -> b) -> [a] -> [NonEmpty a]
415 groupAllWith f = groupWith f . List.sortBy (compare `on` f)
416
417 -- | 'group1' operates like 'group', but uses the knowledge that its
418 -- input is non-empty to produce guaranteed non-empty output.
419 group1 :: Eq a => NonEmpty a -> NonEmpty (NonEmpty a)
420 group1 = groupBy1 (==)
421
422 -- | 'groupBy1' is to 'group1' as 'groupBy' is to 'group'.
423 groupBy1 :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)
424 groupBy1 eq (x :| xs) = (x :| ys) :| groupBy eq zs
425 where (ys, zs) = List.span (eq x) xs
426
427 -- | 'groupWith1' is to 'group1' as 'groupWith' is to 'group'
428 groupWith1 :: (Eq b) => (a -> b) -> NonEmpty a -> NonEmpty (NonEmpty a)
429 groupWith1 f = groupBy1 ((==) `on` f)
430
431 -- | 'groupAllWith1' is to 'groupWith1' as 'groupAllWith' is to 'groupWith'
432 groupAllWith1 :: (Ord b) => (a -> b) -> NonEmpty a -> NonEmpty (NonEmpty a)
433 groupAllWith1 f = groupWith1 f . sortWith f
434
435 -- | The 'isPrefix' function returns @True@ if the first argument is
436 -- a prefix of the second.
437 isPrefixOf :: Eq a => [a] -> NonEmpty a -> Bool
438 isPrefixOf [] _ = True
439 isPrefixOf (y:ys) (x :| xs) = (y == x) && List.isPrefixOf ys xs
440
441 -- | @xs !! n@ returns the element of the stream @xs@ at index
442 -- @n@. Note that the head of the stream has index 0.
443 --
444 -- /Beware/: a negative or out-of-bounds index will cause an error.
445 (!!) :: NonEmpty a -> Int -> a
446 (!!) ~(x :| xs) n
447 | n == 0 = x
448 | n > 0 = xs List.!! (n - 1)
449 | otherwise = error "NonEmpty.!! negative argument"
450
451 -- | The 'zip' function takes two streams and returns a stream of
452 -- corresponding pairs.
453 zip :: NonEmpty a -> NonEmpty b -> NonEmpty (a,b)
454 zip ~(x :| xs) ~(y :| ys) = (x, y) :| List.zip xs ys
455
456 -- | The 'zipWith' function generalizes 'zip'. Rather than tupling
457 -- the elements, the elements are combined using the function
458 -- passed as the first argument.
459 zipWith :: (a -> b -> c) -> NonEmpty a -> NonEmpty b -> NonEmpty c
460 zipWith f ~(x :| xs) ~(y :| ys) = f x y :| List.zipWith f xs ys
461
462 -- | The 'unzip' function is the inverse of the 'zip' function.
463 unzip :: Functor f => f (a,b) -> (f a, f b)
464 unzip xs = (fst <$> xs, snd <$> xs)
465
466 -- | The 'words' function breaks a stream of characters into a
467 -- stream of words, which were delimited by white space.
468 --
469 -- /Beware/: if the input contains no words (i.e. is entirely
470 -- whitespace), this will cause an error.
471 words :: NonEmpty Char -> NonEmpty String
472 words = lift List.words
473
474 -- | The 'unwords' function is an inverse operation to 'words'. It
475 -- joins words with separating spaces.
476 --
477 -- /Beware/: the input @(\"\" :| [])@ will cause an error.
478 unwords :: NonEmpty String -> NonEmpty Char
479 unwords = lift List.unwords
480
481 -- | The 'lines' function breaks a stream of characters into a stream
482 -- of strings at newline characters. The resulting strings do not
483 -- contain newlines.
484 lines :: NonEmpty Char -> NonEmpty String
485 lines = lift List.lines
486
487 -- | The 'unlines' function is an inverse operation to 'lines'. It
488 -- joins lines, after appending a terminating newline to each.
489 unlines :: NonEmpty String -> NonEmpty Char
490 unlines = lift List.unlines
491
492 -- | The 'nub' function removes duplicate elements from a list. In
493 -- particular, it keeps only the first occurence of each element.
494 -- (The name 'nub' means \'essence\'.)
495 -- It is a special case of 'nubBy', which allows the programmer to
496 -- supply their own inequality test.
497 nub :: Eq a => NonEmpty a -> NonEmpty a
498 nub = nubBy (==)
499
500 -- | The 'nubBy' function behaves just like 'nub', except it uses a
501 -- user-supplied equality predicate instead of the overloaded '=='
502 -- function.
503 nubBy :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty a
504 nubBy eq (a :| as) = a :| List.nubBy eq (List.filter (\b -> not (eq a b)) as)
505
506 -- | 'transpose' for 'NonEmpty', behaves the same as 'Data.List.transpose'
507 -- The rows/columns need not be the same length, in which case
508 -- > transpose . transpose /= id
509 transpose :: NonEmpty (NonEmpty a) -> NonEmpty (NonEmpty a)
510 transpose = fmap fromList
511 . fromList . List.transpose . Foldable.toList
512 . fmap Foldable.toList
513
514 -- | 'sortBy' for 'NonEmpty', behaves the same as 'Data.List.sortBy'
515 sortBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
516 sortBy f = lift (List.sortBy f)
517
518 -- | 'sortWith' for 'NonEmpty', behaves the same as:
519 --
520 -- > sortBy . comparing
521 sortWith :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a
522 sortWith = sortBy . comparing