# News aggregator

### Opening for OpenGL, C++ Development.

### Magnus Therning: More Visitor (in Python)

Right after writing the previous post on the Visitor pattern in Python I picked up another paper on the same topic, Visitor Combination and Traversal Control. Of course this one also used Java for its examples, so once again I decided to use Python to explore the ideas presented.

The first part of the paper is all about writing small visitors that then are combined into more complicated ones. This part is nice but not that exciting. The interesting bit is when it gets to controlling traversal, which means it’s possible to remove the traversal code that usually appear in the accept method each visited type has to implement. Let’s see how that can look in Python.

The full code in this post is available at https://gist.github.com/magthe/beddad5c627946f28748.

First we need a structure to traverse, a simple tree will do.

class Tree(Visitable): def __init__(self, left, right): self.left = left self.right = right class Leaf(Visitable): def __init__(self, value): self.value = value def build_tree(): l0 = Leaf(0) l1 = Leaf(1) t0 = Tree(l0, l1) l2 = Leaf(2) t1 = Tree(t0, l2) l3 = Leaf(3) l4 = Leaf(4) t2 = Tree(l3, l4) return Tree(t1, t2)But before this we really should define Visitor, the base class for visitors, and Visitable, the base class of everything that can be visited.

class Visitor: def visit(self, obj): getattr(self, 'visit_' + obj.__class__.__name__)(obj) def visit_Tree(self, t): pass def visit_Leaf(self, l): pass class Visitable: def accept(self, visitor): visitor.visit(self)We’ll throw in a visitor for printing the whole tree too:

class Print(Visitor): def visit_Tree(self, t): print('Tree (%s)' % hex(id(t))) def visit_Leaf(self, l): print('Leaf (%s): %i' % (hex(id(l)), l.value))Due to the lack of traversal in the accept methods it’s easy to be underwhelmed by the Print visitor:

In [32]: build_tree().accept(Print()) Tree (0x7f1680681a90)To address this we first need a visitor combinator that runs two visitors in sequence. Unsurprisingly we’ll call it Sequence. Its constructor takes two visitors, and for each node in the tree it passed each one to the node.accept method.

class Sequence(Visitor): def __init__(self, first, then): self.first = first self.then = then def visit_Tree(self, t): t.accept(self.first) t.accept(self.then) def visit_Leaf(self, l): l.accept(self.first) l.accept(self.then)The next building block is a visitor that descends one level down from a Tree node.

class All(Visitor): def __init__(self, v): self.v = v def visit_Tree(self, t): t.left.accept(self.v) t.right.accept(self.v)At this point it’s worth noting that the name All probably isn’t very well
chosen, since we don’t really get *all* nodes:

We only descend one level, but we still keep the name since that’s the name they use in the paper.

With this in place it does become possible to create combinations that do traverse the full tree though. It even becomes rather simple. Traversing top-down is a simple matter of using a sequence that ends with All, and bottom-up is a matter of using a sequence starting with All.

class TopDown(Sequence): def __init__(self, v): Sequence.__init__(self, v, All(self)) class BottomUp(Sequence): def __init__(self, v): Sequence.__init__(self, All(self), v)First top-down:

In [34]: build_tree().accept(TopDown(Print())) Tree (0x7f1680681ef0) Tree (0x7f16806814a8) Tree (0x7f16806813c8) Leaf (0x7f1680681278): 0 Leaf (0x7f1680681550): 1 Leaf (0x7f1680681a90): 2 Tree (0x7f1680681f28) Leaf (0x7f1680681ba8): 3 Leaf (0x7f1680681a20): 4Then bottom-up:

In [35]: build_tree().accept(BottomUp(Print())) Leaf (0x7f1680681ba8): 0 Leaf (0x7f16806814a8): 1 Tree (0x7f1680681a90) Leaf (0x7f16806813c8): 2 Tree (0x7f1680681550) Leaf (0x7f1680681278): 3 Leaf (0x7f16806a1048): 4 Tree (0x7f16806a1198) Tree (0x7f16806a1390)That’s all rather cute I think.

### Deploy Haskell application

### do your lenses even do notation?

### Mike Izbicki: do your lenses even do notation?

It’s round 5 of typeparams versus GHC. We’ll be extending our Functor and Applicative classes to define a new Monad class. It’s all pretty simple if you just remember: lensified monads are like burritos with fiber optic cables telling you where to bite next. They’re also just monoids in the category of lens-enhanced endofunctors. Piece of cake.

some naughty extensionsWe’ll be using all the same extensions as before:

> {-# LANGUAGE TemplateHaskell #-} > {-# LANGUAGE ScopedTypeVariables #-} > {-# LANGUAGE KindSignatures #-} > {-# LANGUAGE TypeFamilies #-} > {-# LANGUAGE MultiParamTypeClasses #-} > {-# LANGUAGE UndecidableInstances #-} > {-# LANGUAGE FlexibleInstances #-} > {-# LANGUAGE RankNTypes #-}But we’ll be adding some pretty nasty ones today:

> {-# LANGUAGE OverlappingInstances #-} > {-# LANGUAGE RebindableSyntax #-}We need RebindableSyntax to get do notation, but OverlappingInstances is just a product of the Monad class’s definition. I’ll give infinite haskell points to anyone who can refactor this code so we don’t need the extension!

We’ll also be needing all of our previous work on Functors and Applicatives. It has been uploaded to hackage and is sitting in the appropriate modules:

> import Control.Category > import Prelude hiding ( (.), id, Functor(..), Applicative(..), Monad(..) ) > import qualified Prelude as P > import GHC.Exts > import Data.Params > import Data.Params.Applicative > import Data.Params.FunctorAnd we’re off!

joins and cojoinsWe will define our monads in terms of their join function. In the standard libraries, join has the type:

join :: m (m a) -> m aThe input has the same type as the output, except that the Monad m is repeated twice. There are two differences in the lensified join function: First, the monad we’re working with might be nested arbitrarily deeply in other data types. Second, the argument it is monadic in might not be the last one. Here is an example of what the join type signature would look like for the Left Either monad sitting within a Maybe Monad:

join :: TypeLens Base (Param_a (Param_a Base)) -> Maybe (Either (Either String Int) Int) -> Maybe (Either String Int)Since we’re all wannabe category theorists here, we’ll create a CoJoin type family that transforms the output of the join function by duplicating the type at location specified by the lens:

> type family CoJoin (lens :: * -> Constraint) t > type instance CoJoin lens t > = SetParam' > lens > ( SetParam' > ( Objective lens ) > ( GetParam lens t ) > ( GetParam (RemoveObjective lens) t ) > ) > t*(We covered the Objective and RemoveObjective families in a previous post. As a reminder, the Objective family returns the innermost type lens from our input, and the RemoveObjective family returns the lens that results when the innermost lens is taken away.)*

CoJoin only has one instance, so we could have just used a type synonym. That would make debugging harder, however. The advantage of a type family is that when we ask GHCi what the type is, it will perform the substitutions for us. For example:

ghci> :t undefined :: CoJoin (Param_a Base) (Maybe (Either String Int)) :: Maybe (Maybe (Either String Int)) ghci> :t undefined :: CoJoin (Param_a (Param_a Base)) (Maybe (Either String Int)) :: Maybe (Either (Either String Int) Int) making the monadNow we’re ready to see our new Monad class:

> class Applicative lens tfb => Monad lens tfb where > join :: > ( tffb ~ CoJoin lens tfb > ) => TypeLens Base lens > -> tffb -> tfbThe Left and Right Either instances are:

> instance Monad (Param_a Base) (Either a b) where > join lens (Left (Left a)) = Left a > join lens (Left (Right b)) = Right b > join lens (Right b) = Right b > instance Monad (Param_b Base) (Either a b) where > join lens (Right (Right b)) = Right b > join lens (Right (Left a)) = Left a > join lens (Left a) = Left aAnd here are some examples of join in action:

ghci> join _b (Right $ Right "monads") :: Either String String Right "monads" ghci> join _b (Right $ Left "are") :: Either String String Left "are" ghci> join _a (Left $ Left "so") :: Either String String Left "so" ghci> join _a (Right "awesome") :: Either String String Right "awesome"The instances above don’t consider the case when our lenses point inside of the Either type. We’ll need to define two new recursive instances to handle this case. These instances are the reason we needed the OverlappingInstances language extension:

> instance > ( Monad p a > , Either (CoJoin p a) b ~ CoJoin (Param_a p) (Either a b) -- follows from the lens laws > ) => Monad (Param_a p) (Either a b) > where > > join lens (Left a) = Left $ join (zoom lens) a > join lens (Right b) = Right b > instance > ( Monad p b > , Either a (CoJoin p b) ~ CoJoin (Param_b p) (Either a b) -- follows from the lens laws > ) => Monad (Param_b p) (Either a b) > where > > join lens (Left a) = Left a > join lens (Right b) = Right $ join (zoom lens) bThe equality constraints in the instances above are implied by the lens laws. As we discussed yesterday, with the type rules language extension, those constraints could be removed completely, making the code a bit nicer.

Here are some examples of using join in the nested case:

ghci> join (_a._b) (Left $ Right $ Right "lenses") :: Either (Either a String) b Left (Right "lenses") ghci> join (_a._b) (Left $ Right $ Left "are") :: Either (Either String b) b Left (Left "are") ghci> join (_b._b) (Left "neat") :: Either String (Either a String) Left "neat"Sometimes we will get the same answer if we join in two separate locations. In the first example below, we join the second two Right constructors, whereas in the second example, we join the first two Right constructors. The results are the same:

ghci> join (_b._b) (Right $ Right $ Right "easy") :: Either a (Either a String) Right (Right "easy") ghci> join _b (Right $ Right $ Right "peasy") :: Either a (Either a String) Right (Right "peasy")We’ll also be needing a Monad instance for Maybe, so here it is:

> instance Monad (Param_a Base) (Maybe a) where > join lens Nothing = Nothing > join lens (Just Nothing) = Nothing > join lens (Just (Just a)) = Just a > instance > ( Monad p a > , Maybe (CoJoin p a) ~ CoJoin (Param_a p) (Maybe a) -- follows from the lens laws > ) => Monad (Param_a p) (Maybe a) > where > join lens Nothing = Nothing > join lens (Just a) = Just $ join (zoom lens) a bindFrom join and our Applicative instance, we can derive our monadic bind function. We don’t want to use the traditional (>>=) operator for bind just yet. We will need to do something fancy with it to make do notation work out. So instead, we will use the (\\=) operator for bind. Its definition is:

(\\=) :: ( Monad lens tb , a ~ GetParam lens tfa , {- ... lens laws go here ... -} ) => ta -> (a -> tb) -> TypeLens Base lens -> tb > infixl 1 \\= > (m \\= f) lens = join lens $ fmap lens f mWe will create the “minus bind operators” in the same way we created minus operators for the Applicative class. Remember, the minus sign points to the parameters that will get a lens applied to them because they are “minus a lens”. These minus operators are defined as:

> infixl 1 \\=- > infixl 1 -\\=- > infixl 1 -\\= > (m \\=- f) lens = ( m \\= \a -> f a $ objective lens ) lens > (m -\\=- f) lens = ( m lens \\= \a -> f a $ objective lens ) lens > (m -\\= f) lens = ( m lens \\= \a -> f a ) lens example timeFor our example, we’ll build a simple monadic filter. The filterSmall function below sits in the Either Monad, but we’ll be using Left to represent successes (the input passes through the filter), and Right to represent failure (the input doesn’t pass through).

> filterSmall :: (Show a, Ord a) => a -> a -> Either a String > filterSmall k x = if x > k > then Left x > else Right $ show x ++ " is too small"We can call our function using the monadic bind by:

> chain1 :: Either Int String > chain1 = at _a $ Left 20 \\= filterSmall 10 ghci> chain1 Left 20Instead of using the Left constructor, we can make things a little more generic by using the return function. As usual, it is equivalent to pure:

> return :: Monad lens t => GetParam lens t -> TypeLens Base lens -> t > return = pureSine pure’s last parameter is a type lens, we must use the left-minus (-\\=) variant of bind to sequence the computation:

> chain2 :: Either Int String > chain2 = at _a $ return 20 -\\= filterSmall 10 ghci> chain2 Left 20Similarly, all the bind operators take a type lens as their last parameter. So any future binds must also use left-minus bind:

> chain3 :: Either Int String > chain3 = at _a $ return 20 -\\= filterSmall 10 -\\= filterSmall 15 ghci> chain3 Left 20And so on:

> chain4 :: Either Int String > chain4 = at _a $ return 20 -\\= filterSmall 10 -\\= filterSmall 15 -\\= filterSmall 25 ghci> chain4 Right "20 is too small"We can easily nest our monads. Let’s put all of the computations above inside a Maybe wrapper. All we have to do is change the type signature and the lens:

> chain2' :: Maybe (Either Int String) > chain2' = at (_a._a) $ return 20 -\\= filterSmall 10 > chain3' :: Maybe (Either Int String) > chain3' = at (_a._a) $ return 20 -\\= filterSmall 10 -\\= filterSmall 15 > chain4' :: Maybe (Either Int String) > chain4' = at (_a._a) $ return 20 -\\= filterSmall 10 -\\= filterSmall 15 -\\= filterSmall 25 do the notationWe’re using the RebindableSyntax language extension to construct a custom do notation. We do this by defining our own (>>=) operator. The most generic bind operator we have is the double minus bind (-\\=-). Sometimes we will want to feed a lens to both sides of the bind, so that’s what we’ll use:

> infixl 1 >>= > (m >>= f) lens = (m -\\=- f) lensNotice that our (>>=) operator and the one from Prelude take different numbers of arguments! GHC is awesome enough that this is not a problem.

RebindableSyntax also requires us to define functions for failed pattern matching and if statements. Our definitions will be pretty simple:

> fail = error > ifThenElse False _ f = f > ifThenElse True t _ = tNow, we can take our chain2′ function above and rewrite it in do notation. Here it is again for easy reference:

chain2' :: Maybe (Either Int String) chain2' = at (_a._a) $ return 20 -\\= filterSmall 10First, rewrite it to use (-\\=-) instead of (-\\=) by causing the right hand side to take a lens parameter even though it won’t use it:

> chain2'' :: Maybe (Either Int String) > chain2'' = at (_a._a) $ return 20 -\\=- (\x lens -> filterSmall 10 x)Then, rewrite it using do notation:

> chain2''' :: Maybe (Either Int String) > chain2''' = at (_a._a) $ do > x <- return 20 > \lens -> filterSmall 10 xIt looks a little bit nicer if we use const to absorb the lens parameter:

> chain2'''' :: Maybe (Either Int String) > chain2'''' = at (_a._a) $ do > x <- return 20 > const $ filterSmall 10 xHere is our other examples converted into do notation using the same technique:

> chain3''' :: Maybe (Either Int String) > chain3''' = at (_a._a) $ do > x <- return 20 > y <- const $ filterSmall 10 x > const $ filterSmall 15 y > chain4'' :: Maybe (Either Int String) > chain4'' = at (_a._a) $ do > x <- return 20 > y <- const $ filterSmall 10 x > z <- const $ filterSmall 15 y > const $ filterSmall 25 zAnd here is a more complicated expression with a nested do:

> chain5 :: Either a (Either a (Maybe (Either Int String))) > chain5 = at (_b._b._a._a) $ do > x <- return 20 > y <- do > a <- const $ filterSmall x 10 > b <- const $ filterSmall 1 3 > return $ a+b > z <- const $ filterSmall y x > return $ z-xBut there is still a limitation. Due to the way the types work out, the first line of a do block must always be a return statement when using the at function to specify our lens. This is a by product of the extra lens parameter our (>>=) operator is passing around. Fortunately, we can automate this construction with the following function:

> atM lens m = at (removeObjective lens) $ do > return $ at (objective lens) $ mThis lets us rewrite chain5 as:

> chain5' :: Either a (Either a (Maybe (Either Int String))) > chain5' = atM (_b._b._a._a) $ do > let x = 20 > y <- do > a <- const $ filterSmall x 10 > b <- const $ filterSmall 1 3 > return $ a+b > z <- const $ filterSmall y x > return $ z-xNow we fully support do notation!

Hooray!!

Tune in next time…How do we get rid of those ugly const functions?

Can optimus prime use type lenses to save our purity from the effects of the evil decepticons?

Does any one actually care about lensified arrow-do?

Stay tuned to find out.

### Functional Jobs: Developer / DevOps Engineer at Klarna (Full-time)

**Our FRED teams** are responsible for building and operating Klarna’s highly scalable and highly available purchase-accepting system. By combining Erlang, RIAK and RabbitMQ this business critical, multi-node, no-master system handles our exponential growth of real time transactions. The teams have end-to-end responsibility and believe in relentless automation, shipped code and reusability.

**We are looking** for a functional programmer that wants to take on some operations responsibilities and who believes that you should be responsible for what you create. The role will primarily involve developing infrastructure for logging, monitoring, testing, deployment and operations in order to support the system and contributing feature teams, but a willingness to understand the underlying business-logic and when necessary contribute some feature development is also important. We are looking for someone who can grow into being a Hamiltonian salty mechanic in a mission critical helicopter, so to speak.

**Required**

- B.Sc/M.Sc in Computer Science
- experience with a functional programming language (Erlang, a LISP, an ML, Haskell, etc)
- comfortability with shell scripting
- extremely high attention to detail
- intellectual curiosity
- a preference for simple, elegant, and reusable solutions
- a get-things-done attitude

**Nice to have**

- some experience with configuration management (Chef, Puppet, ansible, cfengine, etc)
- some exposure to Java, Erlang or Ruby
- experience with graphite, collectd
- experience with virtualization (CloudStack, AWS, etc)
- nagios/op5 experience
- experience with Splunk API
- RabbitMQ experience
- Riak experience (or experience with distributed databases NoSQL/SQL)
- proven technical writing ability

**Would be cool**

- history of giving entertaining technical talks at conferences

**If you have any question** please email Philip Alsén at: philip [dot] alsen [at] klarna [dot] com. Apply as soon as possible since we are working continuously with the recruitment process.

**Location**
Stockholm, Sweden

Get information on how to apply for this position.

### Erik de Castro Lopo: Moving from Wai 2.X to 3.0.

Michael Snoyman has just released version 3.0 of Wai, the Haskell Web Application Interface library which is used with the Yesod Web Framework and anything that uses the Warp web server. The important changes for Wai are listed this blog post. The tl;dr is that removing the Conduit library dependency makes the Wai interface more easily usable with one of the alternative Haskell streaming libraries, like Pipes, Stream-IO, Iterator etc.

As a result of the above changes, the type of a web application changes as follows:

-- Wai > 2.0 && Wai < 3.0 type Application = Request -> IO Response -- Wai == 3.0 type Application = Request -> (Response -> IO ResponseReceived) -> IO ResponseReceived
Typically a function of type **Application** will be run by the Warp
web server using one of **Warp.run** or associated functions which
have type signatures of:

Its important to note that the only thing that has changed about these Warp
functions is the **Application** type.
That means that if we have a function **oldWaiApplication** that we
want to interface to the new version of Wai, we can just wrap it with the
following function:

and use **newWaiApplication** in place of **oldWaiApplication**
in the call to whichever of the Warp **run** functions you are using.

### non-exhaustive pattern match(es)?

### JOB: AHRC Doctoral Studentship in ComputationalMusicology

### System.Directory.removeDirectoryRecursive and symlinks

### Call for participation: HLPP 2014 - 7th Symposium on High-Level Parallel Programming and Applications

### New gtk2hs 0.12.4 release

Thanks to John Lato and Duncan Coutts for the latest bugfix release! The latest packages should be buildable on GHC 7.6, and the cairo package should behave a bit nicer in ghci on Windows. Thanks to all!

~d