EDIT: It turns out that by folding over the pattern instead of the string, the code gets a lot simpler and shorter and something like
"" `isPrefixOf` undefined
works. Thank you @dfeuer and @WillNess. This is the updated program:
isPrefixOf pattern s = foldr g (const True) pattern s
where
g x r (h:t)
| x == h = r t
| otherwise = False
It works almost the same way as the below program, so refer to that for the explanation.
I managed to solve it using nothing but foldr:
isPrefixOf :: String -> String -> Bool
p `isPrefixOf` s = isPrefixOfS p
where
isPrefixOfS
= foldr
(\c acc ->
\str -> case str of
x:xs -> if c == x
then acc xs
else False
[] -> True
)
null
s
Here's the explanation.
In order to create the function isPrefixOf, we want this:
isPrefixOf pattern s
= case pattern of
[] -> True
x:xs -> if (null s) then False
else if (head s) /= x
then False
else xs `isPrefixOf` (tail s)
Well, let's simplify this - let's create a function called isPrefixOfS that only takes a pattern, which it compares to s automatically. We need to build this chain of nested functions:
-- Pseudocode, not actual Haskell
\p -> case p of
[] -> True
x:xs -> if x /= (s !! 0)
then False
else <apply xs to> \q -> case q of [] -> True
x:xs -> if x /= (s !! 1) -- Note that we've incremented the index
then False
else <apply xs to> \r -> ....
This seems pretty self explanatory - let me know in a comment if it requires further explanation.
Well, we can see that this chain has a recursive property to it, where the last character of s will be compared in the most deeply nested lambda. So we need to nest lambdas from right to left. What can we use for that? foldr.
isPrefixOfS
= foldr -- Folding from right to left across `s`
(\c acc -> -- `c` is the current character of `s`, acc is the chain of nested functions so far
\str -> -- We return a function in the fold that takes a String
case str of
-- If the string is not null:
x:xs -> if c == x -- If the head of the string is equal to the current character of s,
then acc xs -- Then pass the tail of the string to the nested function which will compare it with subsequent characters of s
else False -- Otherwise we return false
-- If the string is null, we have completely matched the prefix and so return True
[] -> True
)
null -- Innermost nested function - we need to make sure that if the prefix reaches here, it is null, i.e. we have entirely matched it
s
And now we use this function isPrefixOfS on p:
p `isPrefixOf` s = isPrefixOfS p
EDIT: I just found this post which uses a similar logic to implement zip in terms of foldr, you may want to look at that as well.
