3 ms·

You could decompose removeIfNot a bit further by representing the intermediate stages as pairs of lists (result + unprocessed input): import Data.Bifunctor

You could decompose removeIfNot a bit further by representing the intermediate stages as pairs of lists (result + unprocessed input): import Data.Bifunctor (bimap, first) type Split a = ([a], [a]) unsplit :: Split a -> [a] unsplit = uncurry (++) splitStart :: [a] -> Split a splitStart xs = ([], xs) skip :: Int -> Split a -> Split a skip n (xs, ys) = first (xs ++) (splitAt n ys) iterateN :: Int -> (a -> a) -> a -> a iterateN n f = (!! n) . iterate f removeOneIfNot :: (a -> Bool) -> Split a -> Split a removeOneIfNot p (xs, ys) = bimap (xs ++) (drop 1) (span p ys) GHCI> unsplit . iterateN 3 (removeOneIfNot even) . skip 5 . splitStart $ [1..15] [1,2,3,4,5,6,8,10,12,13,14,15]

dllthomas 6y ago
Very nice! I had a bit of trouble convincing myself that it has the laziness I'd want out of it, but by experimentation it seems to. Still, definitely a more complicated decomposition than that described in the article (but maybe a more interesting article!)
- nybble41 6y ago
  With one more combinator we can decompose this slightly further: stepSplit :: ([a] -> Split a) -> Split a -> Split a stepSplit f = uncurry first . bimap (++) f skip n = stepSplit (splitAt n) removeOneIfNot p = stepSplit (second (drop 1) . span p) Or in perhaps-more-familiar monadic terms: import Control.Monad (replicateM_) import Control.Monad.Trans (lift) import Control.Monad.Trans.State (StateT, evalStateT, state, get) import Control.Monad.Trans.Writer (WriterT, execWriterT, tell) import Data.Bifunctor (second) import Data.Functor.Identity (Identity, runIdentity) type SplitterT b m = WriterT [b] (StateT [b] m) type Splitter b = SplitterT b Identity splitter :: Monad m => ([b] -> ([b], [b])) -> SplitterT b m () splitter f = lift (state f) >>= tell execSplitterT :: Monad m => SplitterT b m a -> [b] -> m [b] execSplitterT m = evalStateT (execWriterT (m >> lift get >>= tell)) execSplitter :: Splitter b a -> [b] -> [b] execSplitter m = runIdentity . execSplitterT m skip :: Monad m => Int -> SplitterT b m () skip n = splitter (splitAt n) removeOneIfNot :: Monad m => (b -> Bool) -> SplitterT b m () removeOneIfNot p = splitter (second (drop 1) . span p) GHCI> execSplitter (skip 5 >> replicateM_ 3 (removeOneIfNot even)) [1..15] [1,2,3,4,5,6,8,10,12,13,14,15] It's hard to say which version is clearer. It probably depends on what you're used to. The code is essentially the same under the Writer/State abstraction, with `execSplitter` replacing both `unsplit` and `splitStart` and monadic bind in place of function composition. The `Splitter b ()` type is isomorphic to the `[b] -> ([b], [b])` used for the argument to `stepSplit` in the first version.
  - dllthomas 6y ago
    "Whatever happened to the Popular Front, Reg?"

dllthomas 6y ago

Very nice! I had a bit of trouble convincing myself that it has the laziness I'd want out of it, but by experimentation it seems to. Still, definitely a more complicated decomposition than that described in the article (but maybe a more interesting article!)

nybble41 6y ago
With one more combinator we can decompose this slightly further: stepSplit :: ([a] -> Split a) -> Split a -> Split a stepSplit f = uncurry first . bimap (++) f skip n = stepSplit (splitAt n) removeOneIfNot p = stepSplit (second (drop 1) . span p) Or in perhaps-more-familiar monadic terms: import Control.Monad (replicateM_) import Control.Monad.Trans (lift) import Control.Monad.Trans.State (StateT, evalStateT, state, get) import Control.Monad.Trans.Writer (WriterT, execWriterT, tell) import Data.Bifunctor (second) import Data.Functor.Identity (Identity, runIdentity) type SplitterT b m = WriterT [b] (StateT [b] m) type Splitter b = SplitterT b Identity splitter :: Monad m => ([b] -> ([b], [b])) -> SplitterT b m () splitter f = lift (state f) >>= tell execSplitterT :: Monad m => SplitterT b m a -> [b] -> m [b] execSplitterT m = evalStateT (execWriterT (m >> lift get >>= tell)) execSplitter :: Splitter b a -> [b] -> [b] execSplitter m = runIdentity . execSplitterT m skip :: Monad m => Int -> SplitterT b m () skip n = splitter (splitAt n) removeOneIfNot :: Monad m => (b -> Bool) -> SplitterT b m () removeOneIfNot p = splitter (second (drop 1) . span p) GHCI> execSplitter (skip 5 >> replicateM_ 3 (removeOneIfNot even)) [1..15] [1,2,3,4,5,6,8,10,12,13,14,15] It's hard to say which version is clearer. It probably depends on what you're used to. The code is essentially the same under the Writer/State abstraction, with `execSplitter` replacing both `unsplit` and `splitStart` and monadic bind in place of function composition. The `Splitter b ()` type is isomorphic to the `[b] -> ([b], [b])` used for the argument to `stepSplit` in the first version.
- dllthomas 6y ago
  "Whatever happened to the Popular Front, Reg?"