Work on Collections Processing Arrows?
Has anyone developed a typeclass model for (Control.Monad.mapM) and related functions for arrows? I've a preliminary model, using Adam Megacz's Generalized Arrows, of the form: class (GArrowDrop a (**) u) => GArrowMap_ a (**) u c where mapA_ :: a d u -> a (c d) u class (GArrow a (**) u c) => GArrowMap a (**) u c where mapA :: a d r -> a (c d) (c r) class (GArrowMap a (**) u c) => GArrowJoin a (**) u c where join :: a d (c r) -> a (c d) (c r) class (GArrow a (**) u) => GArrowUnion a (**) u c where union :: a ((c r) ** (c r)) (c r) class (GArrowMap a (**) u c, GArrow a (++) v) => GArrowPartition a (**) u (++) v c where partition :: a d (q ++ r) -> a (c d) ((c q) ** (c r)) Motivations: regular arrows (including GArrows) expose simple products for behavior, but those have a static 'width' and don't seem suitable for processing large values. ArrowApply would give me a dynamic amount of processing, but seems excessively expressive. In my own case, 'c' might be representing an asynchronous or distributed, reactive collection, so the ability to restrict expressiveness is important for performance. I'm wondering if you know of any other work along the same lines. Thank you, Dave
David Barbour
I've a preliminary model, using Adam Megacz's Generalized Arrows, of the form:
Hey, neat. Actually, this sounds more like the generalized arrow version of arrowized FRP's "switch" and "par" (Section 2.6 of [1]). I'd been meaning to figure out the GArrow version of those but never got around to it.
ArrowApply would give me a dynamic amount of processing, but seems excessively expressive.
Yes, that's overkill and would rule out the applications where implementing ArrowApply is impossible.
class (GArrow a (**) u c) => GArrowMap a (**) u c where mapA :: a d r -> a (c d) (c r)
class (GArrow a (**) u) => GArrowUnion a (**) u c where union :: a ((c r) ** (c r)) (c r)
class (GArrowMap a (**) u c) => GArrowJoin a (**) u c where join :: a d (c r) -> a (c d) (c r)
I like these; I think you're on the right track. The last one reminds me of concatMap.
class (GArrowDrop a (**) u) => GArrowMap_ a (**) u c where mapA_ :: a d u -> a (c d) u
I don't think you want to ask for a GArrowDrop instance here -- if you've got that, you might as well just ignore the argument and say: mapA_ = \x -> ga_drop Perhaps what you want is gac_drop :: a (c u) u ... which is a bit like ga_cancell and ga_cancelr, but for a whole collection rather than one input at a time. By the way, I've started [2] using type families for the "aggregate" GArrow classes like GArrowSTLC. This greatly reduces the syntactic noise in the types -- you only have one type parameter instead of four. The price is that a single type can't be an instance of these classes in more than one way (see Section 3.6.1 of [3] for why this is important). I tend to think of type classes in terms of dictionary-passing (like in Coq), so I often get myself into trouble in situations where I know which dictionary to pass, but can't get Haskell's instance inference to do what I want. I welcome suggestions on ways to improve the user-friendliness of the GArrow classes -- there are probably a bunch of cool Haskell type class tricks I ought to be using but don't know about.
In my own case, 'c' might be representing an asynchronous or distributed, reactive collection, so the ability to restrict expressiveness is important for performance.
Certainly. The multiplicative disjunction [4] of linear logic is the "binary" version of this: (A \bindnasrepma B) is sort of like an A and a B in geographically distant locations; if you have a (Int \bindnasrepma Int) you have two Int's, but in order to (for example) add them together you must use some sort of communication primitive to get them both to the same place. It sounds like you want a sort of "collection version" of multiplicative disjunction. I bet Data Paralell Haskell's parallel array type-former (([::]) :: * -> *) would be an instance of this class. - a [1] http://dx.doi.org/10.1145/581690.581695 [2] http://git.megacz.com/?p=ghc-base.git;a=commitdiff;h=47c002441ab30c48 [3] http://arxiv.org/pdf/1007.2885v2 [4] http://en.wikipedia.org/wiki/Linear_logic#The_resource_interpretation
I wonder if I need something like your use of 'representation' types, i.e.
to restrict what sort of elements can be stored in a collection.
I've just recently hit on the idea of using a barrier type 'V' to wrap a
synchronous value. A 'synchronous value' is one that can be observed at a
single time and place, without any further communication or delay. In a
sense, any Haskell value might be a synchronous value, since (barring
suspicious use of unsafePerformIO) even lazy or parallel values are
observable without further communication effects.
So, in an implementation, I might get a set of constructors that look
something like this:
arr :: (x->y) -> A (V x) (V y)
synch :: A ((V x) :*: (V y)) (V (x,y))
constant :: t -> A (V ()) (V t) -- 'u' = (V ()) for product
Your use of representation types in GArrowReify, GArrowConstant, etc. really
help for capturing these constructors.
While I'm happy in my case to allow asynchronous collections of asynchronous
types, I can imagine the possibility of someone wanting to impose a
restriction on what sort of types can be generated inside a collection, i.e.
such that we have:
mapA :: a (V x) (V y) -> a (c x) (c y)
This would block, for example, the possibility that 'c' will itself contain
asynchronous collections, sums, or products.
I'll admit to some reluctance, however, to clutter up several typeclasses
with four more types. What are your thoughts regarding this issue?
Regards,
Dave
On Tue, May 10, 2011 at 1:25 PM, Adam Megacz
class (GArrow a (**) u c) => GArrowMap a (**) u c where mapA :: a d r -> a (c d) (c r)
class (GArrow a (**) u) => GArrowUnion a (**) u c where union :: a ((c r) ** (c r)) (c r)
class (GArrowMap a (**) u c) => GArrowJoin a (**) u c where join :: a d (c r) -> a (c d) (c r)
I like these; I think you're on the right track. The last one reminds me of concatMap.
class (GArrowDrop a (**) u) => GArrowMap_ a (**) u c where mapA_ :: a d u -> a (c d) u
I don't think you want to ask for a GArrowDrop instance here -- if you've got that, you might as well just ignore the argument and say:
mapA_ = \x -> ga_drop
Perhaps what you want is
gac_drop :: a (c u) u
... which is a bit like ga_cancell and ga_cancelr, but for a whole collection rather than one input at a time.
By the way, I've started [2] using type families for the "aggregate" GArrow classes like GArrowSTLC. This greatly reduces the syntactic noise in the types -- you only have one type parameter instead of four. The price is that a single type can't be an instance of these classes in more than one way (see Section 3.6.1 of [3] for why this is important).
I tend to think of type classes in terms of dictionary-passing (like in Coq), so I often get myself into trouble in situations where I know which dictionary to pass, but can't get Haskell's instance inference to do what I want. I welcome suggestions on ways to improve the user-friendliness of the GArrow classes -- there are probably a bunch of cool Haskell type class tricks I ought to be using but don't know about.
In my own case, 'c' might be representing an asynchronous or distributed, reactive collection, so the ability to restrict expressiveness is important for performance.
Certainly. The multiplicative disjunction [4] of linear logic is the "binary" version of this: (A \bindnasrepma B) is sort of like an A and a B in geographically distant locations; if you have a (Int \bindnasrepma Int) you have two Int's, but in order to (for example) add them together you must use some sort of communication primitive to get them both to the same place.
It sounds like you want a sort of "collection version" of multiplicative disjunction. I bet Data Paralell Haskell's parallel array type-former (([::]) :: * -> *) would be an instance of this class.
- a
[1] http://dx.doi.org/10.1145/581690.581695
[2] http://git.megacz.com/?p=ghc-base.git;a=commitdiff;h=47c002441ab30c48
[3] http://arxiv.org/pdf/1007.2885v2
[4] http://en.wikipedia.org/wiki/Linear_logic#The_resource_interpretation
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
David Barbour
I wonder if I need something like your use of 'representation' types, i.e. to restrict what sort of elements can be stored in a collection. ... I'll admit to some reluctance, however, to clutter up several typeclasses with four more types. What are your thoughts regarding this issue?
Yes, they certainly do clutter things up... but really, the whole representation business is in there mostly to show that the "functor is identity-on-objects" requirement of Freyd categories need not apply to generalized arrows. If you want to reduce the clutter, the simple trick I'm experimenting with now works like this: start with your multi-parameter class class GArrow g (**) u where ... Then, for all but the first type argument, create a type family indexed by the first type argument: type family GArrowTensor g :: * -> * -> * -- (**) type family GArrowUnit g :: * -- u And then use -XFlexibleContexts to declare a wrapper class with only one argument: class (GArrow g (GArrowTensor g) (GArrowUnit g), GArrowCopy g (GArrowTensor g) (GArrowUnit g), GArrowSwap g (GArrowTensor g) (GArrowUnit g), ... ) => GArrowWrappedUp g I'm sure you could do something similar with the type parameters "c" and "r". The only price is that you can then have only one instance in scope at any given point in time. - a
participants (2)
-
Adam Megacz -
David Barbour