News aggregator

Joachim Breitner: gtk-vector-screenshot screencast

Planet Haskell - Thu, 04/24/2014 - 4:07pm

I recently installed piwik on my website, to get some idea about how it is being used. Piwik is a very nice and shiny tool, although it is slightly scary to watch people walk through your website, click for click. Anyways, I now know that I get around 50 visitors per day.

But I also learn where they are coming from, and this way I noticed that “Shnatsel” did a very nice screencast of my gtk-vector-screenshot tool – if I had not created it myself I would think it was fake.

Categories: Offsite Blogs

Typeable and Data in Haskell

del.icio.us/haskell - Thu, 04/24/2014 - 12:32pm
Categories: Offsite Blogs

Functional Jobs: functional software developer at OpinionLab (Full-time)

Planet Haskell - Thu, 04/24/2014 - 12:10pm

OpinionLab is seeking a Software Developer with strong agile skills to join our Chicago, IL based Product Development team in the West Loop.

As a member of our Product Development team, you will play a critical role in the architecture, design, development, and deployment of OpinionLab's web-based applications and services. You will be part of a high-visibility agile development team empowered to deliver high-quality, innovative, and market leading voice-of-customer (VoC) data acquisition and feedback intelligence solutions. If you thrive in a collaborative, fast-paced, get-it-done environment and want to be a part of one of Chicago's most innovative companies, we want to speak with you!

Key Responsibilities include:

  • Development of scalable data collection, storage, processing & distribution platforms & services.
  • Architecture and design of a mission critical SaaS platform and associated APIs.
  • Usage of and contribution to open-source technologies and framework.
  • Collaboration with all members of the technical staff in the delivery of best-in-class technology solutions.
  • Proficiency in Unix/Linux environments.
  • Work with UX experts in bringing concepts to reality.
  • Bridge the gap between design and engineering.
  • Participate in planning, review, and retrospective meetings (à la Scrum).

Desired Skills & Experience:

  • BDD/TDD, Pair Programming, Continuous Integration, and other agile craftsmanship practices
  • Desire to learn Clojure (if you haven't already)
  • Experience with both functional and object-oriented design and development within an agile environment
  • Polyglot programmer with mastery of one or more of the following languages: Lisp (Clojure, Common Lisp, Scheme), Haskell, Scala, Python, Ruby, JavaScript
  • Knowledge of one or more of: AWS, Lucene/Solr/Elasticsearch, Storm, Chef

Get information on how to apply for this position.

Categories: Offsite Blogs

Tour of the Haskell Syntax

del.icio.us/haskell - Thu, 04/24/2014 - 11:58am
Categories: Offsite Blogs

Pointwise Lenses

Haskell on Reddit - Thu, 04/24/2014 - 10:09am
Categories: Incoming News

Chris Reade: Repa Laplace and SOR

Planet Haskell - Thu, 04/24/2014 - 9:54am
Using the Repa Library for Laplace’s Equation and SOR

This describes the result of some experiments to enhance an existing elegant (haskell parallel array) laplace solver by using successive over-relaxation (SOR) techniques. The starting point was a laplace solver based on stencil convolution and using the Haskell Repa library (Regular Parallel Arrays) as reported in a paper by Lippmeier, Keller and Peyton-Jones. (There is also a 2011 published paper with the first two authors (Lippmeier and Keller 2011))

Background Laplace’s Equation and Iterative solvers

The Laplace equation

is usually abbreviated to simply , where is a scalar potential (such as temperature) over a smooth surface.

For numerical solutions we will restrict attention to a rectangular surface with some fixed boundary values for u. (The boundary is not necessarily the border of the rectangle, as we can allow for fixed values at internal regions as well). The problem is made discrete for finite difference methods by imposing a grid of points over the surface and here we will assume this is spaced evenly ( in the direction and in the direction). Approximating solutions numerically amounts to approximating a fixedpoint for the grid values satisfying the boundary values and also, for non-boundary points (i,j) satisfying

where

If we also assume then this simplifies to

Iterating to find this fixed poiint from some suitable starting values is called relaxation. The simplest (Jacobi) method involves iterating the calculation of new values from previous values until the iterations are close enough to converging.

This method, whilst very simple, can be extremely slow to converge. One improvement is given by the Gauss-Seidel method which assumes the next set of values in each iteration are calculated row by row in a scan across the columns allowing some new values to be used earlier during the same iteration step (changing to for calculated values in the previous column and in the previouus row).

Unfortunately, this assumption about the order of evaluation of array elements interferes with opportunities to use parallel computation of the array elements (as we wish to do using Repa array primitives).

Successive over-relaxation (SOR)

Successive over-relaxation is a method used to speed up convergence of the iterations by using a weighted sum of the previous iteration with the new one at each relaxation step. Using as the weight we calculate first (substituting for in the above equation), then calculate

Values of less than 1 will slow down the convergence (under-relaxation). A value of between 1 and 2 should speed up convergence. In fact the optimal value for will vary for each iteration, but we will work with constant values only here. It is also important to note that starting with values above 1 will generally cause oscillations (divergence) if just the Jacobi scheme is used, so successive over-relaxation relies on a speed up of the basic iteration such as that provided by the Gauss-Seidel scheme.

The original stencil version using Repa

In the paper a stencil mapping technique is used to get fast performance using the Repa array primitives. The code uses the Repa library version 3

The main relaxation step is expressed as

relaxLaplace arr = computeP $ szipWith (+) arrBoundValue -- boundary setting $ szipWith (*) arrBoundMask -- boundary clearing $ smap (/ 4) $ mapStencil2 (BoundConst 0) [stencil2| 0 1 0 1 0 1 0 1 0 |] arr

We will be taking this as a starting point, so we review details of this (working from the bottom up).

A stencil is described in a quoted form to express which neighbours are to be added (using zeros and ones) with the element being scanned assumed to be the middle item. Thus this stencil describes adding the north, west, east, and south neighbours for each item. The mapStencil2 is a Repa array primitive which applies the stencil to all elements of the previous iteration array (arr). It is also supplied with a border directive (Boundconst 0) which just says that any stencil item arising from indices outside the array is to be treated as 0. This stencil mapping will result in a non-manifest array, in fact, in a partitioned array split up into border parts and non-border parts to aid later parallel computation. After the stencil map there is a mapping across all the results to divide by 4 using smap (which improves over the basic repa array map for partitioned arrays). These calculations implement the Jacobi scheme.

The subsequent two szipWith operations are used to reset the fixed boundary values. (The primitive szipWith again improves over the basic repa array zipWith by catering explicitly for partitioned arrays.) More specifically, szipWith(*) is used with an array (arrBoundMask) which has zero for boundary positions and 1 for other positions – thus setting the boundary items to 0. After this szipWith(+) is used with an array (arrBoundValues) which has the fixed initial values for the boundary items and zero for all other items. Thus the addition reinstates the initial boundary values.

These array calculations are all delayed so a final computeP is used to force the parallel evaluations of items to produce a manifest array result. This technique allows a single pass with inlining and fusion optimisations of the code to be possible for the calculation of each element. Use of computeP requires the whole calculation to be part of a monad computation. This is a type constraint for the primitive to exclude the possibility of nested calls of computeP overlapping.

A significant advantage of this stencil implementation is that programming directly with array indices is avoided (these are built into the primitives once and for all and are implemented to avoid array bound checks being repeated unnecessarily).

Unfortunately, though, this implementation is using the Jacobi scheme for the iteration steps which is known to have very slow convergence.

We would like to improve on this by using successive over-relaxation, but as pointed out earlier, this will not work with the Jacobi scheme. Furthermore, the Gauss-Seidel improvement will not help because it is based on retrieving values from an array still being updated. This is not compatible with functional array primitives and stencils and prevents simple exploitation of parallel array calculations.

To the rescue – the red-black scheme for calculating iterations.

Red-black Iterations

This scheme is well known and based on the observation that on a red-black checkerboard, for any red square, the north, west, east, and south neighbours are all black and conversely neighbours of black squares are all red. This leads to the simple idea of calculating updates to all the red squares first, then using these updated values to calculate the new black square values.

Implementation using stencils and repa The set up

We split the original array into a red array and black array with simple traverse operations. We assume the original array (arr) has an even number of columns so the number of red and black cells are the same. As a convention we will take the (0,0) item to be red so we want, for red array (r)

r(i,j) = arr(i, 2*j + (i `mod` 2))

where

arr has i <- 0..n-1, j <- 0..2m-1 r has i <- 0..n-1, j <- 0..m-1

The traverse operation from the Repa library takes as arguments, the original array, a mapping to express the change in shape, and a lookup function to calculate values in the new array (when given a get operation for the original array and a coordinate (i,j) in the new array)

> projectRed :: Array U DIM2 Double -> Array D DIM2 Double > projectRed arr = > traverse arr > (\ (e :. i :. j) -> (e :. i :. (j `div` 2))) > (\get (e :. i :. j) -> get (e :. i :. 2*j + (i `mod` 2)))

Here (and throughout) we have restricted the type to work with two dimensional arrays of Double, although a more general type is possible. Notice also that the argument array is assumed to be manifest (U) and the result is a delayed array (D).

Similarly for the black array (b) we want

b(i,j) = arr(i, 2*j + ((i+1) `mod` 2))

with the same extent (shape) as for r, hence

> projectBlack :: Array U DIM2 Double -> Array D DIM2 Double > projectBlack arr = > traverse arr > (\ (e :. i :. j) -> (e :. i :. (j `div` 2))) > (\ get (e :. i :. j) -> get(e :. i :. 2*j + ((i+1) `mod` 2)))

We can also use these same functions to set up boundary mask and value arrays separately for red and black from the starting array (arrInit), initial mask (arrBoundMask), and boundary values (arrBoundValue)

do redBoundMask <- computeP $ projectRed arrBoundMask blackBoundMask <- computeP $ projectBlack arrBoundMask redBoundValue <- computeP $ projectRed arrBoundValue blackBoundValue <- computeP $ projectBlack arrBoundValue redInit <- computeP $ projectRed arrInit blackInit <- computeP $ projectBlack arrInit

This is part of a monad computation with each step using a computeP (parallel array computation) to create manifest versions of each of the arrays we need before beginning the iterations. These calculations are independent, so the sequencing is arbitrary.

The finish

At the end of the iterations we will reverse the split into red and black by combining using the traverse2 operation from the Repa library. We need

arr(i,j) = r(i, j `div` 2) when even(i+j) = b(i, j `div` 2) otherwise

where

arr has i <- 0..n-1 , j <- 0..2m-1 r has i <- 0..n-1 , j <- 0..m-1 b has i <- 0..n-1 , j <- 0..m-1

The traverse2 operation takes two arrays (here – of the same extent), a mapping to express the new extent (when given the two extents of the argument arrays), and a function to calculate values in the new array (when given the respective get operations for the original arrays (here – get1 and get2) and a coordinate (i,j) in the new array).

> combineRB r b = > traverse2 r b > (\ (e :. i :. j) _ -> (e :. i :. 2*j)) > (\ get1 get2 (e :. i :. j) -> > (if even(i+j) then get1 else get2) (e :. i :. j `div` 2) > ) Stencils in the iteration step

We use stencils as in the original, but when we consider a stencil on black cells which are to be combined as neighbours of the red cell r(i,j) we need the following shape, where b(i,j) corresponds to the middle item

0 1 0 1 1 0 0 1 0

BUT this is only when processing EVEN rows from the black array. For odd rows we need a different shape

0 1 0 0 1 1 0 1 0

That is, we need to apply one of two different stencils depending on whether the row is even or odd. Similarly in processing the red array to combine red neighbours of b(i,j) we need the same shaped stencils but the first shape above is used on odd rows of red cells and the second shape on even rows. We define and name the stencils as leftSt and rightSt

> leftSt :: Stencil DIM2 Double > leftSt = [stencil2| 0 1 0 > 1 1 0 > 0 1 0 |] > rightSt :: Stencil DIM2 Double > rightSt = [stencil2| 0 1 0 > 0 1 1 > 0 1 0 |]

Critically, we will need an efficient way to apply alternate stencils as we map across an array. At first, it may seem that we might have to rebuild a version of the primitive mapStencil2 to accommodate this, but that will get us into some complex array representation handling which is built into that primitive. On reflection, though, the combination of lazy evaluation and smart inlining/fusion optimisation by the compiler should allow us to simply apply both stencils on all elements and then choose the results we actually want. The laziness should ensure that the unwanted stencil applications are not actually calculated, and the administration of choosing should be simplified by compiler optimisations.

To apply our stencils we will use the Repa array primitive mapStencil2 which takes as arguments, a border handling directive, a stencil, and a (manifest) array, to produce a resulting (delayed) array.

mapStencil2 :: Boundary Double -> Stencil DIM2 Double -> Array U DIM2 Double -> Array D DIM2 Double

The choice of stencil will depend on the position (actually the evenness of the row). As we cannot refer to the indices when using the stencil mapping operation we are led to using traverse2 after mapping both stencils to select results from the two arrays produced. Our alternate stencil mapping operation will have a similar type to mapStencil2 except that it expects two stencils rather than one.

altMapStencil2 :: Boundary Double -> Stencil DIM2 Double -> Stencil DIM2 Double -> Array U DIM2 Double -> Array D DIM2 Double altMapStencil2 !bd !s1 !s2 !arr = traverse2 (mapStencil2 bd s1 arr) (mapStencil2 bd s2 arr) (\ e _ -> e) (\ get1 get2 (e :. i :. j) -> (if even i then get1 else get2) (e :. i :. j) )

This function needs to be inlined (with a pragma) and the bang annotations on arguments are there to improve optimisation opportunities.

The iteration step

The main relaxLaplace iteration step involves the following (where r and b are the previous red and black arrays)

  • Calculating a new version of r using stencils over b r1 = smap (/4) $ altMapStencil2 (BoundConst 0) leftSt rightSt b
  • Over-relaxation of this taking weighted sums (using r and r1) r2 = szipWith weightedSum r r1 where weightedSum old new = (1-omega)*old + omega*new
  • Reset the boundaries to get the new version of r (r’) r' = szipWith (+) redBoundValue -- boundary resetting $ szipWith (*) redBoundMask r2 -- boundary clearing
  • Do similar steps for calculating b’ but starting with stencils over r’ (not r) and switching the left and right stencils

This is combined in the following monad computation (where r and b are the old arrays). The monad is necessary because we want to use computeP to ensure that the final returned arrays are manifest.

do r' <- computeP $ relaxStep r b redBoundValue redBoundMask leftSt rightSt b' <- computeP $ relaxStep b r' blackBoundValue blackBoundMask rightSt leftSt ...

which uses

relaxStep !arrOld !arrNbs !boundValue !boundMask !stencil1 !stencil2 = szipWith (+) boundValue $ szipWith (*) boundMask $ szipWith weightedSum arrOld $ smap (/4) $ altMapStencil2 (BoundConst 0) stencil1 stencil2 arrNbs weightedSum !old !new = (1-omega)*old + omega*new

The first argument for relaxStep is the old (red or black) array we are calculating an update for, and the second argument is the neighbour array to use stencils on. The old array is needed for the over-relaxation step with weightedSum.

It is also worth pointing out that we have the over-relaxation step being done before the two boundary resetting steps, but this could just as easily be done after the boundary resetting as it does not make a difference to the final array produced.

Laplace with Red-Black and Stencils

Finally the main function (solveLaplace) sets up the initial arrays and passes them to the function with the main loop (iterateLaplace)

> solveLaplace:: > Monad m > => Int -- ^ Number of iterations to use. > -> Double -- ^ weight for over relaxing (>0.0 and <2.0) > -> Array U DIM2 Double -- ^ Boundary value mask. > -> Array U DIM2 Double -- ^ Boundary values. > -> Array U DIM2 Double -- ^ Initial state. Should have even number of columns > -> m (Array U DIM2 Double) > solveLaplace !steps !omega !arrBoundMask !arrBoundValue !arrInit > do redBoundMask <- computeP $ projectRed arrBoundMask > blackBoundMask <- computeP $ projectBlack arrBoundMask > redBoundValue <- computeP $ projectRed arrBoundValue > blackBoundValue <- computeP $ projectBlack arrBoundValue > redInit <- computeP $ projectRed arrInit > blackInit <- computeP $ projectBlack arrInit > iterateLaplace steps omega redInit blackInit > redBoundValue blackBoundValue redBoundMask blackBoundMask

where

iterateLaplace !steps !omega !redInit !blackInit !redBoundValue !blackBoundValue !redBoundMask !blackBoundMask = go steps redInit blackInit where go 0 !r !b = computeP $ combineRB r b -- return final combined array go n !r !b = do r' <- computeP $ relaxStep r b redBoundValue redBoundMask leftSt rightSt b' <- computeP $ relaxStep b r' blackBoundValue blackBoundMask rightSt leftSt go (n - 1) r' b' {-# INLINE relaxStep #-} relaxStep !arrOld !arrNbs !boundValue !boundMask !stencil1 !stencil2 = szipWith (+) boundValue $ szipWith (*) boundMask $ szipWith weightedSum arrOld $ smap (/4) $ altMapStencil2 (BoundConst 0) stencil1 stencil2 arrNbs {-# INLINE weightedSum #-} weightedSum !old !new = (1-omega)*old + omega*new {-# INLINE iterateLaplace #-} Performance and a New Version

The number of calculations in an iteration of red-black is comparable to the original stencil implementation (with just the weighting operations addded in). Although there are two arrays to update, they are half the size of the original. We would expect optimised performance to be only fractionally slower than the original. The speedup in progress towards convergence can be dramatic (one iteration per 8 of the original for our test examples). So, in principle, this would be a big improvement. Unfortunately optimisation did not seem to be achieving the same speedups as the original and the code was roughly 12 times slower.

After much experimentation it looked as though the inner traverse2 operation of altMapStencil2 was inhibiting the optimisations (fusions with stencil mapping code and subsequent maps and zips).

A better performance was achieved by separating the stencil mapping from the traverse2 for alternate row selection and delaying the alternate row selection until after all the other operations. The new version drops altMapStencil2 and instead simply uses altRows

> altRows :: forall r1 r2 a . (Source r1 a, Source r2 a) > => Array r1 DIM2 a -> Array r2 DIM2 a -> Array D DIM2 a > > altRows !arr1 !arr2 = -- assumes argument arrays with the same shape > traverse2 arr1 arr2 > (\ e _ -> e) > (\ get1 get2 e@(_ :. i :. _) -> > if even i then get1 e else get2 e > ) > > {-# INLINE altRows #-}

The function relaxStep in the following revised version of iterateLaplace has altRows done last, with mapStencil2 applied first (using a different stencil in each alternative)

> iterateLaplace :: > Monad m > => Int > -> Double > -> Array U DIM2 Double > -> Array U DIM2 Double > -> Array U DIM2 Double > -> Array U DIM2 Double > -> Array U DIM2 Double > -> Array U DIM2 Double > -> m (Array U DIM2 Double) > > iterateLaplace !steps !omega !redInit !blackInit > !redBoundValue !blackBoundValue !redBoundMask !blackBoundMask > = go steps redInit blackInit > where > go 0 !r !b = computeP $ combineRB r b -- return final combined array > go n !r !b > = do r' <- computeP > $ relaxStep r b redBoundValue redBoundMask leftSt rightSt > b' <- computeP > $ relaxStep b r' blackBoundValue blackBoundMask rightSt leftSt > go (n - 1) r' b' > > {-# INLINE relaxStep #-} > relaxStep !arrOld !arrNbs !boundValue !boundMask !stencil1 !stencil2 > = altRows (f stencil1) (f stencil2) > where > {-# INLINE f #-} > f s = szipWith (+) boundValue > $ szipWith (*) boundMask > $ szipWith weightedSum arrOld > $ smap (/4) > $ mapStencil2 (BoundConst 0) s arrNbs > > {-# INLINE weightedSum #-} > weightedSum !old !new = (1-omega)*old + omega*new > > {-# INLINE iterateLaplace #-}

This now seems to be only a little slower to run than the original stencil solution (about 4 times slower so about 3 times faster than the previous version of red-black). Thus, with an approximately 8-fold speed up in convergence, this does give an overall improvement.

In order to compile this version, it was necessary to use not just the ghc -O2 flag, but also -fsimpl-tick-factor=1000. The need for this flag was indicated by a ghc compiler bug message.

All the code above with birdfeet ( >) in this (incomplete) literate haskell document is essentially that in the module RedBlackStencilOpt.hs (which has some extra preliminaries and imports and checking of arguments in functions which were elided here for clarity). This code can be found here along with the module RedBlackStencil.hs which contains the first version. These can both be loaded by the wrapper newWrapper.hs which is just an adaptation of the original wrapper to allow for passing the extra parameter.

Acknowledgements and References

There are many numerical methods books covering relevant background mathematics, but online, there are also lecture notes. In particular, on Computational Numerical Analysis of Partial Differential Equations by J.M.McDonough and on Numerical Solution of Laplace Equation by G.E.Urroz. T. Kadin has some tutorial notes with a diagram for the red-black scheme (and an implementation using Fortran 90). There is a useful Repa tutorial online and more examples on parallel array fusion are reported in (Lippmeier et al. 2012).

Lippmeier, Ben, and Gabriele Keller. 2011. “Efficient Parallel Stencil Convolution in Haskell.” In Proceedings of the 4th ACM Symposium on Haskell, 59–70. Haskell ’11. New York, NY, USA: ACM. doi:10.1145/2034675.2034684. http://doi.acm.org/10.1145/2034675.2034684.

Lippmeier, Ben, Manuel Chakravarty, Gabriele Keller, and Simon Peyton Jones. 2012. “Guiding Parallel Array Fusion with Indexed Types.” SIGPLAN Not. 47 (12) (September): 25–36. doi:10.1145/2430532.2364511. http://doi.acm.org/10.1145/2430532.2364511.


Categories: Offsite Blogs

Template project for web dev?

Haskell on Reddit - Thu, 04/24/2014 - 8:54am

I'm looking for a sort of template application/architecture for web dev using haskell. The scotty-starter repository is a nice example of this - though lacking any form of database persistence. I would love to know if there are any similar projects for other frameworks or more complete projects, but my google-fu is failing me here, hence this post.

The goal is to have a small sample application which demonstrates a good architectural style/convention to follow.

submitted by Madsn
[link] [8 comments]
Categories: Incoming News

Well-Typed.Com: Pointwise Lenses

Planet Haskell - Thu, 04/24/2014 - 7:54am
Pointwise Lenses

Lenses are a current hot topic in the Haskell community, with a bunch of packages providing implementations (data-accessor, fclabels, lens, amongst others). Although we will recall definitions, this post is not meant as an introduction to lenses. If you have not worked with lenses before, the talk from Simon Peyton Jones or the blog post by Sebastiaan Visser about fclabels are good starting points.

In this blog post we will propose a generalization to the lens representation used in fclabels and in many other packages (with various minor variations); we will consider the relation to the representation used in lens in a separate section.

If you wanted to follow along, this is the header I am using:

{-# LANGUAGE FlexibleInstances, RankNTypes, TupleSections #-} import Prelude hiding ((.), id, const, curry, uncurry) import Control.Arrow import Control.Applicative import Control.Category import Control.Monad import Control.Monad.Free import Control.Monad.Trans.Class import Data.Functor.Identity import Data.Functor.Compose import Data.Traversable import qualified Data.Traversable as Traversable -- We define some Show instances just for the examples instance Show a => Show (Compose [] Identity a) where show (Compose a) = show a instance Show a => Show (Compose [] (Compose [] Identity) a) where show (Compose a) = show a instance Show a => Show (Identity a) where show (Identity a) = show a Basics

A lens from a to b is a way to get a b from an a, and to modify an a given a modification of b:

data Lens a b = Lens { lensGet :: a -> b , lensModify :: (b -> b) -> (a -> a) }

A simple example is a lens for the first component of a pair:

lensFst :: Lens (a, b) a lensFst = Lens fst first

Importantly, lenses can be composed—they form a category:

instance Category Lens where id = Lens id id Lens g m . Lens g' m' = Lens (g . g') (m' . m) Motivation

Suppose we have a lens from somewhere to a list of pairs:

lensFromSomewhere :: Lens Somewhere [(Int, Char)]

We would like to be able to somehow compose lensFromSomewhere with lensFst to get a lens from Somewhere to [Int]. The obvious thing to do is to try and define

mapLens :: Lens a b -> Lens [a] [b] mapLens (Lens g m) = Lens (map g) _

The getter is easy enough: we need to get a [b] from a [a], and we have a function from b -> a, so we can just map. We get stuck in the modifier, however: we need to give something of type

([b] -> [b]) -> [a] -> [a]

given only a modifier of type (b -> b) -> (a -> a), and there is simply no way to do that.

If you think about it, there is a conceptual problem here too. Suppose that we did somehow manage to define a lens of type

weirdLens :: Lens [(Int, Char)] [Int]

This means we would have a modifier of type

weirdModify :: ([Int] -> [Int]) -> [(Int, Char)] -> [(Int, Char)]

What would happen if we tried

weirdModify (1 :)

to insert one Int into the list? Which (Int, Char) pair would we insert into the original list?

Pointwise lenses

What we wanted, really, is a lens that gave us a [Int] from a [(Int, Char)], and that modified a [(Int, Char)] given a modifier of type Int -> Int: we want to apply the modifier pointwise at each element of the list. For this we need to generalize the lens datatype with a functor f:

data PLens f a b = PLens { plensGet :: a -> f b , plensModify :: (b -> b) -> (a -> a) }

It is easy to see that PLens is strictly more general than Lens: every lens is also a Pointwise lens by choosing Identity for f. Here’s a lens for the first component of a pair again:

plensFst :: PLens Identity (a, b) a plensFst = PLens (Identity . fst) first

Note that the type of the modifier is precisely as it was before. As a simple but more interesting example, here is a lens from a list to its elements:

plensList :: PLens [] [a] a plensList = PLens id map

You can think of plensList as shifting the focus from the set as a whole to the elements of the set, not unlike a zipper.

Composition

How does composition work for pointwise lenses?

compose :: Functor f => PLens g b c -> PLens f a b -> PLens (Compose f g) a c compose (PLens g m) (PLens g' m') = PLens (Compose . fmap g . g') (m' . m)

The modifier is unchanged. For the getter we have a getter from a -> f b and a getter from b -> g c, and we can compose them to get a getter from a -> f (g c).

As a simple example, suppose we have

exampleList :: [[(Int, Char)]] exampleList = [[(1, 'a'), (2, 'b')], [(3, 'c'), (4, 'd')]]

Then we can define a lens from a list of list of pairs to their first coordinate:

exampleLens :: PLens (Compose [] (Compose [] Identity)) [[(a, b)]] a exampleLens = plensFst `compose` plensList `compose` plensList

Note that we apply the plensList lens twice and then compose with plensFst. If we get with this lens we get a list of lists of Ints, as expected:

> plensGet exampleLens exampleList [[1,2],[3,4]]

and we modify pointwise:

> plensModify exampleLens (+1) exampleList [[(2,'a'),(3,'b')],[(4,'c'),(5,'d')]] Category Instance

As we saw in the previous section, in general the type of the lens changes as we compose. We can see from the type of a lens where the focus is: shifting our focus from a list of list, to the inner lists, to the elements of the inner lists:

PLens Identity [[a]] [[a]] PLens (Compose [] Identity) [[a]] [a] PLens (Compose [] (Compose [] Identity)) [[a]] a

However, if we want to give a Category instance then we need to be able to keep f constant. This means that we need to be able to define a getter of type a -> f c from two getters of type a -> f b and b -> f c; in other words, we need f to be a monad:

instance Monad f => Category (PLens f) where id = PLens return id PLens g m . PLens g' m' = PLens (g <=< g') (m' . m)

This is however less of a restriction that it might at first sight seem. For our examples, we can pick the free monad on the list functor (using Control.Monad.Free from the free package):

plensFst' :: PLens (Free []) (a, b) a plensFst' = PLens (Pure . fst) first plensList' :: PLens (Free []) [a] a plensList' = PLens lift map

We can use these as before:

> plensGet id exampleList :: Free [] [[(Int, Char)]] Pure [[(1,'a'),(2,'b')],[(3,'c'),(4,'d')]] > plensGet plensList' exampleList Free [Pure [(1,'a'),(2,'b')],Pure [(3,'c'),(4,'d')]] > plensGet (plensList' . plensList') exampleList Free [Free [Pure (1,'a'),Pure (2,'b')],Free [Pure (3,'c'),Pure (4,'d')]] > plensGet (plensFst' . plensList' . plensList') exampleList Free [Free [Pure 1,Pure 2],Free [Pure 3,Pure 4]]

Note that the structure of the original list is still visible, as is the focus of the lens. (If we had chosen [] for f instead of Free [], the original list of lists would have been flattened.) Of course we can still modify the list, too:

> plensModify (plensFst' . plensList' . plensList') (+1) exampleList [[(2,'a'),(3,'b')],[(4,'c'),(5,'d')]] Comparison to Traversal

An alternative representation of a lens is the so-called van Laarhoven lens, made popular by the lens package:

type LaarLens a b = forall f. Functor f => (b -> f b) -> (a -> f a)

(this is the representation Simon Peyton-Jones mentions in his talk). Lens and LaarLens are isomorphic: we can translate from Lens to LaarLens and back. This isomorphism is a neat result, and not at all obvious. If you haven’t seen it before, you should do the proof. It is illuminating.

A Traversal is like a van Laarhoven lens, but using Applicative instead of Functor:

type Traversal a b = forall f. Applicative f => (b -> f b) -> (a -> f a)

Traversals have a similar purpose to pointwise lenses. In particular, we can define

tget :: Traversal a b -> a -> [b] tget t = getConst . t (Const . (:[])) tmodify :: Traversal a b -> (b -> b) -> (a -> a) tmodify t f = runIdentity . t (Identity . f)

Note that the types of tget and tmodify are similar to types of the getter and modifier of a pointwise lens, and we can use them in a similar fashion:

travFst :: LaarLens (a, b) a travFst f (a, b) = (, b) <$> f a travList :: Traversal [a] a travList = traverse exampleTrav :: Traversal [[(Int, Char)]] Int exampleTrav = travList . travList . travFst

As before, we can use this traversal to modify a list of list of pairs:

> tmodify exampleTrav (+1) exampleList [[(2,'a'),(3,'b')],[(4,'c'),(5,'d')]]

However, Traversals and pointwise lenses are not the same thing. It is tempting to compare the f parameter of the pointwise lens to the universally quantified f in the type of the Traversal, but they don’t play the same role at all. With pointwise lenses it is possible to define a lens from a list of list of pairs to a list of list of ints, as we saw; similarly, it would be possible to define a lens from a tree of pairs to a tree of ints, etc. However, the getter from a traversal only ever returns a single, flat, list:

> tget exampleTrav exampleList [1,2,3,4]

Note that we have lost the structure of the original list. This behaviour is inherent in how Traversals work: every element of the structure is wrapped in a Const constructor and are then combined in the Applicative instance for Const.

On the other hand, the Traversal type is much more general than a pointwise lens. For instance, we can easily define

mapM :: Applicative m => (a -> m a) -> [a] -> m [a] mapM = travList

and it is not hard to see that we will never be able to define mapM using a pointwise lens. Traversals and pointwise lenses are thus incomparable: neither is more general than the other.

In a sense the generality of the Traversal type is somewhat accidental, however: it’s purpose is similar to a pointwise lens, but it’s type also allows to introduce effectful modifiers. For pointwise lenses (or “normal” lenses) this ability is entirely orthogonal, as we shall see in the next section.

(PS: Yes, traverse, travList and mapM are all just synonyms, with specialized types. This is typical of using the lens package: it defines 14 synonyms for id alone! What you take away from that is up to you :)

Generalizing further

So far we have only considered pure getters and modifiers; what about effectful ones? For instance, we might want to define lenses into a database, so that our getter and modifier live in the IO monad.

If you look at the actual definition of a lens in fclabels you will see that it generalises Lens to use arrows:

data GLens cat a b = GLens { glensGet :: cat a b , glensModify :: cat (cat b b, a) a }

(Actually, the type is slightly more general still, and allows for polymorphic lenses. Polymorphism is orthogonal to what we are discussing here and we will ignore it for the sake of simplicity.) GLens too forms a category, provided that cat satisfies ArrowApply:

instance ArrowApply cat => Category (GLens cat) where id = GLens id app (GLens g m) . (GLens g' m') = GLens (g . g') (uncurry (curry m' . curry m)) const :: Arrow arr => c -> arr b c const a = arr (\_ -> a) curry :: Arrow cat => cat (a, b) c -> (a -> cat b c) curry m i = m . (const i &&& id) uncurry :: ArrowApply cat => (a -> cat b c) -> cat (a, b) c uncurry a = app . arr (first a)

The ArrowApply constraint effectively means we have only two choices: we can instantiate cat with ->, to get back to Lens, or we can instantiate it with Kleisli m, for some monad m, to get “monadic” functions; i.e. the getter would have type (isomorphic to) a -> m b and the modifier would have type (isomorphic to) (b -> m b) -> (a -> m a).

Can we make a similar generalization to pointwise lenses? Defining the datatype is easy:

data GPLens cat f a b = GPLens { gplensGet :: cat a (f b) , gplensModify :: cat (cat b b, a) a }

The question is if we can still define composition.

Interlude: Working with ArrowApply

I personally find working with arrows horribly confusing. However, if we are working with ArrowApply arrows then we are effectively working with a monad, or so Control.Arrow tells us. It doesn’t however quite tell us how. I find it very convenient to define the following two auxiliary functions:

toMonad :: ArrowApply arr => arr a b -> (a -> ArrowMonad arr b) toMonad f a = ArrowMonad $ app . (const (f, a)) toArrow :: ArrowApply arr => (a -> ArrowMonad arr b) -> arr a b toArrow act = app . arr (\a -> (unArrowMonad (act a), ())) where unArrowMonad (ArrowMonad a) = a

Now I can translate from an arrow to a monadic function and back, and I just write monadic code. Right, now we can continue :)

Category instance for GPLens

Since the type of the modifier has not changed at all from GLens we can concentrate on the getters. For the identity we need an arrow of type cat a (f a), but this is simply arr return, so that is easy.

Composition is trickier. For the getter we have two getters of type cat a (f b) and cat b (f c), and we need a getter of type cat a (f c). As before, it looks like we need some kind of monadic (Kleisli) composition, but now in an arbitrary category cat. If you’re like me at this stage you will search Hoogle for

(ArrowApply cat, Monad f) => cat a (f b) -> cat b (f c) -> cat a (f c)

… and find nothing. So you try Hayoo and again, find nothing. Fine, we’ll have to try it ourselves. Let’s concentrate on the monadic case:

compM :: (Monad m, Monad f) => (a -> m (f b)) -> (b -> m (f c)) -> a -> m (f c) compM f g a = do fb <- f a _

so far as good; fb has type f b. But now what? We can fmap g over fb to get something of type f (m (f c)), but that’s no use; we want that m on the outside. In general we cannot commute monads like this, but if you are a (very) seasoned Haskell programmer you will realize that if f happens to be a traversable functor then we can flip f and m around to get something of type m (f (f c)). In fact, instead of fmap and then commute we can use mapM from Data.Traversable to do both in one go:

compM :: (Monad m, Monad f, Traversable f) => (a -> m (f b)) -> (b -> m (f c)) -> a -> m (f c) compM f g a = do fb <- f a ffc <- Traversable.mapM g fb _

Now we’re almost there: ffc has type f (f c), we need somthing of type f c; since f is a monad, we can just use join:

compM :: (Monad m, Monad f, Traversable f) => (a -> m (f b)) -> (b -> m (f c)) -> a -> m (f c) compM f g a = do fb <- f a ffc <- Traversable.mapM g fb return (join ffc)

We can use the two auxiliary functions from the previous section to define Kleisli composition on arrows:

compA :: (ArrowApply cat, Monad f, Traversable f) => cat a (f b) -> cat b (f c) -> cat a (f c) compA f g = toArrow (compM (toMonad f) (toMonad g))

And now we can define our category instance:

instance (ArrowApply cat, Monad f, Traversable f) => Category (GPLens cat f) where id = GPLens (arr return) app GPLens g m . GPLens g' m' = GPLens (g' `compA` g) (uncurry (curry m' . curry m))

Note that the Traversable constraint comes up now because we need to commute the “effects” of two monads: the monad f from the structure that we are returning (be it a list or a tree or..) and the monad m implicit in the arrow. In a Traversal these two are somehow more closely coupled. In particular, if we lift a (pure) pointwise lens PLens to the more general GPLens, by picking Identity for f, the Traversable constraint is trivially satisfied.

Categories: Offsite Blogs

A Quick Look at Haskell

del.icio.us/haskell - Thu, 04/24/2014 - 6:58am
Categories: Offsite Blogs

Generalising `Control.Lens.Iso.mapping`

Haskell on Reddit - Thu, 04/24/2014 - 5:30am

The lens package includes this function in the Control.Lens.Iso module:

-- | This can be used to lift any 'Iso' into an arbitrary 'Functor'. mapping :: (Functor f, Functor g) => AnIso s t a b -> Iso (f s) (g t) (f a) (g b) mapping k = withIso k $ \ sa bt -> iso (fmap sa) (fmap bt)

I'd like to generalise it so I can lift any Iso over any Setter.

whatIWant :: ASetter {-mumble-} -> AnIso {-mumble-} -> Iso s t a b

Then I could write e.g.

mappingFirst :: AnIso s t a b -> Iso (s,r) (t,r) (a,r) (b,r) mappingFirst = whatIWant _1

But I can't manage it.

Here's how far I've got:

-- these isomorphisms convert one way only: useless uselessIsos :: ASetter s t a b -> AnIso a b b a -> Iso s t t s uselessIsos aSetter anIso = withIso anIso (\there back -> iso (aSetter %~ there) (aSetter %~ back)) -- must pass the setter twice, at different types: error-prone errorProne :: ASetter u c s a -> ASetter d v b t -> AnIso s t a b -> Iso u v c d errorProne aSetter bSetter anIso = withIso anIso (\there back -> iso (aSetter %~ there) (bSetter %~ back)) mappingFirst = errorProne _1 _1

If I inline _1 in the definition, the types work out:

mappingFirst :: AnIso s t a b -> Iso (s,r) (t,r) (a,r) (b,r) mappingFirst anIso = withIso anIso (\there back -> iso (_1 %~ there) (_1 %~ back))

The problem I think is how to properly generalise the types in whatIWant. Or perhaps I'm missing something obvious. (I half-expect the function I want to be hiding in a module I didn't look in.) Any ideas?

submitted by dave4420
[link] [13 comments]
Categories: Incoming News

Haskell-Beginners Info Page

del.icio.us/haskell - Thu, 04/24/2014 - 4:54am
Categories: Offsite Blogs