ANNOUNCE: arrow-list. List arrows for Haskell.
Hi all, Live from the Hackaton in Ghent, Belgium, I present the first release of the arrow-list[1,2] package. List arrows are a powerful tool when processing XML, building query languages and lots of other domains that build on functions that might return more than one value as their output. This package is inspired by the arrow combinators provided by the HXT package, but in my opinion list arrows deserve to be on Hackage on their own. Cheers, Sebastiaan [1] http://hackage.haskell.org/package/arrow-list [2] https://github.com/sebastiaanvisser/arrow-list ------------------------------------------------------------------------ (package description) List arrows for Haskell. This small Haskell library provides some type class, types and functions to work with list arrows. List arrows represent computations that may return multiple outputs. Making functions that return lists an instance of both the `Category` and `Arrow` type classes allow you to easily compose multiple computations into one with standard building blocks. This package provides: - A type class `ArrowList` for embedding functions that produce a list of outputs into _some_ list arrow. - A list of utility functions for working with list-arrows, these functions are based on the `ArrowList` type class so they are not tied one specific instance. - A concrete list arrow type that is implemented as a `Kleisli` arrow over the `ListT` list monad transformer. In short, you can both build pure list arrows and list arrows that produce tributary effects. - Not list arrow specific: A type class `ArrowKleisli` for embedding monadic computations into an arrow.
On Nov 6, 2010, at 10:00 PM, Sebastiaan Visser wrote:
List arrows are a powerful tool when processing XML, building query languages and lots of other domains that build on functions that might return more than one value as their output.
Interesting. Do you plan to write some examples that show * how to use ListArrows, * differences to using the list monad, and * when using ListArrow is preferrable? I'm interested to see something like this worked out although I have some rough ideas like "monads are more powerful and arrows may allow stronger reasoning and more efficient implementations". Can you substantiate these general points for the concrete case of ListArrow vs list monad? I assume your implementation is *not* more efficient than the list monad as it builds on ListT. Sebastian
On Nov 7, 2010, at 1:40 AM, Sebastian Fischer wrote:
On Nov 6, 2010, at 10:00 PM, Sebastiaan Visser wrote:
List arrows are a powerful tool when processing XML, building query languages and lots of other domains that build on functions that might return more than one value as their output.
Interesting. Do you plan to write some examples that show
* how to use ListArrows,
Yes, I certainly am. Although, time is currently not on my side. I'm planning to write up a blog post about using list arrows for XML processing.
* differences to using the list monad, and * when using ListArrow is preferrable?
Currently I'm playing with the idea of a translation of XML list arrows in Haskell to DOM operations in JavaScript. The lack of ArrowApply (the full power of monads) allows you to inspect your computations, this makes translations to other languages possible.
I'm interested to see something like this worked out although I have some rough ideas like "monads are more powerful and arrows may allow stronger reasoning and more efficient implementations". Can you substantiate these general points for the concrete case of ListArrow vs list monad?
Beside the fact that, after playing with them for while, I find arrows more convenient to use than monads, the ability to inspect their structure can help you to optimize them. Maybe this sounds weird on the Haskell mailing list, but at Silk[1] we have a full implementation of (functional reactive) list arrows in JavaScript. The arrows build up an AST of operations that we statically optimize to a more efficient form. This is needed because JavaScript itself is not going to fuse intermediate list for you. I'm reinventing all of this in Haskell now to gain more insight in what we've actually done in JavaScript. :-)
I assume your implementation is *not* more efficient than the list monad as it builds on ListT.
That is entirely true. But this is only implementation, different implementations may be possible that are more efficient. As long as ArrowApply is not involved static optimization might be possible that fuses intermediate lists, as far as the compiler is not already doing so. I'm also planning to investigate whether it is possible (useful) to perform the list computations (the map in concatMap) in parallel. I'm not sure if someone has already tried this for list monads.
Sebastian
Sebastiaan [1] https://blog.silkapp.com/2009/12/reinventing-xslt-in-pure-javascript/
I'm planning to write up a blog post about using list arrows for XML processing.
Ok, I'll say tuned! Maybe a smaller example for the Haddock docs needs less time.
Maybe this sounds weird on the Haskell mailing list, but at Silk[1] we have a full implementation of (functional reactive) list arrows in JavaScript. The arrows build up an AST of operations that we statically optimize to a more efficient form. This is needed because JavaScript itself is not going to fuse intermediate list for you.
I'm reinventing all of this in Haskell now to gain more insight in what we've actually done in JavaScript. :-)
Sounds more interesting than weird to me. In case you blog about that too, I'll probably read it. I'm interested to get an intuition what you can do with arrows and what not. An intuition that goes beyond the quite abstract "you can't choose different computation paths based on the result of a computation". Can you, for example, define a `perm` arrow that yields every permutation of it's input? Monadic implementations look like they need `>>=` but there may be another way.. Maybe you now have an example for the docs ;o)
I'm also planning to investigate whether it is possible (useful) to perform the list computations (the map in concatMap) in parallel. I'm not sure if someone has already tried this for list monads.
I tried something similar a while ago (for monads): <http://www-ps.informatik.uni-kiel.de/~sebf/haskell/speedup-search-with-paral...
Sebastian P.S. In
[1] https://blog.silkapp.com/2009/12/reinventing-xslt-in-pure-javascript/
there are two occurrences of the `sum` function which should probably be `alt` instead.
to answer my own question: On Nov 7, 2010, at 8:33 PM, Sebastian Fischer wrote:
Can you, for example, define a `perm` arrow that yields every permutation of it's input? Monadic implementations look like they need `>>=` but there may be another way..
A `perm` arrow can be defined in the "usual" way using the list-arrow package: {-# LANGUAGE TypeOperators #-} import Control.Arrow import Control.Arrow.ArrowList perm :: (ArrowList (~>), ArrowPlus (~>)) => [a] ~> [a] perm = isA null <+> (uncons >>> second perm >>> insert) insert :: (ArrowList (~>), ArrowPlus (~>)) => (a,[a]) ~> [a] insert = cons <+> (second uncons >>> rearrange >>> second insert
cons) where rearrange = assocL >>> first swap >>> assocR
It may be possible to do this with `ArrowChoice` only, that is, without resorting to the operations of `ArrowList`, but they looked simpler. In order to support the above, we need a bunch of auxiliary arrows. First, list con- and destructors: cons :: Arrow (~>) => (a,[a]) ~> [a] cons = arr (uncurry (:)) uncons :: ArrowList (~>) => [a] ~> (a,[a]) uncons = isA (not . null) >>> arr (\ (x:xs) -> (x,xs)) Second (and more annoyingly), "reordering" arrows: swap :: Arrow (~>) => (a,b) ~> (b,a) swap = arr (\ (x,y) -> (y,x)) assocL :: Arrow (~>) => (a,(b,c)) ~> ((a,b),c) assocL = arr (\ (x,(y,z)) -> ((x,y),z)) assocR :: Arrow (~>) => ((a,b),c) ~> (a,(b,c)) assocR = arr (\ ((x,y),z) -> (x,(y,z))) This is my first program with arrows so it might be unnecessarily complicated. Is there a more elegant way? I wonder how badly my use of `arr` influences how the program can be optimized. I hope it's still better than just using perm = arrL perms where perms :: [a] -> [[a]] perms = ... ;o) Sebastian
participants (2)
-
Sebastiaan Visser -
Sebastian Fischer