On Wed, Sep 24, 2008 at 1:14 PM, Creighton Hogg <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
