How to make these string matching functions in Haskell?

Question

Consider the following multi-line string S:

apple
banana berry
cantelope

I'm trying to write/locate Haskell functions which I will call in this post or-match and and-match. Here are some examples of what they should do:

or-match S ("apple","berry")

{- should return the two line string:
apple
banana berry
-}

and-match S ("apple", "berry") --should return the empty string, or something like "No matches."

and-match S ("banana" "berry") --should return a single line containing "banana berry"

In the above examples, I used the type (String, String) for the domain argument of or-match and and-match. I'm not sure that's the best way to go about it though, since I might want to use more than two arguments. I'm new to Haskell though, and am not sure how to make an tuple of arbitrary length the argument of a function.

In sum, the overall question of this post: How do I make or-match and and-match in Haskell, such that the domain argument for each of these functions is a tuple of arbitrary length (or some type that allows an arbitrary length of searches)?

Daniel Wagner · Accepted Answer · 2016-04-28 21:39:36Z

4

You may write

andMatchPred, orMatchPred :: Eq a => [a] -> [a] -> Bool
andMatchPred needles haystack = all (`elem` haystack) needles
orMatchPred  needles haystack = any (`elem` haystack) needles

Then your desired functions might be written as

andMatch, orMatch :: Eq a => [a] -> [[a]] -> [[a]]
andMatch = filter . andMatchPred
orMatch  = filter . orMatchPred

There should be plenty of opportunities to improve the efficiency later if that turns out to be a bottleneck, but the simple and readable implementation should come first.

A quick use in ghci to show how it might be used:

> let s = [["apple"],["banana","berry"],["cantelope"]]
> andMatch ["apple", "berry"] s
[]
> orMatch ["apple", "berry"] s
[["apple"],["banana","berry"]]

answered Apr 28, 2016 at 21:39

Daniel Wagner

156k10 gold badges231 silver badges392 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

bheklilr · Accepted Answer · 2016-04-28 21:45:21Z

2

such that the domain argument for each of these functions is a tuple of arbitrary length (or some type that allows an arbitrary length of searches)?

You're looking for a list, specifically in this case [String]. Tuples are fixed length but allow for a different type in each position, lists are homogeneous meaning each value has to have the same type, but are of arbitrary length.

So what you're looking for is are functions of type

orMatch, andMatch :: [String] -> [String] -> [String]

You'll need a function hasSubString :: String -> String -> Bool that you'll have to write yourself, but your code could look something like the following pseudo-code:

orMatch lines searchTerms = filter (\line -> any (hasSubString line) searchTerms) lines
andMatch lines searchTerms = filter (\line -> all (hasSubString line) searchTerms) lines

Where

hasSubString string substring

returns True if substring appears in string, and False otherwise. For example hasSubString "hello, world" "world" == True, hasSubString "hello, world" "unicorns" == False

answered Apr 28, 2016 at 21:45

bheklilr

54.2k6 gold badges112 silver badges166 bronze badges

1 Comment

Daniel Wagner Over a year ago

It's not necessary to implement hasSubString yourself; the standard libraries have it as isInfixOf, and more efficient versions exist on Hackage.

Collectives™ on Stack Overflow

How to make these string matching functions in Haskell?

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related