Haskell String substring function

Question

My function takes 2 strings and determines if the first string is a substring of the second input string. For instance:

isSubb "abc" "abcmhk" -- True
isSubb "abc" "uyabcmhk" -- True
isSubb "abc" "okaibcmhk" -- False
isSubb "abc" "amnabkaaabcmhk" -- gives True

So far I have:

isSubb :: [Char] -> [Char] -> Bool
isSubb sub str = auxx sub sub str

auxx :: [Char] -> [Char] -> [Char] -> Bool
auxx safe (s:ub) (st:r)
| s:ub == []    = True
| st:r == []  = False
| s == st   = auxx safe ub r
| otherwise  = auxx safe safe r

But its giving me a non-exhaustive error on the auxx function.

Any help is greatly appreciated! Thank you!

A bit nitpicking: you are looking for substrings (or sublists), not for subsets. Because "abc" is surely a subset of "axbycz", ins't it? — Ingo
– Ingo, Commented Nov 18, 2013 at 0:41

Mihai Maruseac · Accepted Answer · 2013-11-18 00:27:31Z

4

In Data.List there is the isInfixOF function.

isInfixOf :: Eq a => [a] -> [a] -> Bool

The isInfixOf function takes two lists and returns True iff the first list is contained, wholly and intact, anywhere within the second.

Prelude Data.List> isInfixOf "abc" "abcmhk"
True
Prelude Data.List> isInfixOf "abc" "uyabcmhk"
True
Prelude Data.List> isInfixOf "abc" "okaibcmhk"
False
Prelude Data.List> isInfixOf "abc" "amnabkaaabcmhk"
True

You could write your function like

import Data.List (isInfixOf)

isSubb :: [Char] -> [Char] -> Bool
isSubb sub str = isInfixOf sub str

edited Nov 18, 2013 at 0:27

Mihai Maruseac

21.5k7 gold badges61 silver badges110 bronze badges

answered Nov 17, 2013 at 23:55

Cameron White

5424 silver badges10 bronze badges

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

Comments

Mihai Maruseac · Accepted Answer · 2013-11-17 23:30:03Z

3

Your auxx function needs to take into account the cases where the second or the third parameters are [] (because you are getting there).

The s:ub == [] and st:r == [] will never be True since pattern matching happens before guard evaluation.

A sane equivalent of you function would be

auxx safe sub str
  | sub == [] = True
  | str == [] = False
  | head sub == head str = auxx safe ub r
  | otherwise = auxx safe safe r

Though the above is not efficient since it can be improved by pattern matching.

auxx _ [] _ = True
auxx _ _ [] = False
auxx safe (s:ub) (st:r)
  | s == st = auxx safe ub r
  | otherwise = auxx safe safe r

answered Nov 17, 2013 at 23:30

Mihai Maruseac

21.5k7 gold badges61 silver badges110 bronze badges

2 Comments

IanTimmis Over a year ago

Thank you! This worked beautifully! i was trying to figure out something like that and didnt know you could use _

Mihai Maruseac Over a year ago

_ stands for anything, you can place there a variable name and it will be pattern matched and bound but using _ is desirable because no pattern match and variable binding occurs - it is simply discarded.

user2994248 · Accepted Answer · 2013-11-17 23:31:14Z

-1

Your definition is not correct!

 | s == st   = auxx safe ub r

gives problems. Look, determining whether "abc" is in "afkjskgsbc" is not the same as determining whether "bc" is in "fkjskgsbc" . So you need to consider that the first letter may or may not be a part of the string you're looking for.

answered Nov 17, 2013 at 23:31

user2994248

1

3 Comments

Mihai Maruseac Over a year ago

This doesn't solve his error message. And, have you looked at his examples?

user2994248 Over a year ago

You're right, my answer is not helpful and he already has a right test case to check for. Sorry!

Mihai Maruseac Over a year ago

Also what you say is the problem in your answer is not a problem. Look at the otherwise branch

Collectives™ on Stack Overflow

Haskell String substring function

3 Answers 3

Comments

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related