Add `isSubsequenceOf` to Data.List (#9767)
authorAlexander Berntsen <alexander@plaimi.net>
Wed, 5 Nov 2014 11:32:06 +0000 (12:32 +0100)
committerHerbert Valerio Riedel <hvr@gnu.org>
Wed, 5 Nov 2014 11:40:43 +0000 (12:40 +0100)
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>
libraries/base/Data/List.hs
libraries/base/changelog.md

index 193ebbc..4f99926 100644 (file)
@@ -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
index c3e1fa7..86595d6 100644 (file)
@@ -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