Proposal: Add isSubsequenceOf to Data.List
Data.List has `subsequences`, calculating all subsequences of a list, but it doesn't provide a function to check whether a list is a subsequence of another list. `isSubsequenceOf` would go into the "Predicates" section (http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-List.html#g:12) which already contains: * isPrefixOf (dual of inits) * isSuffixOf (dual of tails) * isInfixOf With this proposal, we would add * isSubsequenceOf (dual of subsequences) Suggested implementation: -- | `isSubsequenceOf a b`: Checks if a is a subsequence of b. 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 Niklas
On 2014-10-13 at 17:34:17 +0200, Niklas Hambüchen wrote: [...]
With this proposal, we would add
* isSubsequenceOf (dual of subsequences)
Suggested implementation:
-- | `isSubsequenceOf a b`: Checks if a is a subsequence of b. 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
+1
Hi, Am Montag, den 13.10.2014, 17:34 +0200 schrieb Niklas Hambüchen:
`isSubsequenceOf` would go into the "Predicates" section (http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-List.html#g:12) which already contains:
* isPrefixOf (dual of inits) * isSuffixOf (dual of tails) * isInfixOf
With this proposal, we would add
* isSubsequenceOf (dual of subsequences)
+1
Suggested implementation:
-- | `isSubsequenceOf a b`: Checks if a is a subsequence of b. 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
The docs should explain what a subsequence is (possibly by giving an educating example, or referring to "subsequences"). Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org
On Mon, Oct 13, 2014 at 10:34 PM, Niklas Hambüchen
* isSubsequenceOf (dual of subsequences)
+1 Suggested haddock to assist usage: Every infix of str is also a subsequence of str, but the converse doesn't generally hold. E.g. "ac" `isSubsequenceOf` "abc" is True, but "ac" `isInfixOf` "abc" is False. As negative examples, neither "ba" nor "bca" isSubsequenceOf "abc". -- Kim-Ee
participants (4)
-
Herbert Valerio Riedel -
Joachim Breitner -
Kim-Ee Yeoh -
Niklas Hambüchen