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] <mailto:[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] <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
--
Alex R
