[Haskell-cafe] Am I doing it right?

Luke Palmer lrpalmer at gmail.com
Wed Sep 24 15:16:22 EDT 2008


On Wed, Sep 24, 2008 at 1:14 PM, Creighton Hogg <wchogg at gmail.com> wrote:
> Hi Haskellers,
> So as another step in my education, I wanted to ask if the following
> code at least feels 'morally' correct as a find/replace function,
> replacing each occurrence of the sub-list before with after in the
> list.  unfoldr felt like the most natural higher order function to
> capture the recursion, but I imagine there are still slicker ways to
> have done this because I am creating an intermediate list-of-lists.
> However, doing it this way seems at least moderately speedy given that
> I was able to read in, find/replace, and write out a 120 MB file in 30
> seconds on a fairly dinky linux box.
>
> replace :: (Eq a) => [a] -> [a] -> [a] -> [a]
> replace before after = concat . unfoldr aux
>     where aux [] = Nothing
>               aux str | take l str == before = Just (after,drop l str)
>                           | otherwise = Just (take 1 str,drop 1 str)
>               l = length before

Yeah, this code is pretty nice.  concat is a foldr, so you have an
elegant foldr . unfoldr at the top.  IIRC foldr . unfoldr fuses, so
you get efficiency that way.

"take l str == before" is also known as "before `isPrefixOf` str",
just to be slightly more idiomatic.

This algorithm is quite inefficient, O(nm).  There is probably a more
efficient one that still only relies on Eq, I am not certain though.€€

Luke


More information about the Haskell-Cafe mailing list