Safe looping - keep tab on the lookahead in a Pipe? #10

Closed
alexanderkjeldaas opened this Issue Mar 22, 2012 · 2 comments

Comments

Projects
None yet
2 participants

Below, I'm using the <+> combinator that you implemented in Issue #9

I wonder if it would be possible to ensure that loops work in the type system.
Below are some examples of simple loops. Without the 'yield 0', it doesn't work of course, but in a larger system, keeping tabs of this when using <+> etc. can be difficult.

Is there a solution to this?

counter = runPipe $ printer <+< net
  where
    adder = yield 0 >> (forever $ do
        x <- await
        yield (x + 1))
    net = fromList [1..10] <+> (adder <+< net)

counter2 = runPipe $ printer <+< net
  where
    adder = yield 0 >> (forever $ do
        x <- await
        yield (x + 1))
    net = adder <+< net
Owner

Gabriel439 commented Mar 22, 2012

It doesn't work because <+> assumes the streams are sorted, but in your
example they aren't necessarily sorted. I used the following
modification to your code to show this

take' n = replicateM_ n $ await >>= yield

adder = yield 100 >> pipe (+1)

net = fromList [1..3] <+> (adder <+< net)

Main*> runPipe $ printer <+< take' 20 <+< net
1
2
3
100
2
3
4
101
3
4
5
102
4
5
6
103
5
6
7
104

In the above example, the merge failed because "adder <+< net" wasn't
sorted. So the answer to your question is that there would have to be a
way to specify at the type level that the streams are sorted in order to
enforce the invariant that merging requires. Right now there is no way
to do this in pipes, or even in ordinary lists as far as I can tell.

This is actually an interesting question, because you could imagine for
just ordinary lists designing such a type-level encoding of the sorted
invariant. In other words, you'd have an API like:

newtype Sorted a = Sorted [a] -- constructor not exposed

-- The only exposed way to construct a "Sorted a" type from a list
sort' :: (Ord a) => [a] -> Sorted a
sort' = Sorted . sort

(<+>) :: Sorted a -> Sorted a -> Sorted a
(<+>) = ... -- conventional merge for sorted lists

toList :: Sorted a -> [a]
toList (Sorted xs) = xs

So yeah, I could conceivably implement something similar in pipes along
those lines, however, I'm surprised that something similar hasn't been
done for lists. The fact that there seems to be such little demand for
a type-level sorted invariant for ordinary lists makes me wonder if it's
an important feature or if I'm missing some obvious flaw in my above
mock API.

On 03/22/2012 03:10 AM, alexanderkjeldaas wrote:

Below, I'm using the<+> combinator that you implemented in Issue #9

I wonder if it would be possible to ensure that loops work in the type system.
Below are some examples of simple loops. Without the 'yield 0', it doesn't work of course, but in a larger system, keeping tabs of this when using<+> etc. can be difficult.

Is there a solution to this?

counter = runPipe $ printer<+<  net
   where
     adder = yield 0>>  (forever $ do
         x<- await
         yield (x + 1))
     net = fromList [1..10]<+>  (adder<+<  net)

counter2 = runPipe $ printer<+<  net
   where
     adder = yield 0>>  (forever $ do
         x<- await
         yield (x + 1))
     net = adder<+<  net

Reply to this email directly or view it on GitHub:
#10

Owner

Gabriel439 commented Dec 12, 2012

I will go ahead and close this old issue since you haven't replied. The issue was mostly outside of the scope of this library and consisted primarily of ensuring that the input lists were sorted, since your merge algorithm assumed they were sorted.

You can always open a new issue if you have more questions.

@Gabriel439 Gabriel439 closed this Dec 12, 2012

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment