CODEWITHSUNDEEP
haskellset
problem_solver_level_1
problem_solver_level_1

Reputation: 33

Haskell: find out if an element in a Data.Set starts with a string?

Since it is possible to check for whether a string is in a set in the following manner:

import qualified Data.Set as S
S.member "examplestr"

I was wondering whether there is a function that tests whether a string is a prefix of a member of the set. For instance, if I want to find out if any of the members of the set begin with the string "ro", the function would return True if there was a string "roller" in the set. Thanks for replies

Upvotes: 1

Views: 380

Answers (2)

daniel gratzer
daniel gratzer

Reputation: 53901

Yep, since type String = [Char], we can use isPrefixOf,

anyStartsWith :: Eq a => [a] -> Set [a] -> Bool
anyStartsWith str set =  not . S.empty $ S.filter (isPrefixOf str) set

Or, since Set is foldable,

 import qualified Data.Foldable as F
 anyStartsWith str = F.any (isPrefixOf str)

Upvotes: 6

nponeccop
nponeccop

Reputation: 13677

Here is a faster O(log(N)) solution:

import qualified Data.Set as S
import Data.List

s = S.fromList [ "fowl", "foo", "foobar", "goo" ]

hasPrefix key s = case S.lookupGE key s of
        Nothing -> False
        Just p -> key `isPrefixOf` p

Here is a shorter variant using maybe from Data.Maybe:

hasPrefix key = maybe False (isPrefixOf key) . S.lookupGE key

Upvotes: 2

Related Questions