Hi, Yet another "Function looking for a name" post. Here's the type:
morph :: ([a] -> Maybe (b,[a])) -> (b -> [a]) -> [a] -> [a]
Here, I am calling ([a] -> Maybe (b,[a])) the 'selector'. It is actually the same type as a simple parser. I am calling (b -> [a]) the 'transformer'. Once you've chosen your selector and transformer, it's a stream processing function [a] -> [a]. The idea is that the 'selector' looks at the front of the stream and decides if it matches some predicate. (Not necessarily just based on only the first element, though). If it does not, it will return Nothing and that element is passed through unchanged. If it matches then it produces (parses) some representation or calculation 'b'. The transformer is then responsible to transforming this 'b' back into a list of as to be spliced back into the stream. So morph is a general stream manipulation combinator. Let me give some examples: * Replace all strings of odd numbers by (just one occurence of) the number 0 *Main> morph (sAll odd) (const [0]) [1,3,2,3,4,4,3,1,5] [0,2,0,4,4,0] * Add one to all even numbers *Main> morph (sAll even) (map (+1)) [1,3,2,3,4,4,3,1,5] [1,3,3,3,5,5,3,1,5] Here "sAll" is the very simply defined:
sAll p l@(x:xs) | p x = Just (span p l) | otherwise = Nothing
* simple string replacement *Main> morph (sMatch "fox") (const "ferret") "the quick brown fox jumped over the lazy dog" "the quick brown ferret jumped over the lazy dog" * string match + modify *Main Data.Char> morph (sMatch "fox") (("'"++).(++"'").reverse . map toUpper) "the quick brown fox jumped over the lazy dog" "the quick brown 'XOF' jumped over the lazy dog" ...in the above two examples, sMatch is defined as:
sMatch a l | a `isPrefixOf` l = Just (a,drop (length a) l) | otherwise = Nothing
I'm fairly sure that the active hive-mind of haskell-cafe will be able to think of many more uses of this function. I actually wrote it to do HTML fix-up, working with the TagSoup library. A few quick definitions and it becomes easy to express things like 'remove all FONT, BR and U tags; replace all instances of B with SPAN CLASS="important"...'; the task of repairing broken HTML and replacing simplistic markup with semantic markup. It's very powerful to have the separation between selection and transformation; it's quite easy to build up powerful libraries of selectors and use them with simple transformers. Here is the definition of morph:
morph sel trans [] = [] morph sel trans l@(x:xs) = case sel l of Nothing -> x : morph sel trans xs Just (b,xs') -> trans b ++ morph sel trans xs'
I've written it to run over lists, but it would not be difficult to make it run over ByteStrings instead, and exploit the 'no-copying' effect on the bits of the stream which were not modified, which would be very handy for programs processing large bytestrings. It could be used for a streaming filter, for example; although care must be taken. A composition of 'morphs' will 'read-ahead' as far as its most greedy selector, so if did want it to stream, you'd have to make sure that your selectors don't read ahead indefinitely (like an XML selector waiting for a closing tag would). There is a close cousin which is fully recursive and not guaranteed to terminate, where you call 'morph' again on the "trans b" part, which I've been calling 'rmorph'. You need it if you want to, for example, remove all correctly nested <FONT>...</FONT> tags. (Although you wouldn't need it if you forgot about nesting, which is arguably more sane for that particular case). Has anyone spotted this function or a close analogue elsewhere in the haskell canon? Does anyone have a better name for it that 'morph'? Jules