Exercise of "Programming with Arrows"

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Exercise of "Programming with Arrows"

Thiago Negri
The paper "Programming with Arrows" of John Hughes gives some exercises to
do [1].
I'm trying to solve it and would like to receive a feedback if I'm doing it
right or not before reading the rest of the paper.
I didn't find the answers in the internet (if someone could point me to it,
please do so).

Exercise 2 (section 2.5) is asking to create a Stream Processor that can
map more than one output per input (e.g. 3 outcomes for a single consume of
the stream).

The paper says that implementing "first" will be tricky, and it really is.
I've came up to the solution listed below, *is it right?*
*
*
*
*
module SP where

import Prelude hiding (id, (.))
import Control.Category
import Control.Arrow

data SP a b = Put b (SP a b) | Get (a -> SP a b)

runSP :: SP a b -> [a] -> [b]
runSP (Put b s) as = b:runSP s as
runSP (Get k) (a:as) = runSP (k a) as
runSP (Get k) [] = []

compose :: SP b c -> SP a b -> SP a c
compose (Put a s) g = Put a (compose s g)
compose (Get k) (Put a s) = compose (k a) s
compose f (Get k) = Get (\a -> compose f (k a))

instance Category SP where
  id = arr id
  (.) = compose

instance Arrow SP where
  arr f = Get (\a -> Put (f a) (arr f))
  first (Put a s) = Get (\(a', c) -> Put (a, c) (delayed (a', c) s))
  first (Get k) = Get (\(a, c) -> firstWithValue (k a) c)

delayed :: (a, c) -> SP a b -> SP (a, c) (b, c)
delayed (a, c) (Put b s) = Put (b, c) (delayed (a, c) s)
delayed (a, c) (Get k) = firstWithValue (k a) c

firstWithValue :: SP a b -> c -> SP (a, c) (b, c)
firstWithValue (Put a s) c = Put (a, c) (firstWithValue s c)
firstWithValue (Get k) _ = Get (\(a, c) -> firstWithValue (k a) c)

input :: [(String, String)]
input = [("a1", "a2"), ("b1", "b2"), ("c1", "c2"), ("d1", "d2")]

myArrow :: SP (String, String) (String, String)
myArrow = (delay "db1" >>> delay "da1") *** (delay "db2" >>> delay "da2")

delay :: a -> SP a a
delay b = Put b (arr id)

main :: IO ()
main = let output = runSP myArrow input in mapM_ f output
  where f (a, b) = putStrLn $ "(" ++ show a ++ ", " ++ show b ++ ")"
*
*

The output of "main" is:


*SP> main
("da1", "da2")
("da1", "db2")
("da1", "a2")
("db1", "a2")
("a1", "a2")
("b1", "b2")
("c1", "c2")
("d1", "d2")


[1] http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20131007/61bb8ad6/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Exercise of "Programming with Arrows"

Kim-Ee Yeoh
Administrator
Hey Thiago,

First of all, congratulations for reading Hughes! Many of his papers are
worth reading and re-reading for both beginners and experts alike.

On Tue, Oct 8, 2013 at 12:05 AM, Thiago Negri <evohunz at gmail.com> wrote:

> Exercise 2 (section 2.5) is asking to create a Stream Processor that can
> map more than one output per input (e.g. 3 outcomes for a single consume of
> the stream).


Given

> data SP a b = Put b (SP a b) | Get (a -> SP a b)

it's easy to see that it's not just about more than one output per input.
It's about n pieces of input producing m pieces of output, where (n,m) may
even -- and probably does -- depend on previous inputs!

The exercise asks for an implementation of the following Arrow instance:

> first :: arr a b -> arr (a,c) (b,c)

which, specialized to our case, is just SP a b -> SP (a,c) (b,c).

It should now be apparent what the 'trickiness' is. On the one hand,
indeterminate a's need to be fed in before indeterminate b's get pulled
out. On the other hand, the c's need to behave as if they were in a no-op
assembly line. One c goes in, the one (and same!) c drops out.

So one way to look at this is as a buffering problem.

At this point, I'd encourage you to think of some quickcheck tests you can
write to convince yourself whether you have a right implementation or not.

Your main function doesn't seem adequate for the task.

-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20131008/bcabcbec/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Exercise of "Programming with Arrows"

Thiago Negri
"On the one hand, indeterminate a's need to be fed in before indeterminate
b's get pulled out. On the other hand, the c's need to behave as if they
were in a no-op assembly line. One c goes in, the one (and same!) c drops
out."

I agree with "no-op assembly line", but when I'm using `first` on a
processor, I want to process the first stream *only*. The second stream
should remain as it was not touched, so future processors will receive the
same sequence from the second stream.

I mean, I think I need to guarantee that this definition holds:

`g *** f` is the same as `first g >>> swap >>> first f >>> swap`

If my implementation of `first` uses a real no-op assembly line for `c`
(i.e., `arr id`), then I would lose the stream. As you said, I need to
buffer the second stream while processing the first one.

Is my line of tought correct?

I'll try to write some tests to verify this.

Thanks!


2013/10/7 Kim-Ee Yeoh <ky3 at atamo.com>

> Hey Thiago,
>
> First of all, congratulations for reading Hughes! Many of his papers are
> worth reading and re-reading for both beginners and experts alike.
>
>
> On Tue, Oct 8, 2013 at 12:05 AM, Thiago Negri <evohunz at gmail.com> wrote:
>
>> Exercise 2 (section 2.5) is asking to create a Stream Processor that can
>> map more than one output per input (e.g. 3 outcomes for a single consume of
>> the stream).
>
>
> Given
>
>
> > data SP a b = Put b (SP a b) | Get (a -> SP a b)
>
> it's easy to see that it's not just about more than one output per input.
> It's about n pieces of input producing m pieces of output, where (n,m) may
> even -- and probably does -- depend on previous inputs!
>
> The exercise asks for an implementation of the following Arrow instance:
>
> > first :: arr a b -> arr (a,c) (b,c)
>
> which, specialized to our case, is just SP a b -> SP (a,c) (b,c).
>
> It should now be apparent what the 'trickiness' is. On the one hand,
> indeterminate a's need to be fed in before indeterminate b's get pulled
> out. On the other hand, the c's need to behave as if they were in a no-op
> assembly line. One c goes in, the one (and same!) c drops out.
>
> So one way to look at this is as a buffering problem.
>
> At this point, I'd encourage you to think of some quickcheck tests you can
> write to convince yourself whether you have a right implementation or not.
>
> Your main function doesn't seem adequate for the task.
>
> -- Kim-Ee
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20131007/1c874cb6/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Exercise of "Programming with Arrows"

Thiago Negri
This is my first contact with QuickCheck, but does this test count as a
proof that my implementation is correct?

QuickCheck shows 100 tests passed.

prop_a xs = runSP (f *** g) xs == runSP (first f >>> swap >>> first g >>>
swap) xs
  where swap = arr (\(a,b) -> (b,a))
        f = arr (++"a")
        g = arr (++"b")



2013/10/7 Thiago Negri <evohunz at gmail.com>

> "On the one hand, indeterminate a's need to be fed in before
> indeterminate b's get pulled out. On the other hand, the c's need to behave
> as if they were in a no-op assembly line. One c goes in, the one (and
> same!) c drops out."
>
> I agree with "no-op assembly line", but when I'm using `first` on a
> processor, I want to process the first stream *only*. The second stream
> should remain as it was not touched, so future processors will receive the
> same sequence from the second stream.
>
> I mean, I think I need to guarantee that this definition holds:
>
> `g *** f` is the same as `first g >>> swap >>> first f >>> swap`
>
> If my implementation of `first` uses a real no-op assembly line for `c`
> (i.e., `arr id`), then I would lose the stream. As you said, I need to
> buffer the second stream while processing the first one.
>
> Is my line of tought correct?
>
> I'll try to write some tests to verify this.
>
> Thanks!
>
>
> 2013/10/7 Kim-Ee Yeoh <ky3 at atamo.com>
>
>> Hey Thiago,
>>
>> First of all, congratulations for reading Hughes! Many of his papers are
>> worth reading and re-reading for both beginners and experts alike.
>>
>>
>> On Tue, Oct 8, 2013 at 12:05 AM, Thiago Negri <evohunz at gmail.com> wrote:
>>
>>> Exercise 2 (section 2.5) is asking to create a Stream Processor that can
>>> map more than one output per input (e.g. 3 outcomes for a single consume of
>>> the stream).
>>
>>
>> Given
>>
>>
>> > data SP a b = Put b (SP a b) | Get (a -> SP a b)
>>
>> it's easy to see that it's not just about more than one output per input.
>> It's about n pieces of input producing m pieces of output, where (n,m) may
>> even -- and probably does -- depend on previous inputs!
>>
>> The exercise asks for an implementation of the following Arrow instance:
>>
>> > first :: arr a b -> arr (a,c) (b,c)
>>
>> which, specialized to our case, is just SP a b -> SP (a,c) (b,c).
>>
>> It should now be apparent what the 'trickiness' is. On the one hand,
>> indeterminate a's need to be fed in before indeterminate b's get pulled
>> out. On the other hand, the c's need to behave as if they were in a no-op
>> assembly line. One c goes in, the one (and same!) c drops out.
>>
>> So one way to look at this is as a buffering problem.
>>
>> At this point, I'd encourage you to think of some quickcheck tests you
>> can write to convince yourself whether you have a right implementation or
>> not.
>>
>> Your main function doesn't seem adequate for the task.
>>
>> -- Kim-Ee
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20131007/0e01fc03/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Exercise of "Programming with Arrows"

Thiago Negri
I think I'm starting to get the "way of arrows".

My implementation was incorrect. I've seen it with the hand made test
listed below [1].
The output of "first arrA" and "first arrB" should be joined together and
form a new stream with the length of the shortest output of both ("arrA ***
arrB"), and this wasn't happening.

I've found package "streamproc" at Hackage and that gave me some insights.
Yet I think "streamproc" is also wrong, as it does not buffer the second
stream.
You can check it at line 58 of SP.hs [3] that it ignores the first element
of the pair.
But I didn't write a test to check what is the implication of this, I'll
try to do this as a next step into understanding arrows.

That exercise really helped me!

My new implementation, wich I think is correct now, is listed below [2].

Thanks!

Thiago


[1]:
inputA :: [String]
inputA = ["a", "b", "hello", "c", "d", "e", "hello", "f", "g", "e", "x"]

arrA :: SP String String
arrA = Get (\a -> if a == "hello" then (Put a (Put "world" arrA))
                                  else (Put "unknown" arrA))

arrB :: SP String String
arrB = Get (\a -> if a == "my" then (Get (\a -> if a == "name" then (Get
(\a -> if a == "is" then Get (\a -> Put ("name: " ++ a) arrB)

                 else arrB))
                                                               else arrB))
                               else arrB)

inputB :: [String]
inputB = ["a", "b", "my", "name", "is", "thiago", "and", "I", "am", "so",
"cool"]

inputAB :: [(String, String)]
inputAB = zip inputA inputB

main :: IO ()
main = let actualOutputB = runSP arrB inputB
           actualOutputB1 = runSP (first arrB) (zip inputB (repeat "a"))
           actualOutputA = runSP arrA inputA
           actualOutputA1 = runSP (first arrA) (zip inputA (repeat "a"))
           actualOutputAB = runSP (arrA *** arrB) inputAB
       in do putStrLn $ "inputAB: " ++ show inputAB
             putStrLn $ "outputA: " ++ show actualOutputA
             putStrLn $ "outputA1: " ++ show actualOutputA1
             putStrLn $ "outputB: " ++ show actualOutputB
             putStrLn $ "outputB1: " ++ show actualOutputB1
             putStrLn $ "outputAB: " ++ show actualOutputAB



[2]:
module SP where

import Prelude hiding (id, (.))
import Control.Category
import Control.Arrow
import Test.QuickCheck

data SP a b = Put b (SP a b) | Get (a -> SP a b)

runSP :: SP a b -> [a] -> [b]
runSP (Put b s) as = b:runSP s as
runSP (Get k) (a:as) = runSP (k a) as
runSP (Get k) [] = []

compose :: SP b c -> SP a b -> SP a c
compose (Put a s) g = Put a (compose s g)
compose (Get k) (Put a s) = compose (k a) s
compose f (Get k) = Get (\a -> compose f (k a))

instance Category SP where
  id = arr id
  (.) = compose

instance Arrow SP where
  arr f = Get (\a -> Put (f a) (arr f))
  first = queued empty empty

queued :: Queue a -> Queue c -> SP a b -> SP (a, c) (b, c)
queued qa qc (Put a s) = case pop qc of Nothing -> Get (\(a', c) -> Put (a,
c) (queued (push a' qa) qc s))
                                        Just (c, qc') -> Put (a, c) (queued
qa qc' s)
queued qa qc (Get k) = case pop qa of Nothing -> Get (\(a, c) -> queued qa
(push c qc) (k a))
                                      Just (a, qa') -> queued qa' qc (k a)

data Queue a = Queue [a]

empty :: Queue a
empty = Queue []

push :: a -> Queue a -> Queue a
push a (Queue as) = Queue (a:as)

pop :: Queue a -> Maybe (a, Queue a)
pop (Queue []) = Nothing
pop (Queue (a:as)) = Just (a, Queue as)

delayed :: (a, c) -> SP a b -> SP (a, c) (b, c)
delayed (a, c) (Put b s) = Put (b, c) (delayed (a, c) s)
delayed (a, c) (Get k) = firstWithValue (k a) c

firstWithValue :: SP a b -> c -> SP (a, c) (b, c)
firstWithValue (Put a s) c = Put (a, c) (firstWithValue s c)
firstWithValue (Get k) _ = Get (\(a, c) -> firstWithValue (k a) c)

input :: [(String, String)]
input = [("a1", "a2"), ("b1", "b2"), ("c1", "c2"), ("d1", "d2")]

myArrow :: SP (String, String) (String, String)
myArrow = (delay "db1" >>> delay "da1") *** (delay "db2" >>> delay "da2")

delay :: a -> SP a a
delay b = Put b (arr id)

inputA :: [String]
inputA = ["a", "b", "hello", "c", "d", "e", "hello", "f", "g", "e", "x"]

arrA :: SP String String
arrA = Get (\a -> if a == "hello" then (Put a (Put "world" arrA))
                                  else (Put "unknown" arrA))

arrB :: SP String String
arrB = Get (\a -> if a == "my" then (Get (\a -> if a == "name" then (Get
(\a -> if a == "is" then Get (\a -> Put ("name: " ++ a) arrB)

                 else arrB))
                                                               else arrB))
                               else arrB)

inputB :: [String]
inputB = ["a", "b", "my", "name", "is", "thiago", "and", "I", "am", "so",
"cool"]

inputAB :: [(String, String)]
inputAB = zip inputA inputB

main :: IO ()
main = let actualOutputB = runSP arrB inputB
           actualOutputB1 = runSP (first arrB) (zip inputB (repeat "a"))
           actualOutputA = runSP arrA inputA
           actualOutputA1 = runSP (first arrA) (zip inputA (repeat "a"))
           actualOutputAB = runSP (arrA *** arrB) inputAB
       in do putStrLn $ "inputAB: " ++ show inputAB
             putStrLn $ "outputA: " ++ show actualOutputA
             putStrLn $ "outputA1: " ++ show actualOutputA1
             putStrLn $ "outputB: " ++ show actualOutputB
             putStrLn $ "outputB1: " ++ show actualOutputB1
             putStrLn $ "outputAB: " ++ show actualOutputAB



[3]: https://github.com/peti/streamproc/blob/master/Control/Arrow/SP.hs#L58


2013/10/7 Thiago Negri <evohunz at gmail.com>

> This is my first contact with QuickCheck, but does this test count as a
> proof that my implementation is correct?
>
> QuickCheck shows 100 tests passed.
>
> prop_a xs = runSP (f *** g) xs == runSP (first f >>> swap >>> first g >>>
> swap) xs
>   where swap = arr (\(a,b) -> (b,a))
>         f = arr (++"a")
>         g = arr (++"b")
>
>
>
> 2013/10/7 Thiago Negri <evohunz at gmail.com>
>
>> "On the one hand, indeterminate a's need to be fed in before
>> indeterminate b's get pulled out. On the other hand, the c's need to behave
>> as if they were in a no-op assembly line. One c goes in, the one (and
>> same!) c drops out."
>>
>> I agree with "no-op assembly line", but when I'm using `first` on a
>> processor, I want to process the first stream *only*. The second stream
>> should remain as it was not touched, so future processors will receive the
>> same sequence from the second stream.
>>
>> I mean, I think I need to guarantee that this definition holds:
>>
>> `g *** f` is the same as `first g >>> swap >>> first f >>> swap`
>>
>> If my implementation of `first` uses a real no-op assembly line for `c`
>> (i.e., `arr id`), then I would lose the stream. As you said, I need to
>> buffer the second stream while processing the first one.
>>
>> Is my line of tought correct?
>>
>> I'll try to write some tests to verify this.
>>
>> Thanks!
>>
>>
>> 2013/10/7 Kim-Ee Yeoh <ky3 at atamo.com>
>>
>>> Hey Thiago,
>>>
>>> First of all, congratulations for reading Hughes! Many of his papers are
>>> worth reading and re-reading for both beginners and experts alike.
>>>
>>>
>>> On Tue, Oct 8, 2013 at 12:05 AM, Thiago Negri <evohunz at gmail.com> wrote:
>>>
>>>> Exercise 2 (section 2.5) is asking to create a Stream Processor that
>>>> can map more than one output per input (e.g. 3 outcomes for a single
>>>> consume of the stream).
>>>
>>>
>>> Given
>>>
>>>
>>> > data SP a b = Put b (SP a b) | Get (a -> SP a b)
>>>
>>> it's easy to see that it's not just about more than one output per
>>> input. It's about n pieces of input producing m pieces of output, where
>>> (n,m) may even -- and probably does -- depend on previous inputs!
>>>
>>> The exercise asks for an implementation of the following Arrow instance:
>>>
>>> > first :: arr a b -> arr (a,c) (b,c)
>>>
>>> which, specialized to our case, is just SP a b -> SP (a,c) (b,c).
>>>
>>> It should now be apparent what the 'trickiness' is. On the one hand,
>>> indeterminate a's need to be fed in before indeterminate b's get pulled
>>> out. On the other hand, the c's need to behave as if they were in a no-op
>>> assembly line. One c goes in, the one (and same!) c drops out.
>>>
>>> So one way to look at this is as a buffering problem.
>>>
>>> At this point, I'd encourage you to think of some quickcheck tests you
>>> can write to convince yourself whether you have a right implementation or
>>> not.
>>>
>>> Your main function doesn't seem adequate for the task.
>>>
>>> -- Kim-Ee
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> Beginners at haskell.org
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20131008/a6fb6264/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Exercise of "Programming with Arrows"

Thiago Negri
And now I'm stuck trying to create an instance of ArrowLoop for the stream
processor. :(

My first implementation used a queue, just like the "first" function of my
Arrow instance. It worked like a charm, but failed in the test proposed by
the paper:

"""
- Check that your implementation of loop has the property that the arrows
loop (arr id) and loop (arr swap) behave as arr id:

SP> runSP (loop (arr id)) [1..10]
[1,2,3,4,5,6,7,8,9,10]

SP> runSP (loop (arr swap)) [1..10]
[1,2,3,4,5,6,7,8,9,10]
"""

The first test was ok, but the "runSP (loop (arr swap)) [1..10]" tried to
consume a value from my empty feedback queue and it exploded.

I scrolled back to section 2.3 to see how Hughes did this neat trick to his
SF type and it kind of made sense to me. But I can't express that same
"irrefutable pattern magic" on the SP data type. As the result of consuming
an element of the stream is dynamic (it's like a monad bind), I can't find
a way to declare fit the expression of the feedback stream in terms of
itself, I keep hitting recursion at some point.

I don't even know if I can explain what I'm feeling about what my problem
is. Yet I can't find a way to solve the problem.

Can someone help me?
Please, don't solve it for me, just give some tips.

My current code is here:
https://gist.github.com/thiago-negri/2e541a9f9762c727bdd4
The problematic ArrowLoop instance is at line 45.

Thanks,
Thiago.



2013/10/8 Thiago Negri <evohunz at gmail.com>

> I think I'm starting to get the "way of arrows".
>
> My implementation was incorrect. I've seen it with the hand made test
> listed below [1].
> The output of "first arrA" and "first arrB" should be joined together and
> form a new stream with the length of the shortest output of both ("arrA ***
> arrB"), and this wasn't happening.
>
> I've found package "streamproc" at Hackage and that gave me some insights.
> Yet I think "streamproc" is also wrong, as it does not buffer the second
> stream.
> You can check it at line 58 of SP.hs [3] that it ignores the first element
> of the pair.
> But I didn't write a test to check what is the implication of this, I'll
> try to do this as a next step into understanding arrows.
>
> That exercise really helped me!
>
>  My new implementation, wich I think is correct now, is listed below [2].
>
> Thanks!
>
> Thiago
>
>
> [1]:
> inputA :: [String]
> inputA = ["a", "b", "hello", "c", "d", "e", "hello", "f", "g", "e", "x"]
>
> arrA :: SP String String
> arrA = Get (\a -> if a == "hello" then (Put a (Put "world" arrA))
>                                   else (Put "unknown" arrA))
>
> arrB :: SP String String
> arrB = Get (\a -> if a == "my" then (Get (\a -> if a == "name" then (Get
> (\a -> if a == "is" then Get (\a -> Put ("name: " ++ a) arrB)
>
>                    else arrB))
>                                                                else arrB))
>                                else arrB)
>
> inputB :: [String]
> inputB = ["a", "b", "my", "name", "is", "thiago", "and", "I", "am", "so",
> "cool"]
>
> inputAB :: [(String, String)]
> inputAB = zip inputA inputB
>
> main :: IO ()
> main = let actualOutputB = runSP arrB inputB
>            actualOutputB1 = runSP (first arrB) (zip inputB (repeat "a"))
>            actualOutputA = runSP arrA inputA
>            actualOutputA1 = runSP (first arrA) (zip inputA (repeat "a"))
>            actualOutputAB = runSP (arrA *** arrB) inputAB
>        in do putStrLn $ "inputAB: " ++ show inputAB
>              putStrLn $ "outputA: " ++ show actualOutputA
>              putStrLn $ "outputA1: " ++ show actualOutputA1
>              putStrLn $ "outputB: " ++ show actualOutputB
>              putStrLn $ "outputB1: " ++ show actualOutputB1
>              putStrLn $ "outputAB: " ++ show actualOutputAB
>
>
>
> [2]:
> module SP where
>
> import Prelude hiding (id, (.))
> import Control.Category
> import Control.Arrow
>  import Test.QuickCheck
>
> data SP a b = Put b (SP a b) | Get (a -> SP a b)
>
> runSP :: SP a b -> [a] -> [b]
> runSP (Put b s) as = b:runSP s as
> runSP (Get k) (a:as) = runSP (k a) as
> runSP (Get k) [] = []
>
> compose :: SP b c -> SP a b -> SP a c
> compose (Put a s) g = Put a (compose s g)
> compose (Get k) (Put a s) = compose (k a) s
> compose f (Get k) = Get (\a -> compose f (k a))
>
> instance Category SP where
>   id = arr id
>   (.) = compose
>
> instance Arrow SP where
>   arr f = Get (\a -> Put (f a) (arr f))
>   first = queued empty empty
>
> queued :: Queue a -> Queue c -> SP a b -> SP (a, c) (b, c)
> queued qa qc (Put a s) = case pop qc of Nothing -> Get (\(a', c) -> Put
> (a, c) (queued (push a' qa) qc s))
>                                         Just (c, qc') -> Put (a, c)
> (queued qa qc' s)
> queued qa qc (Get k) = case pop qa of Nothing -> Get (\(a, c) -> queued qa
> (push c qc) (k a))
>                                       Just (a, qa') -> queued qa' qc (k a)
>
> data Queue a = Queue [a]
>
> empty :: Queue a
> empty = Queue []
>
> push :: a -> Queue a -> Queue a
> push a (Queue as) = Queue (a:as)
>
> pop :: Queue a -> Maybe (a, Queue a)
> pop (Queue []) = Nothing
> pop (Queue (a:as)) = Just (a, Queue as)
>
> delayed :: (a, c) -> SP a b -> SP (a, c) (b, c)
> delayed (a, c) (Put b s) = Put (b, c) (delayed (a, c) s)
> delayed (a, c) (Get k) = firstWithValue (k a) c
>
> firstWithValue :: SP a b -> c -> SP (a, c) (b, c)
> firstWithValue (Put a s) c = Put (a, c) (firstWithValue s c)
> firstWithValue (Get k) _ = Get (\(a, c) -> firstWithValue (k a) c)
>
> input :: [(String, String)]
> input = [("a1", "a2"), ("b1", "b2"), ("c1", "c2"), ("d1", "d2")]
>
> myArrow :: SP (String, String) (String, String)
> myArrow = (delay "db1" >>> delay "da1") *** (delay "db2" >>> delay "da2")
>
> delay :: a -> SP a a
> delay b = Put b (arr id)
>
> inputA :: [String]
> inputA = ["a", "b", "hello", "c", "d", "e", "hello", "f", "g", "e", "x"]
>
> arrA :: SP String String
> arrA = Get (\a -> if a == "hello" then (Put a (Put "world" arrA))
>                                   else (Put "unknown" arrA))
>
> arrB :: SP String String
> arrB = Get (\a -> if a == "my" then (Get (\a -> if a == "name" then (Get
> (\a -> if a == "is" then Get (\a -> Put ("name: " ++ a) arrB)
>
>                    else arrB))
>                                                                else arrB))
>                                else arrB)
>
> inputB :: [String]
> inputB = ["a", "b", "my", "name", "is", "thiago", "and", "I", "am", "so",
> "cool"]
>
> inputAB :: [(String, String)]
> inputAB = zip inputA inputB
>
> main :: IO ()
> main = let actualOutputB = runSP arrB inputB
>            actualOutputB1 = runSP (first arrB) (zip inputB (repeat "a"))
>            actualOutputA = runSP arrA inputA
>            actualOutputA1 = runSP (first arrA) (zip inputA (repeat "a"))
>            actualOutputAB = runSP (arrA *** arrB) inputAB
>        in do putStrLn $ "inputAB: " ++ show inputAB
>              putStrLn $ "outputA: " ++ show actualOutputA
>              putStrLn $ "outputA1: " ++ show actualOutputA1
>              putStrLn $ "outputB: " ++ show actualOutputB
>              putStrLn $ "outputB1: " ++ show actualOutputB1
>              putStrLn $ "outputAB: " ++ show actualOutputAB
>
>
>
> [3]:
> https://github.com/peti/streamproc/blob/master/Control/Arrow/SP.hs#L58
>
>
> 2013/10/7 Thiago Negri <evohunz at gmail.com>
>
>> This is my first contact with QuickCheck, but does this test count as a
>> proof that my implementation is correct?
>>
>> QuickCheck shows 100 tests passed.
>>
>> prop_a xs = runSP (f *** g) xs == runSP (first f >>> swap >>> first g >>>
>> swap) xs
>>   where swap = arr (\(a,b) -> (b,a))
>>         f = arr (++"a")
>>         g = arr (++"b")
>>
>>
>>
>> 2013/10/7 Thiago Negri <evohunz at gmail.com>
>>
>>> "On the one hand, indeterminate a's need to be fed in before
>>> indeterminate b's get pulled out. On the other hand, the c's need to behave
>>> as if they were in a no-op assembly line. One c goes in, the one (and
>>> same!) c drops out."
>>>
>>> I agree with "no-op assembly line", but when I'm using `first` on a
>>> processor, I want to process the first stream *only*. The second stream
>>> should remain as it was not touched, so future processors will receive the
>>> same sequence from the second stream.
>>>
>>> I mean, I think I need to guarantee that this definition holds:
>>>
>>> `g *** f` is the same as `first g >>> swap >>> first f >>> swap`
>>>
>>> If my implementation of `first` uses a real no-op assembly line for `c`
>>> (i.e., `arr id`), then I would lose the stream. As you said, I need to
>>> buffer the second stream while processing the first one.
>>>
>>> Is my line of tought correct?
>>>
>>> I'll try to write some tests to verify this.
>>>
>>> Thanks!
>>>
>>>
>>> 2013/10/7 Kim-Ee Yeoh <ky3 at atamo.com>
>>>
>>>> Hey Thiago,
>>>>
>>>> First of all, congratulations for reading Hughes! Many of his papers
>>>> are worth reading and re-reading for both beginners and experts alike.
>>>>
>>>>
>>>> On Tue, Oct 8, 2013 at 12:05 AM, Thiago Negri <evohunz at gmail.com>wrote:
>>>>
>>>>> Exercise 2 (section 2.5) is asking to create a Stream Processor that
>>>>> can map more than one output per input (e.g. 3 outcomes for a single
>>>>> consume of the stream).
>>>>
>>>>
>>>> Given
>>>>
>>>>
>>>> > data SP a b = Put b (SP a b) | Get (a -> SP a b)
>>>>
>>>> it's easy to see that it's not just about more than one output per
>>>> input. It's about n pieces of input producing m pieces of output, where
>>>> (n,m) may even -- and probably does -- depend on previous inputs!
>>>>
>>>> The exercise asks for an implementation of the following Arrow instance:
>>>>
>>>> > first :: arr a b -> arr (a,c) (b,c)
>>>>
>>>> which, specialized to our case, is just SP a b -> SP (a,c) (b,c).
>>>>
>>>> It should now be apparent what the 'trickiness' is. On the one hand,
>>>> indeterminate a's need to be fed in before indeterminate b's get pulled
>>>> out. On the other hand, the c's need to behave as if they were in a no-op
>>>> assembly line. One c goes in, the one (and same!) c drops out.
>>>>
>>>> So one way to look at this is as a buffering problem.
>>>>
>>>> At this point, I'd encourage you to think of some quickcheck tests you
>>>> can write to convince yourself whether you have a right implementation or
>>>> not.
>>>>
>>>> Your main function doesn't seem adequate for the task.
>>>>
>>>> -- Kim-Ee
>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> Beginners at haskell.org
>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20131010/3ca1d812/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Exercise of "Programming with Arrows"

Kim-Ee Yeoh
Administrator
On Fri, Oct 11, 2013 at 12:10 AM, Thiago Negri <evohunz at gmail.com> wrote:

> And now I'm stuck trying to create an instance of ArrowLoop for the stream
> processor. :(


If you want quick help, you can always ask on cafe.

That said, I believe you're capable of figuring this out on your own. Give
it a couple more days to see where it leads you. Read up on irrefutable
patterns if need be.

"But surely," you ask, "learning more quickly is better, no?"

It really depends on what one means by learning. The point is, the struggle
etches the ensuing revelation more deeply, resulting in more durable
retention.

-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20131011/4704247f/attachment.htm>