List.hs 4.45 KB
Newer Older
1
{-# LANGUAGE NoImplicitPrelude #-}
2
{-# LANGUAGE Trustworthy #-}
3

4
-----------------------------------------------------------------------------
5
-- |
6 7
-- Module      :  Data.List
-- Copyright   :  (c) The University of Glasgow 2001
8
-- License     :  BSD-style (see the file libraries/base/LICENSE)
9
--
10
-- Maintainer  :  libraries@haskell.org
11
-- Stability   :  stable
12 13 14 15 16 17 18
-- Portability :  portable
--
-- Operations on lists.
--
-----------------------------------------------------------------------------

module Data.List
Don Stewart's avatar
Don Stewart committed
19
   (
20
   -- * Basic functions
21

22 23 24 25 26
     (++)
   , head
   , last
   , tail
   , init
David Feuer's avatar
David Feuer committed
27
   , uncons
28 29
   , null
   , length
30 31

   -- * List transformations
32 33
   , map
   , reverse
34

35 36 37
   , intersperse
   , intercalate
   , transpose
38

39 40
   , subsequences
   , permutations
41 42 43

   -- * Reducing lists (folds)

44 45 46 47 48 49
   , foldl
   , foldl'
   , foldl1
   , foldl1'
   , foldr
   , foldr1
50 51 52

   -- ** Special folds

53 54 55 56 57 58 59 60 61 62
   , concat
   , concatMap
   , and
   , or
   , any
   , all
   , sum
   , product
   , maximum
   , minimum
63 64 65 66

   -- * Building lists

   -- ** Scans
67
   , scanl
68
   , scanl'
69 70 71
   , scanl1
   , scanr
   , scanr1
72 73

   -- ** Accumulating maps
74 75
   , mapAccumL
   , mapAccumR
76 77

   -- ** Infinite lists
78 79 80 81
   , iterate
   , repeat
   , replicate
   , cycle
82 83

   -- ** Unfolding
84
   , unfoldr
85 86 87 88

   -- * Sublists

   -- ** Extracting sublists
89 90 91
   , take
   , drop
   , splitAt
92

93 94 95 96 97
   , takeWhile
   , dropWhile
   , dropWhileEnd
   , span
   , break
98

99
   , stripPrefix
100

101
   , group
102

103 104
   , inits
   , tails
105 106

   -- ** Predicates
107 108 109
   , isPrefixOf
   , isSuffixOf
   , isInfixOf
110
   , isSubsequenceOf
111 112 113 114

   -- * Searching lists

   -- ** Searching by equality
115 116 117
   , elem
   , notElem
   , lookup
118 119

   -- ** Searching with a predicate
120 121 122
   , find
   , filter
   , partition
123 124 125 126 127

   -- * Indexing lists
   -- | These functions treat a list @xs@ as a indexed collection,
   -- with indices ranging from 0 to @'length' xs - 1@.

128
   , (!!)
129

130 131
   , elemIndex
   , elemIndices
132

133 134
   , findIndex
   , findIndices
135 136 137

   -- * Zipping and unzipping lists

138
   , zip
Don Stewart's avatar
Don Stewart committed
139
   , zip3
140 141
   , zip4, zip5, zip6, zip7

142
   , zipWith
143
   , zipWith3
144 145
   , zipWith4, zipWith5, zipWith6, zipWith7

146
   , unzip
147
   , unzip3
148 149 150 151 152
   , unzip4, unzip5, unzip6, unzip7

   -- * Special lists

   -- ** Functions on strings
153 154 155 156
   , lines
   , words
   , unlines
   , unwords
157 158

   -- ** \"Set\" operations
Don Stewart's avatar
Don Stewart committed
159

160
   , nub
161

162 163
   , delete
   , (\\)
Don Stewart's avatar
Don Stewart committed
164

165 166
   , union
   , intersect
167 168

   -- ** Ordered lists
169
   , sort
170
   , sortOn
171
   , insert
172 173 174 175 176 177

   -- * Generalized functions

   -- ** The \"@By@\" operations
   -- | By convention, overloaded functions have a non-overloaded
   -- counterpart whose name is suffixed with \`@By@\'.
178 179 180 181
   --
   -- It is often convenient to use these functions together with
   -- 'Data.Function.on', for instance @'sortBy' ('compare'
   -- \`on\` 'fst')@.
182 183 184

   -- *** User-supplied equality (replacing an @Eq@ context)
   -- | The predicate is assumed to define an equivalence.
185 186 187 188 189 190
   , nubBy
   , deleteBy
   , deleteFirstsBy
   , unionBy
   , intersectBy
   , groupBy
191 192 193

   -- *** User-supplied comparison (replacing an @Ord@ context)
   -- | The function is assumed to define a total ordering.
194 195 196 197
   , sortBy
   , insertBy
   , maximumBy
   , minimumBy
198 199 200 201 202

   -- ** The \"@generic@\" operations
   -- | The prefix \`@generic@\' indicates an overloaded function that
   -- is a generalized version of a "Prelude" function.

203 204 205 206 207 208
   , genericLength
   , genericTake
   , genericDrop
   , genericSplitAt
   , genericIndex
   , genericReplicate
209 210 211

   ) where

212
import Data.Foldable
213
import Data.Traversable
214

215
import Data.OldList hiding ( all, and, any, concat, concatMap, elem, find,
216 217
                             foldl, foldl1, foldl', foldr, foldr1, mapAccumL,
                             mapAccumR, maximum, maximumBy, minimum, minimumBy,
218
                             length, notElem, null, or, product, sum )
219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241

import GHC.Base ( Bool(..), Eq((==)), otherwise )

-- | The 'isSubsequenceOf' function takes two lists and returns 'True' if the
-- first list is a subsequence of the second list.
--
-- @'isSubsequenceOf' x y@ is equivalent to @'elem' x ('subsequences' y)@.
--
-- /Since: 4.8.0.0/
--
-- ==== __Examples__
--
-- >>> isSubsequenceOf "GHC" "The Glorious Haskell Compiler"
-- True
-- >>> isSubsequenceOf ['a','d'..'z'] ['a'..'z']
-- True
-- >>> isSubsequenceOf [1..10] [10,9..0]
-- False
isSubsequenceOf :: (Eq a) => [a] -> [a] -> Bool
isSubsequenceOf []    _                    = True
isSubsequenceOf _     []                   = False
isSubsequenceOf a@(x:a') (y:b) | x == y    = isSubsequenceOf a' b
                               | otherwise = isSubsequenceOf a b