diff options
| author | Alexander Berntsen <alexander@plaimi.net> | 2014-11-05 12:32:06 +0100 |
|---|---|---|
| committer | Herbert Valerio Riedel <hvr@gnu.org> | 2014-11-05 12:40:43 +0100 |
| commit | 40b1ee4043fefdd19ff6614a63939002840c6d97 (patch) | |
| tree | 18b7d83de2039366dcc2b8c85ec36d0ea91f9952 /libraries | |
| parent | ac0915b8f2b6f5b73f0a6d7e7739abe96c3745eb (diff) | |
| download | haskell-40b1ee4043fefdd19ff6614a63939002840c6d97.tar.gz | |
Add `isSubsequenceOf` to Data.List (#9767)
Niklas Hambüchen suggested that we add the dual of `subsequences`,
isSubsequenceOf (like `isPrefixOf` to `inits` & `isSuffixOf` to `tails`).
It was a simple and noncontroversial proposal which passed unanimously.
For more details see the original proposal discussion at
https://www.haskell.org/pipermail/libraries/2014-November/024063.html
Differential Revision: https://phabricator.haskell.org/D435
Signed-off-by: Alexander Berntsen <alexander@plaimi.net>
Diffstat (limited to 'libraries')
| -rw-r--r-- | libraries/base/Data/List.hs | 24 | ||||
| -rw-r--r-- | libraries/base/changelog.md | 2 |
2 files changed, 26 insertions, 0 deletions
diff --git a/libraries/base/Data/List.hs b/libraries/base/Data/List.hs index 193ebbc0c4..4f999261d8 100644 --- a/libraries/base/Data/List.hs +++ b/libraries/base/Data/List.hs @@ -106,6 +106,7 @@ module Data.List , isPrefixOf , isSuffixOf , isInfixOf + , isSubsequenceOf -- * Searching lists @@ -214,3 +215,26 @@ import Data.OldList hiding ( all, and, any, concat, concatMap, elem, find, foldl, foldl1, foldl', foldr, foldr1, mapAccumL, mapAccumR, maximum, maximumBy, minimum, minimumBy, length, notElem, null, or, product, sum ) + +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 diff --git a/libraries/base/changelog.md b/libraries/base/changelog.md index c3e1fa7240..86595d62e8 100644 --- a/libraries/base/changelog.md +++ b/libraries/base/changelog.md @@ -91,6 +91,8 @@ * Add `Alt`, an `Alternative` wrapper, to `Data.Monoid`. (#9759) + * Add `isSubsequenceOf` to `Data.List` (#9767) + ## 4.7.0.1 *Jul 2014* * Bundled with GHC 7.8.3 |