What I ended up writing (not cleaned up at all, and not exactly solving the problem posed; CRAPLed <http://matt.might.net/articles/crapl/>, if you will) can be found here: http://lpaste.net/104155
I used a monadic fold and the Writer monad, though looking back on it, I feel like Pipes would be a natural fit. I'm keeping a buffer just big enough to know what to output at each step in the consumption of the list. One problem I had was that I misremembered how scan works; for some reason I thought that `scan list` was `tails` and not `inits`. On Wed, May 14, 2014 at 7:50 PM, Gabriel Gonzalez <[email protected]>wrote: > Actually, there's not a good way to do this using `Foldl` because the > fold does not have access to elements ahead of it in the stream. > > However, there's a pretty simple solution in terms of ordinary list > functions: > > import Data.List (tails) > > > takeInteresting :: Int -> (a -> Bool) -> [a] -> [a] > takeInteresting n pred = go n > where > -- go :: Int -> [a] -> [a] > go n as = > if n <= 0 > then [] > else let (prefix , suffix ) = break pred as > (prefix', suffix') = case suffix of > [] -> (prefix, suffix) > s:uffix -> (prefix ++ [s], uffix) > in prefix' ++ go (n - 1) suffix' > > scanInteresting :: Int -> (a -> Bool) -> [a] -> [[a]] > scanInteresting n pred = map (takeInteresting n pred) . tails > > Here's an example usage: > > >>> scanInteresting 2 (== 0) [1, 2, 0, 3, 4, 0, 5, 6, 0] > > [[1,2,0,3,4,0],[2,0,3,4,0],[0,3,4,0],[3,4,0,5,6,0],[4,0,5,6,0],[0,5,6,0],[5,6,0],[6,0],[0],[]] > > > > On 5/11/14, 9:40 AM, Alex Rozenshteyn wrote: > > Only tangentially related, but still, close enough that I feel like > it's a follow-up, and tricky enough that I feel like I should ask someone > else. > > This is a Foldl question, so if there's a better place to ask it, please > let me know. > > Some context, which can mostly be safely ignored, but I'm providing for > motivation in case my explanation is not clear: > > I'm trying to make Anki flashcards to memorize "The Love Song of J. > Alfred Prufrock". My input format is the text of the poem (slightly > preprocessed), and my output formate is a newline separated file with some > formatting on each line. Each line defines a flashcard with a hole (a cloze > deletion). I would like sufficient context; in this case, it's 5 lines or > to the beginning of the stanza, whichever is longer. > > </context> > > What I want to write is a variant on a take function that takes the first > n "interesting" elements and any uninteresting ones interspersed; that is > > takeInteresting :: Int -> (a -> Bool) -> [a] -> [a] > > such that > > length . filter p . takeInteresting n p == n > isPrefixOf (takeInteresting n p xs) xs > > If I understand correctly, I can write this as a fold and then use a scan > to apply it at every starting point. > > My question is how best to write this fold. > > My ad-hoc approach was to use a decorate-doStuff-undecorate pattern where > I would count the number of interesting elements, but it wasn't very > compositional; I expect there's a better approach. > > Thank you. > > > On Thu, Mar 6, 2014 at 12:43 AM, Gabriel Gonzalez <[email protected]>wrote: > >> The trick is to combine `pipes` with the `foldl` library. In fact, >> given any `Fold`, you can convert it into a scanning pipe like this: >> >> convert :: Monad m => Fold a b -> Pipe a b m r >> convert = Control.Foldl.purely Pipes.Prelude.scan >> >> So now you have a smaller problem: write a fold for a moving average of a >> stream of numbers. It turns out that there is a nice way to do this in >> O(1) space if you do an exponential moving average: >> >> http://lpaste.net/100765 >> >> You can also do an ordinary moving average, too, but that requires O(N) >> space (where N is the window size). It basically involves storing the last >> N elements as the fold's internal state. >> >> The `foldl` library is easy to learn. Just read the module header here >> and the documentation for the `Fold` type: >> >> http://hackage.haskell.org/package/foldl-1.0.2/docs/Control-Foldl.html >> >> Now, technically, you could do all of this without using the `foldl` >> library at all, just by passing the folding logic directly to >> `Pipes.Prelude.scan`, but by using `foldl` you make it really easy to add >> additional metrics to your `Fold` while still passing over the data just >> once. >> >> >> On 3/5/2014 8:01 AM, Alex Rozenshteyn wrote: >> >> I feel like I must be missing something rather basic, but I have been >> trying to figure out how to use pipes to compute a moving average of a >> stream of numbers. I've written code to do the EWMA, but I can't figure out >> how to do the sliding window. It doesn't help that I'm a bit of a pipes >> beginner. >> >> Advice is welcome and appreciated. >> >> Thank you. >> -- >> You received this message because you are subscribed to the Google >> Groups "Haskell Pipes" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> >> To post to this group, send email to [email protected]. >> >> >> > > > -- > Alex R > > > -- Alex R -- You received this message because you are subscribed to the Google Groups "Haskell Pipes" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected].
