operations on lists with continuations
I have a few functions for operating on lists that take continuations: -- | Like takeWhile but with a continuation, so you can chain takes without -- copying. takeWhileThen :: (a -> Bool) -> ([a] -> [a]) -> [a] -> [a] takeWhileThen _ _ [] = [] takeWhileThen f cont (x:xs) | f x = x : takeWhileThen f cont xs | otherwise = cont (x:xs) But of course this isn't enough, then I start wanting a takeThen. And then a filterThen. That makes me think plain explicit recursion would be clearer, but the problem I have with that is that it has an imperative feel. What I mean by that is that the result is a product of the changing state of the recursing function, and it's non-composable. E.g. filterUntil start end msgs = go where go [] = [] go (m:ms) | msg_start m >= start = takeWhile ((<end) . msg_start) (m : ms) | condition m = m : go ms | otherwise = go ms Whereas with filterThen I can write: filterUntil start end = filterThen condition ((>=start) . msg_start) . takeWhile ((<end) . msg_start) This looks much more functional to me, and can be composed: filterUntilPlus1 start end = filterThen condition ((>=start) . msg_start) $ takeWhileThen ((<end) . msg_start) $ take 1 So my question is, am I about to discover this already exists in the Prelude, or is unnecessary because of something I'm overlooking? I imagine it must be a special case of some kind of generalization, right? Surely someone has thought of this and taken it much further than I have. I suppose this starts to look like maybe a CPS version of a parser... but it seems lighter-weight for simple tasks.
Maybe you've invented the ApoPrelude? If I were doing it I'd probably code them in terms of an apomorphism - unfoldr with flush. Unlike regular unfoldr which discards the final state, an apomorphism uses the final state to produce the tail of the output list. See Jeremy Gibbons paper "Streaming representation-changers" section 4.4. http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/
On Wed, Mar 2, 2011 at 12:00 AM, Stephen Tetley <stephen.tetley@gmail.com> wrote:
Maybe you've invented the ApoPrelude?
If I were doing it I'd probably code them in terms of an apomorphism - unfoldr with flush. Unlike regular unfoldr which discards the final state, an apomorphism uses the final state to produce the tail of the output list. See Jeremy Gibbons paper "Streaming representation-changers" section 4.4.
Interesting, thanks for the link. Indeed it looks like a special case of a general concept someone has already gotten a fair bit of milage out of :)
To make up for my total misunderstanding of what you were asking before, I hereby offer you the Plumbing module, available here: https://bitbucket.org/mtnviewmark/haskell-playground/src/2d022b576c4e/Plumbi... With it, I think you can construct the kinds of pipelines you describe with the composition aspects you desire:
:load Plumbing.hs [1 of 1] Compiling Plumbing ( Plumbing.hs, interpreted ) Ok, modules loaded: Plumbing. let filterUntil cond start end = (passUntil (>=start) =|= pfilter cond) =+= passWhile (<end) let filterUntilPlus1 cond start end = filterUntil cond start end =+= pass 1 filterUntil even 10 15 `pump` [1..] [2,4,6,8,10,11,12,13,14] filterUntilPlus1 even 10 15 `pump` [1..] [2,4,6,8,10,11,12,13,14,15]
- Mark
On Thu, Mar 3, 2011 at 12:33 AM, Mark Lentczner <mark.lentczner@gmail.com> wrote:
To make up for my total misunderstanding of what you were asking before, I hereby offer you the Plumbing module, available here: https://bitbucket.org/mtnviewmark/haskell-playground/src/2d022b576c4e/Plumbi...
With it, I think you can construct the kinds of pipelines you describe with the composition aspects you desire:
Indeed, it looks like a more thorough version of what I'm doing. I'm guessing the breaking into pairs thing would be ultimately more composable, by which I mean lead to fewer special case functions.
:load Plumbing.hs [1 of 1] Compiling Plumbing ( Plumbing.hs, interpreted ) Ok, modules loaded: Plumbing. let filterUntil cond start end = (passUntil (>=start) =|= pfilter cond) =+= passWhile (<end) let filterUntilPlus1 cond start end = filterUntil cond start end =+= pass 1 filterUntil even 10 15 `pump` [1..] [2,4,6,8,10,11,12,13,14] filterUntilPlus1 even 10 15 `pump` [1..] [2,4,6,8,10,11,12,13,14,15]
I would write the above as:
let filterUntilPlus1 cond start end = Then.filter cond (>=start) $ Then.takeWhile (<end) $ take 1 filterUntilPlus1 even 10 15 [1..] [2,4,6,8,10,11,12,13,14,15]
I think mine is less flexible but it interacts with the basic list functions more directly so it feels simpler to me. In a way it reminds me of STM, in that as long as you leave the last continuation on, it's still "open" and can be composed. But to get the actual result, you have to stick a non-continuation function on the end, at which point it no longer composes. I suppose that's the model for many many little DSLs though.
participants (3)
-
Evan Laforge -
Mark Lentczner -
Stephen Tetley