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] <mailto:[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]
<mailto:[email protected]>.
To post to this group, send email to
[email protected]
<mailto:[email protected]>.
--
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].
