my top-level description technique failed me

Submitted by metaperl on Tue, 08/09/2005 - 7:18pm.

I was trying to work problem 7.26 in Simon Thompson's "Craft of Functional Programming":

given a STRING search for SEARCH and replace with REPLACE

Now, having fallen in love with the ability to give top-down specs for things in Haskell, I tried this for starters:

substr search replace input = pre ++ sub ++ post

meaning given an input string, we have the unaltered pre and post parts and a conditionally altered sub part.

But I could not take this top-down description further without searching the string numerous times. John Goerzen was nice enough to come up with this solution for me:


I'd recurse over the string, dropping the first character on
each recursion
then I'd compare the first (length search) characters to (search)
If they're the same, I'd return (replace ++ xs)
otherwise return x:self xs


subst search@(s:ss) replace input@(i:is)
| chunkSearch search input = replace ++ (drop (length search) input)
| otherwise = i : subst search replace is

-- presumes length a < length b
chunkSearch a b = a == take (length a) b

Well, I like this solution, but I'm a bit worried that my top-down approach fell through on me. It's interesting how he simply builds the pre part on the fly and then pastes the post part in with replace

Submitted by saggmannen (not verified) on Wed, 08/10/2005 - 3:45am.

If you wish all instances of the substring replaced, slightly modify the append:
++ subst(search replace (drop (length search) input))
Also, why the (s:ss) pattern match?

Submitted by metaperl on Wed, 08/10/2005 - 8:31pm.

thanks for the input on global search and replace!

and yes, the (s:ss) is un-needed.

Submitted by dtlin on Wed, 09/07/2005 - 11:08am.

chunkSearch a b = and $ zipWith (==) a b  -- does not impose any requirements on the length of a and b, only that they're not both infinite ;-)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.