# News aggregator

### What's the deal with Yesod?

I used to feel that Yesod had a lot of promise. But it has really failed to deliver. Major failings:

- still no blog system, after years of discussion about it. Never mind things like CRUD screens. Shouldn't these be derivable from the Persistent model?
- highly, highly opinionated at the core level. This wouldn't be so bad, but it's also wrong very often. I know this is just my opinion. But I also know that when I make opinionated choices in my libraries, I do them in type classes and provide a way to override my choice. Yesod abandoned that principle a long time ago.
- Highly inconsistent and type un-safe interfaces. This is especially scary in the Auth system. A "Creds master" is a text token and list of text key-values. The semantics of the key-value pairs depends on the Auth plugin that sets the Creds master. Really? String typing? In 2014? In a strongly typed language? There are a
**lot**of examples like this, especially in the Auth system. The bizarre thing is, Yesod already uses TypeFamilies all over the place, so there is literally no reason to pass around a blob of texts. - type safe URLs are over-hyped. Especially for a "RESTful" framework. Type safe URLs just aren't useful when your hrefs are dynamically generated by JavaScript.
- Having a "Foundation" module splits your project in two -- the stuff that imports Foundation, and the stuff Foundation imports. This division is really painful. Moving code from one side of the Foundation to the other very often breaks code, just because the Import.hs module doesn't work.
- Actually, the whole Import idea is misguided. I end up having to import parts of Prelude constantly, especially on the framework side of the Foundation boundary.
- There are like 5 different ways to load a widget. The pro's and con's are not explained anywhere, including the source code.
The documentation is actually really really bad. Consider:

-- | Determine the ID associated with the set of credentials.

getAuthId :: Creds master -> HandlerT master IO (Maybe (AuthId master))

-- | Retrieves user credentials, if user is authenticated.

By default, this calls defaultMaybeAuthId to get the user ID from the session. This can be overridden to allow authentication via other means, such as checking for a special token in a request header. This is especially useful for creating an API to be accessed via some means other than a browser.

maybeAuthId :: HandlerT master IO (Maybe (AuthId master))

Notice that maybeAuthId does not return a Creds master. Notice that 'getAuthId' determines the ID associated with a set of credentials. Notice that this means having to read the spaghetti code to figure out what is actually going on. This is even worse, since the semantics for credentials aren't even defined in Yesod.Auth. They're defined by plugins.

- The documentation is even worse than that. If you Google for Yesod function names, Google ends up pointing you toward old versions. Especially since a lot of the functions have become private in newer versions (so they don't get documented on Hackage). Fair enough, but Yesod was always a bit on the spaghetti side, and this just pours on thick, inky squid sauce. In other words,
*obscure*. - Multitudes of special cases. Why is whamlet a widget quasiquoter, but not julius?
- The community is not very good. It's the weakest community I've seen from a "major" Haskell project.

Strengths:

- Hamlet is sweet. I actually do like type safe URLs. And the templating language is nice.
- Persistent: I can take it or leave it, honestly. But it's decent enough to count as a strength.
- esqueleto: an "associated" project.

I'm 100% sure there are other strengths. And that I am feeling uncharitable this evening.

Is Yesod a viable platform? Will it ever be one? Or is it just a vehicle for Michael Snoyman to write a book?

submitted by 2piix[link] [46 comments]

### Exceptions and monad transformers

### Yesod Web Framework: Exceptions and monad transformers

Duncan Coutts kicked off a discussion on the core libraries mailing list in April about exception handling in monad transformers. We made a lot of headway in that discussion, and agreed to bring up the topic again on the libraries mailing list, but unfortunately none of us ever got around to that. So I'm posting a summary of that initial discussion (plus some of my own added thoughts) to hopefully get a broader discussion going.

The initial thread kicked off with a link to ghc's ExceptionMonad typeclass, which encapsulates the ability to catch exceptions, mask async exceptions, and guarantee cleanup actions (a.k.a. bracket/finally). The question is: is there a canonical way to do the same thing, without depending on the ghc library?

As is usually the case in the Haskell ecosystem, the answer is that there are about five different packages providing this functionality. I'd break them down into two categories:

- Packages which define a typeclass (or set of typeclasses) specifically for exception handling. Such examples include MonadCatchIO-mtl, MonadCatchIO-transformers, and exceptions.
- Packages which define a generic way to embed a monad transformer inside the value, and thereby perform
*any*control operation in the base monad. Examples are monad-peel and monad-control (or if you want to go really far in time, neither).

Fortunately, most of those options have been deprecated in favor of alternatives. Today, there are really two choices: exceptions and monad-control. I'd like to describe these in a bit more detail, and contrast some of the pluses and minuses of both approaches. My overall goals are twofold:

- Get more knowledge out there about the advantages of the two libraries.
- Work towards a community consensus on when each library should be used.

I'm interested in the latter point, since having a consistent usage of the MonadBaseControl vs MonadMask typeclasses in various packages makes it easier to reuse code.

Note: I don't mean to take credit for the ideas that are expressed in this blog post. As I said, it's a combination of summary of a previous discussion (mostly amongst Duncan, Edward, and myself) and a few new thoughts from me.

exceptionsThe exceptions package exposes three typeclasses, all specifically geared at exception handling, and each one incrementally more powerful than the previous one. MonadThrow is for any monad which can throw exceptions. Some examples of instances are:

- IO, where the exception becomes a runtime exception.
- Either, where the exception becomes the Left value.
- Maybe, where an exception results in Nothing.
- Any monad transformer built on top of one of those. (Note also that there's a special CatchT transformer, which keeps the exception in the transformer itself.)

In addition to just throwing exceptions, you often want to be able to catch exceptions as well. For that, the MonadCatch typeclass is available. However, some monads (in particular, Maybe) cannot be MonadCatch instances, since there's no way to recover the thrown exception from a Nothing.

The final typeclass is MonadMask, which allows you to guarantee that certain actions are run, even in the presence of exceptions (both synchronous and asynchronous). In order to provide that guarantee, the monad stack must be able to control its flow of execution. In particular, this excludes instances for two categories of monads:

- Continuation based monads, since the flow of execution may ignore a callback entirely, or call it multiple times. (For more information, see my previous blog post.)
- Monads with multiple exit points, such as ErrorT over IO.

And this is the big advantage of the exceptions package vs MonadCatchIO: by making this distinction between catching and masking, we end up with instances that are well behaved, and finally functions that guarantee cleanup happens once, and only once.

One design tradeoff is that all exceptions are implicitly converted to SomeException. An alternate approach is possible, but ends up causing many more problems.

monad-controlmonad-control takes a completely different approach. Let's consider the StateT Int IO monad stack, and consider a function

foo :: StateT String IO IntNow suppose that I'd like to catch any exceptions thrown by foo, using the standard try function (specialized to IOException for simplicity):

tryIO :: IO a -> IO (Either IOException a)Obviously these two functions don't mix together directly. But can we coerce them into working together somehow? The answer lies in exposing the fact that, under the surface, StateT just becomes a function in IO returning a tuple. Working that way, we can write a tryState function:

tryState :: StateT String IO a -> StateT String IO (Either IOException a) tryState (StateT f) = StateT $ \s0 -> do eres <- tryIO $ f s0 return $ case eres of Left e -> (Left e, s0) Right (x, s1) -> (Right x, s1)(Full example on School of Haskell.) The technique here is to:

- Capture the initial state.
- Use tryIO on the raw IO function.
- Case analyze the result, either getting an exception or a successful result and new state. Either way, we need to reconstitute the internal state of the transformer, in the former by using the initial state, in the latter, using the newly generated state.

It turns out that this embedding technique can be generalized in two different ways:

- It applies to just about any IO function, not just exception functions.
- It applies to many different transformers, and to arbitrarily deep layerings of these transformers.

For examples of the power this provides, check out the lifted-base package, which includes such things as thread forking, timeouts, FFI marshaling.

This embedding technique does *not* work for all transformers. As you've
probably guessed, it does not work for continuation-based monads.

Even though these libraries are both being proposed for solving the same problem (exception handling in transformer stacks), that's actually just a narrow overlap between the two. Let's look at some of the things each library handles that the other does not:

- exceptions allows throwing exceptions in many more monads than monad-control works with. In particular, monad-control can
*only*handle throwing exceptions in IO-based stacks. (Note that this actually has nothing to do with monad-control.) - exceptions allows
*catching*exceptions in many more monads as well, in particular continuation based monads. - monad-control allows us to do far more than exception handling.

So the overlap squarely falls into: throwing, catching, and cleaning up from exceptions in a monad transformer stack which can be an instance of MonadMask/MonadBaseControl, which is virtually any stack without short-circuiting or continuations, and is based on IO.

Given that the overlap is relatively narrow, the next question is- if you have a situation that could use either approach- which one should you use? I think this is something that as a community, we should really try to standardize on. It would be beneficial from a library user standpoint if it was well accepted that "oh, I'm going to need a bracket here, so I should use MonadXXX as the constraint," since it will make library building more easily composable.

To help kick off that discussion, let me throw in my more subjective opinions on the topic:

- exceptions is an easier library for people to understand. I've been using monad-control for a while, and frankly I still find it intimidating.
- If you're writing a function that might fail, using MonadThrow as the constraint can lead to much better code composability and more informative error messages. (I'm referring back to 8 ways to report errors in Haskell.)
- exceptions allows for more fine-grained constraints via MonadThrow/MonadCatch/MonadMask.
- monad-control makes it virtually impossible to write an incorrect instance. It's fairly easy to end up writing an invalid MonadMask instance, however, which could easily lead to broken code. This will hopefully be addressed this documentation and education, but it's still a concern of mine.
- monad-control requires more language extensions.
- While there are things that exceptions does that monad-control does not, those are relatively less common.

Overall, I'm leaning in the direction that we should recommend exceptions as the standard, and reserve monad-control as a library to be used for the cases that exceptions doesn't handle at all (like arbitrary control functions). This is despite the fact that, until now, all of my libraries have used monad-control. If the community ends up deciding on exceptions, I agree to (over time) move my libraries in that direction.

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

### Announcement: Bang, a drum DSL for Haskell

### Problems using ghc 7.8.2 with options -staticlib and-threaded on osx

### Oliver Charles: A Category for Correct-By-Construction Serializers and Deserializers

Frequently in computer programming we need to work with data in different representations, and we need to work with the data on both sides of said representation. For example, we might have some Haskell data types in memory, which we later serialize to disk. When the user restarts our application, we need to reload this data back into Haskell data types, to allow them to resume work.

Haskell provides us with machinery for doing this serialization via the binary library, which gives us the Binary type class with two methods:

class Binary t where put :: t -> Put get :: Get tget deserializes a sequence of bytes into Haskell values, while put operates in the reverse direction - transforming Haskell values to a sequence of bytes.

Usually, we want the implementations of these methods to be mutual inverses - the computation in get should restore data serialized with put, and vice versa. Unfortunately, nothing in the type system nor the structure of these methods gives us this guarantee - it’s all down to the programmer. I don’t trust myself, so I set out to investigate a more reliable approach.

Ideally, we would like to build up serializers and deserializers from smaller pieces, such that each piece carries its own inverse. For example, we could pair up serialization for a String with its own inverse:

type Serializer a = (Get a, a -> Put) string :: Serializer String string = (get, put)As long as String has a Binary instance where get and put correctly specified, we know that string is going to function as we expect in both directions.

We’re on to something here, but currently this only works for single Strings. What if I have a pair of Strings that I want to serialize? From what we’ve seen so far, there’s no way to combine our bidirectional serializers. Earlier I mentioned that we would like to work with small pieces and compose them - lets see if we can solve this problem for just serialization first.

Serialization *consumes* data. If we have data to serialize, the application of one serializer should consume some of this data, leaving us with slightly less data that we have to continue serializing. By repeated application of serializers, we will eventually have considered the entire structure and will have nothing left to do. This consumption of a structure bit-by-bit suggests that serialization will be a type changing operation, as a record with a field removed is certainly not the same type as its larger record. So let’s try and incorporate that:

Composition of Serializing should now be clear - we just need to compose them one after another:

(.) :: Serializing b c -> Serializing a b -> Serializing a c (Serializing g) . (Serializing f) = Serializing (f >=> g) putTwoStrings :: Serializing (String, String) () putTwoStrings = pString1 . pString2We’ve built a serializer that can serialize a tuple of two strings, and we did so piece-by-piece. While what we have so far is not entirely satisfactory, it seems like we’re heading in the right direction. We’ll come back to this later, but first let’s see if the same ideas translate to deserializers.

Our serializer consumed data, so deserialization is naturally the opposite of consuming data - that is, deserialization *produces* data. When we deserialize we’ll start with nothing, and we’ll deserialize a few bytes into part of our structure one step at a time. Each step of deserialization should take the smaller structure and expand it into a larger structure - eventually leading us to the desired structure. Again, this will be a type changing operation, and we can encode all of this just as we did with Serializing:

As you can see, it’s pretty much exactly the same idea. The only difference is that now each of our deserializers return a slightly *bigger* structure, whereas our serializers would move our structure to something *smaller*.

Just to prove that what we have so far works, we can try this in GHCI:

> let bytes = case putTwoStrings of Serializing p -> runPut (p ("Hello", "World!")) > case getTwoStrings of Deserializing g -> runGet (g ()) (LBS.pack bytes) ("Hello","World!")To carry on working towards our goal, we need to pair the Serializer up with its Deserializer. Unfortunately, what we have so far won’t work:

data Serializer a b = Serializer (a -> Get b) (a -> Put b)Notice here how the types *both* move from a to b - that’s certainly not going to work, as the shape of the data is changing in opposite directions! In Get, a is “smaller” than b, whereas for Put a is “larger” then b. In order to work around this, we just need to swap the order of types in one of these functions - I’ve swapped the order for Put:

This makes sense - if put will shrink our structure, then get can move from this smaller structure back to the original structure. We can express our string1 and string2 serializers now:

string2 :: Serializer (String, String) String string2 = Serializer (\(a, b) -> do put a; return b) (\s -> do { s' <- get; return (s', s) }) string1 :: Serializer String () string1 = Serializer put (\() -> get)We were able to compose things before, and we can certainly compose things here…

(.) :: Serializer b c -> Serializer a b -> Serializer a c (Serializer g g') . (Serializer f f') = Serializer (f >=> g) (g' >=> f') twoStrings :: Serializer (String, String) () twoStrings = string1 . string2However, this has a rather significant problem - can you spot it? Take time to think about this and see if you can work out what’s going wrong.

Did you find it? If we fire up GHCI and have a play with our twoStrings serializer, lets see what we get…

> let bytes = case twoStrings of Serializer _ p -> runPut (p ("A", "B")) > case twoStrings of Serializer g _ -> runGet (g ()) bytes ("B","A")Oh no - that’s not what we wanted at all! The problem is that the order of effects are being reversed. When we put data, we put the first tuple element first, and then the second. However, we’re reading data in the opposite order - expecting the *second* element to be first in the stream, which is clearly not correct. For (String, String) the deserializer works but the tuple is in the wrong order - for other data types this would lead to a runtime exception.

With the current definition of Serializer, there’s simply no way around this - the types won’t let us run effects in different orders. The reason for this is that we can only access the underlying Get computation by having the smaller structure around first. However, we can be sneaky and changes things around just enough to let us run Get in a different order. Now the Get computation is no longer a function, but is a computation that *returns* a function:

With this change we *do* have access to any Get computation we like, and we are free to run them in a different order:

Now it’s clear that both our Put and our Get computations are sequenced in the same order - nice! It turns out that our composition comes with a sane definition of identity too, which means our Serializer can be used with Category:

instance Category Serializer where (Serializer g g') . (Serializer f f') = Serializer (do buildF <- g buildG <- f return (buildF . buildG)) (g' >=> f') id = Serializer (return id) return Serializing Through Heterogeneous ListsWe have finally reached a nice core to our solution, but the surface API isn’t really working out. We had to write different Serializers for both (String, String) and String, which is certainly not desirable. Ultimately, we would like to be able to work with just one Serializer for String, and compose them however we please.

Unfortunately, working with tuples is causing us the real pain here. The reason for this is that tuples don’t really have any structure that would allow us to work with them in any sort of principled manner. Instead, what we can do is use a heterogeneous list, which we can recurse on just like an ordinary linked list. So, we introduce a type for heterogeneous lists:

data List :: [*] -> * where Nil :: List '[] Cons :: a -> List as -> List (a ': as)And now we can use the new poly-kinded Category to upgrade Serializer to work with these lists:

data Serializer :: [*] -> [*] -> * where Serializer :: (Get (List a -> List b)) -> (List b -> PutM (List a)) -> Serializer a b instance Category Serializer where (Serializer g g') . (Serializer f f') = Serializer (do mkB <- g mkA <- f return (mkB . mkA)) (g' >=> f') id = Serializer (return id) returnThis was quite a detour, and has this really helped us? Indeed it has, as we can now we can write a much more general Serializer String:

string :: Serializer as (String ': as) string = Serializer (do a <- get; return (Cons a)) (\(Cons a as) -> do put a; return as)The type of string now indicates that this Serializer can serialize anything that starts with a String, and likewise when deserializing it expects a String to be the first element. This composes exactly as we’d expect:

twoStrings :: Serializer as (String ': String ': as) twoStrings = string . stringAll we need to do is unwrap the List resulting from a Get or wrap up data in a List for Put and we’re good to go:

> let bytes = case twoStrings of Serializer _ p -> runPut (void $ p ("A" `Cons` ("B" `Cons` Nil))) > case twoStrings of Serializer g _ -> runGet (($ Nil) <$> g) bytes Cons "A" (Cons "B" Nil) Destructuring Data Via PrismsThe API we’ve built works really well if we already have data decomposed into a List, but we don’t normally have this luxury. This means we need a way to convert from a data type to it’s constituent parts, and this is exactly the functionality that Prisms in the lens library provide us with. While Prisms can be a little hard to get your head around, it can be illuminating to experiment with them in GHCI:

> review _Cons (10, []) [10] > review _Cons (10, [20]) [10,20] > review _Cons (1, [2..5]) [1,2,3,4,5] > preview _Cons [10, 20, 30] Just (10,[20,30]) > preview _Cons [10] Just (10,[]) > preview _Cons [] NothingPrisms have two main operations: review and preview. review lets us construct some data out of its parts - above we use _Cons with (10, [20]), which is the same as (10 : [20]) - resulting in the list [10, 20]. preview lets us go the other way, which is the same idea as pattern matching on a constructor. If we preview _Cons on non-empty lists, then the pattern matching succeeds and the list is separated into its head and tail. However, we can’t pattern match with _Cons on an empty list, so preview returns Nothing - which corresponds to a pattern match failure.

Armed with Prism, we’re almost entirely ready to go! The only problem is that Prism normally works with tuples, which we’ve already seen aren’t a great data for our needs. It’s entirely mechanical to convert between tuples and List, so we simply move between them with a type class. Combining this all together, we have the following:

class ListIso a b | a -> b, b -> a where _HList :: Iso' b (List a) usePrism :: ListIso a b => Prism' d b -> Serializer a '[d] usePrism p = Serializer get put where put (Cons d Nil) = do Just tuple <- return (preview p d) return (tuple ^. _HList) get = return $ \hlist -> Cons (review p (hlist ^. from _HList)) NilNow we are free to use this on our data types, just as we’d expect:

instance ListIso '[a, b] (a, b) where _HList = iso (\(a, b) -> Cons a (Cons b Nil)) (\(Cons a (Cons b Nil)) -> (a, b)) data PairOfStrings = PairOfStrings String String makePrisms ''PairOfStrings pairOfStrings :: Serializer '[] '[PairOfStrings] pairOfStrings = usePrism _PairOfStrings . string . string ChoicesIf you look closely at our definition of usePrism you might have seen something suspicious. Here’s the relevant code:

usePrism = ... where put (Cons d Nil) = do Just tuple <- return (Lens.preview p d) return (tuple ^. _HList)In our put definition, we are assuming that Lens.preview is always returning a Just value. However, we saw earlier that this isn’t necessarily the case - the Prism corresponds to one of potentially many constructors. If we try and use usePrism with a prism that doesn’t match our expectations, then things go horribly wrong:

data Strings = PairOfStrings String String | ThreeStrings String String String makePrims ''Strings > case pairOfStrings of Serializer _ p -> runPut (void $ p (ThreeStrings "Uh" "Oh" "!" `Cons` Nil)) "*** Exception: Pattern match failure in do expression at ...What we need to do is to allow for choice - if we have multiple possible prisms, then we need to consider each one. This corresponds to exhaustive pattern matching in case analysis.

It turns out choice is relatively straight forward to add in. Get is already an instance of MonadPlus, so we get choice there for free. Put however is a little more involved, as it doesn’t have an instance of MonadPlus. The best solution I’ve found thus far is to wrap up our Put computation inside Maybe, but this isn’t entirely satisfactory. Unfortunately binary doesn’t quite export enough to have a less expensive solution (PairS doesn’t have its oconstructor exported).

Monoid is a sensible type class to use for alternatives - choice is associative, and there is a sane identity (an always-failing Serializer). Thus the final definition of Serializer and its associated type classes are:

data Serializer :: [*] -> [*] -> * where Serializer :: (Get (List a -> List b)) -> (List b -> Maybe (PutM (List a))) -> Serializer a b instance Category Serializer where (Serializer g g') . (Serializer f f') = Serializer (g >>= \b -> f >>= \a -> return (b . a)) (\a -> do putF <- g' a let (b, lbs) = runPutM putF putG <- f' b return (putLazyByteString lbs >> putG)) id = Serializer (return id) (return . return) instance Monoid (Serializer a b) where mempty = Serializer mzero (const mzero) (Serializer g p) `mappend` (Serializer g' p') = Serializer (g `mplus` g') (\i -> p i `mplus` p' i)Armed with this final definition of Serializer, we’re almost ready to provide a complete definition of serializing our Strings type. We need to provide a little extra information however, which allows us to disambiguate constructors. This is because if we are deserializing, if I read two strings I don’t necessarily know constructor to choose (yes, if we considered EOF this could be done, I’m going for brevity). You can find the definition of disambiguate in the full code listing.

Thus the final user-facing code is just:

strings :: Serializer '[] '[Strings] strings = mconcat [ usePrism _PairOfStrings . disambiguate 1 . string . string , usePrism _ThreeStrings . disambiguate 2 . string . string . string ]And just to prove it all works…

> let Just putter = case strings of Serializer _ p -> p (ThreeStrings "A" "B" "C" `Cons` Nil) bytes = runPut (void putter) > case strings of Serializer g _ -> runGet (($ Nil) <$> g) bytes Cons (ThreeStrings "A" "B" "C") Nil > let Just putter = case strings of Serializer _ p -> p (PairOfStrings "Hello" "World!" `Cons` Nil) bytes = runPut (void putter) > case strings of Serializer g _ -> runGet (($ Nil) <$> g) bytes Cons (PairOfStrings "Hello" "World!") Nil Final ThoughtsWe’ve seen that it’s possible to build correct-by-construction serializers and deserializers, and we got there by breaking down our problem into small parts and finding a good way to combine the parts together. Hopefully, I’ve illustrated some of the problems that arise from a naive solution, and how these problems guided us towards an implementation that is both more correct and more flexible.

Serializer is still not perfect however. With the idea of choice above, there’s no way to indicate exhaustive pattern matching. For example, in strings we are considering both constructors, yet put strings returns Maybe Put. This isn’t particularly satisfactory, because it should now always be possible to serialize this data type! On a similar note, it becomes harder to get compile time checks about exhaustive pattern matching, because we’re no longer doing case analysis explicitly. This is an interesting problem to me, and one that I would still like to solve.

There is also a bit more work that we might want to consider doing with Get and Put, which is to use a different concept of choice. There are other options than using Maybe - for example we could use lists which would inform us of *all* possible serializations for a data type, which might provide better debugging information than simply using the first one that matches.

I’d like to conclude by mentioning that the ideas here aren’t particularly new. In 2010 Rendel and Ostermann presented a solution using a category of partial isomorphisms and product functors from this category to Hask, which lead to various libraries on Hackage such as invertible-syntax, and boomerang. At ZuriHack, Martijn van Steenbergen presented the latest version of JsonGrammar, which uses a free category to describe operations on a JSON AST, and also illustrated how one can use prisms to provide a modern vocabulary for partial isomorphisms. json-grammar uses a stack-prism data type, which achieves the same goal as using heterogeneous lists, but does require another Template Haskell call (makeStackPrisms).

While I’m happy with the solution so far, I haven’t finished playing around with this. It’s unclear to me how this plays with recursive data types (for example, does this work for lists? What about trees?), and I need to learn more about stack-prism to see if using heterogenous lists impedes composition (as Sjoerd Visscher has warned me!). Hopefully I’ll be able to start using what I have so far in production, iron out the last problems, and release this to Hackage in the near future.

Thanks for reading, a full code listing can be found on Github

### New Functional Programming Job Opportunities

### Is there a functional concept similar to Union-Find?

Obviously, one could do a naive translation, such as simply using a monad for effects or doing incremental updates, but it seems to me that in functional programming, it would make sense to make it a monoid and stuff like that.

submitted by tailcalled[link] [7 comments]

### Mike Izbicki: lens you an applicative for great haskell?

Welcome back for round 2 of adventures in typeparams. In our last episode, we lensified the Functor type class. In this episode, we’re going to lensify the Applicative type class and plunge head first into type lens parsing.

Okay… down to business.

> {-# LANGUAGE TemplateHaskell #-} > {-# LANGUAGE ScopedTypeVariables #-} > {-# LANGUAGE KindSignatures #-} > {-# LANGUAGE TypeFamilies #-} > {-# LANGUAGE MultiParamTypeClasses #-} > {-# LANGUAGE UndecidableInstances #-} > {-# LANGUAGE FlexibleInstances #-} > {-# LANGUAGE RankNTypes #-} > {-# LANGUAGE OverloadedStrings #-}We’ve got a few more imports today. Our work from last time has been uploaded to hackage and is in the Data.Params.Functor module. For parsing, we’ll be torturing the attoparsec library.

> import Control.Category > import Prelude hiding ( (.), id, Functor(..), Applicative(..) ) > import qualified Prelude as P > import Data.Params > import Data.Params.Functor > import qualified Control.Applicative as Ap > import qualified Data.Attoparsec.Text as A > import Data.Attoparsec.Text (parse,Parser,Result) > import Data.Monoid > import Data.Text (Text,pack) Functor reviewAs a quick warm up, let’s talk about the infix fmap operator <$>. The fmap function has type:

fmap :: Functor lens tb => TypeLens Base lens -> (a -> GetParam lens tb) -> SetParam lens a tb -> tbAll this <$> operator does is move fmap’s lens parameter to the end of the parameter list. This restructuring will help us chain our operators together and will be a common theme throughout the post. The operator is defined as:

> infixl 4 <$> > (f <$> t) lens = fmap lens f tWe can use the operator like:

ghci> length <$> (Left $ Right "test") $ _a._b Left (Right 4)It will also be useful to have an operator just for specifying the type lens. Since a lens specifies the location “at” which we are operating, we call our new operator @@. It is defined as:

> infixr 0 @@ > (@@) :: (TypeLens p q -> b) -> TypeLens p q -> b > (@@) = idAnd used like:

ghci> length <$> (Left $ Right "test") @@ _a._b Left (Right 4)The fourth lens laws states that we must provide both prefix and infix versions of every combinator. Therefore we also introduce the function:

> at :: TypeLens q p -> (TypeLens q p -> t) -> t > at lens f = f lens ghci> at (_a._b) $ length <$> (Left $ Right "test") Left (Right 4) Lens you an ApplicativeWe’re ready to see our new Applicative class:

> class Functor lens tb => Applicative lens tb where > > pure :: GetParam lens tb -> TypeLens Base lens -> tb > > ap :: > ( tf ~ SetParam lens (a -> b) tb > , ta ~ SetParam lens a tb > , a ~ GetParam lens ta > , b ~ GetParam lens tb > ) > => TypeLens Base lens > -> tf > -> ta > -> tbThe functions pure and ap have the exact same meaning and laws as their counterparts in the standard libraries. The only difference is the addition of the TypeLens parameter and corresponding constraints.

The Left and Right Applicative instances for the Either class are defined as:

> instance Applicative p a => Applicative (Param_a p) (Either a b) where > pure a lens = Left $ pure a (zoom lens) > ap lens (Right a) _ = Right a > ap lens (Left f) (Right a) = Right a > ap lens (Left f) (Left b) = Left $ ap (zoom lens) f b > instance Applicative p b => Applicative (Param_b p) (Either a b) where > pure b lens = Right $ pure b (zoom lens) > ap lens (Left a) _ = Left a > ap lens (Right f) (Left a) = Left a > ap lens (Right f) (Right b) = Right $ ap (zoom lens) f bAnd just like with Functors, we have to define the base case for our recusive definitions:

> instance Applicative Base t where > pure a _ = a > ap _ f = fNow, to get the Applicative notation we all know and love, we redefine the <*> operator. It is just a thin wrapper around the ap function. Like the <$> operator, we just move the lens parameter to the end:

> infixl 4 <*> > (tf <*> ta) lens = ap lens (tf lens) taEasy as cake!

Let’s try it out!

We’ll start with the doubly nested Either. For nested Eithers, the lens we use specifies what the success constructors are. Any other constructors will act as errors.

Here’s an example without an error:

> fact1 :: Either (Either a String) b > fact1 = (++) <$> Left (Right "haskell") <*> Left (Right " rocks!") @@ _a._b ghci> fact1 Left (Right "haskell rocks!")Here we have one possible way of signaling an error:

> fact2 :: Either (Either a String) String > fact2 = (++) <$> Left (Right "python") <*> Right "error" @@ _a._b ghci> fact2 Right "error"And here we have the other way:

> fact3 :: Either (Either String String) b > fact3 = (++) <$> Left (Right "c++") <*> Left (Left "error") @@ _a._b ghci> fact3 Left (Left "error")Of course, Applicatives are much more useful when our functions have many arguments. Let’s create a function that concatenates four strings together into a phrase:

> cat4 :: String -> String -> String -> String -> String > cat4 a b c d = a ++ " " ++ b ++ " "++ c ++ " " ++ dAnd create a phrase with no errors:

> phrase1 :: Either (Either a String) b > phrase1 = cat4 > <$> Left (Right "haskell") > <*> Left (Right "is") > <*> Left (Right "super") > <*> Left (Right "awesome") > @@ _a._b ghci> phrase1 Left (Right "haskell is super awesome")And a phrase with two errors:

> phrase2 :: Either (Either String String) String > phrase2 = cat4 > <$> Left (Right "python") > <*> Right "error" > <*> Left (Right "is") > <*> Left (Left "error") > @@ _a._b ghci> phrase2 Right "error"Notice that in phrase2 we had two different causes of errors. The error with the fewest number of terms will always win. As a proof by example, let’s shuffle around our previous errors. We still get the same result:

> phrase3 :: Either (Either String String) String > phrase3 = cat4 > <$> Left (Right "python") > <*> Left (Left "error") > <*> Left (Right "is") > <*> Right "error" > @@ _a._b ghci> phrase3 Right "error" Pure bloods onlyThisis cool, but it’s not yet very generic. Everytime we want a success, we have to manually specify the constructors we want to use. We can avoid this tedium using the pure function. It’s type signature is:

pure :: Applicative lens tb => GetParam lens tb -> TypeLens Base lens -> tbThe important thing to notice is that the last parameter takes a TypeLens. This follows our magic formula. We can substitute it into our phrase1 variable like:

> phrase1' :: Either (Either a String) b > phrase1' = cat4 > <$> (pure "haskell" @@ _a._b) > <*> (pure "is" @@ _a._b) > <*> (pure "super" @@ _a._b) > <*> (pure "awesome" @@ _a._b) > @@ _a._bBut this is nasty! We have to specify the same TypeLens everywhere we want to use the pure function.

Thankfully, we don’t have to do this. The whole point of lenses is to create ridiculous new combinators that reduce boilerplate! So let’s do that! The “ap minus” combintator will automatically apply the lens for us:

> infixl 4 <*>- > (tf <*>- ta) lens = (tf <*> ta lens) lensThe minus sign signifies that the right side is “minus a lens” and so we should give it one automtically. Using this combinator, we can rewrite our phrase to look like:

> phrase1'' :: Either (Either a String) b > phrase1'' = cat4 > <$> (pure "haskell" @@ _a._b) > <*>- pure "is" > <*>- pure "super" > <*>- pure "awesome" > @@ _a._bIn order to get rid of the first lens application, we’ll need to perform the same trick to <$>:

> infixl 4 <$>- > (f <$>- t) lens = (f <$> t lens) lensAnd we get the beautiful:

> phrase1''' :: Either (Either a String) b > phrase1''' = cat4 > <$>- pure "haskell" > <*>- pure "is" > <*>- pure "super" > <*>- pure "awesome" > @@ _a._b Combinatorics with combinatorsThere’s two more Applicative combinators needed for parsing: *> and <* . They use the same definition in the standard libraries, but with a third lens parameter:

> infixl 4 <* > (u <* v) lens = pure const <*> u <*> v @@ lens > infixl 4 *> > (u *> v) lens = pure (const id) <*> u <*> v @@ lensNow we need to create all of the “minus” operators. Remember that the minus sign points to the variable that will have the lens automatically applied for us:

> infixl 4 <*- > infixl 4 -<*- > infixl 4 -<* > (u <*- v) lens = ( u <* v lens ) lens > (u -<*- v) lens = ( u lens <* v lens ) lens > (u -<* v) lens = ( u lens <* v ) lens > infixl 4 *>- > infixl 4 -*>- > infixl 4 -*> > (u *>- v) lens = ( u *> v lens ) lens > (u -*>- v) lens = ( u lens *> v lens ) lens > (u -*> v) lens = ( u lens *> v ) lensConfused? Just remember: when you master these new combinators, all the n00bs will worship your l33t h4sk311 5ki115.

Parsing timeNow that we’ve constructed our torture chamber, it’s time to put attoparsec on the rack. We’ll use the built-in “blind” Functor and Applicative instances to define our lensified ones as:

> mkParams ''Parser > instance Functor p a => Functor (Param_a p) (Parser a) where > fmap' lens f parser = P.fmap (fmap' (zoom lens) f) parser > instance Applicative (Param_a Base) (Parser a) where > pure a lens = Ap.pure $ pure a (zoom lens) > ap lens tf ta = tf Ap.<*> taAnd now we’re ready to start parsing. We’ll start simple. The attoparsec library provides a function called string that matches a specified string. We’ll use it to create a Parser that matches the phrase “haskell rocks”:

> chain1 :: TypeLens Base (Param_a Base) -> Parser Text > chain1 = A.string "haskell" *> A.string " rocks" ghci> parse (chain1 @@ _a) "haskell rocks" Done "" " rocks"In the above example, we chose to *not* specify the lens in the chain1 variable. This means that if we want to chain it with another parser, we should use the minus then operator like:

> chain2 :: TypeLens Base (Param_a Base) -> Parser Text > chain2 = chain1 -*> A.string "!" ghci> parse (chain2 @@ _a) "haskell rocks!" Done "" "!"If we choose to compose on the right, then we’ll need to move the minus sign to the right:

> chain3 :: TypeLens Base (Param_a Base) -> Parser Text > chain3 = A.string "¡" *>- chain2 ghci> parse (chain3 @@ _a) "¡haskell rocks!" Done "" "!"We have to use minus operators whenever we chain more than two parsers together. In the example below, the first *> takes three parameters (two parsers and a lens). It gets the lens from the minus of the first -*> operator. That operator also needs a lens, which it gets from the next -*>, and so on.

> chain4 :: TypeLens Base (Param_a Base) -> Parser Text > chain4 = A.string "do" > *> A.string " you" > -*> A.string " get" > -*> A.string " it" > -*> A.string " yet?" ghci> parse (chain4 @@ _a) "do you get it yet?" Done "" " yet?"If we need to apply a lens to both sides, then we use the -*>- operator:

> chain5 :: TypeLens Base (Param_a Base) -> Parser Text > chain5 = chain3 -*> A.string " ... " -*>- chain4 ghci> parse (chain5 @@ _a) "¡haskell rocks! ... do you get it yet?" Done "" " yet?" Stacking parsersEverything in the last section we could have done without type lenses. But now we’re going to lift the Parser into an arbitrary data type and work with it.

As a concrete example, we’ll put our Parser inside a Maybe. The Maybe Applicative instance is:

> instance Applicative p a => Applicative (Param_a p) (Maybe a) where > pure a lens = Just $ pure a (zoom lens) > ap lens Nothing _ = Nothing > ap lens (Just f) Nothing = Nothing > ap lens (Just f) (Just b) = Just $ ap (zoom lens) f bAnd for convenience we’ll use the following parseMaybe function. It has the same effect as the parse function provided by attoparsec, but does everything from within a Maybe.

> parseMaybe :: Maybe (Parser a) -> Text -> Maybe (Result a) > parseMaybe parser str = flip parse str <$> parser @@ _aNext, we lensify our parser combinators. This string lifts the string function provided by the attoparsec library into an arbitrary parameter specified by our type lens:

> string c lens = pure (A.string c) (zoom lens)Back to parsing.

Let’s just repeat the same 5 parse chains from above, but now within the Maybe context. Notice two things:

- The A.string function provided by the attoparsec library did not take a type parameter, but our new string function does. This means there’s a lot more minus combinators!
- Instead of specifying our lens to focus on the _a parameter, we must focus on the _a._a parameter to hit the parser.

> chain2' :: TypeLens Base (Param_a (Param_a Base)) -> Maybe (Parser Text) > chain2' = chain1' -*>- string "!" ghci> parse (chain2' @@ _a._a) "haskell rocks!" Done "" '!'

> chain3' :: TypeLens Base (Param_a (Param_a Base)) -> Maybe (Parser Text) > chain3' = string "¡" -*>- chain2' ghci> parse (chain3' @@ _a._a) "¡haskell rocks!" Done "" '!'

> chain4' :: TypeLens Base (Param_a (Param_a Base)) -> Maybe (Parser Text) > chain4' = string "do" -*>- string " you" -*>- string " get" -*>- string " it" -*>- string " yet?" ghci> parse (chain4' @@ _a._a) "do you get it yet?" Done "" " yet?"

> chain5' :: TypeLens Base (Param_a (Param_a Base)) -> Maybe (Parser Text) > chain5' = chain3' -*>- string " ... " -*>- chain4' ghci> parse (chain5' @@ _a._a) "¡haskell rocks! ... do you get it yet?" Done "" " yet?"

Again, there’s nothing special about being nested inside a Maybe. We could be nested inside any monstrous data type of your choosing. Yay!

But in the example we’ve chosen, what happens if we add a Maybe into the chain? Nothing takes over and eats the whole Parser. It doesn’t matter if the Parse was failing or succeeding, the answer is Nothing.

> chain6 :: TypeLens Base (Param_a (Param_a Base)) -> Maybe (Parser Text) > chain6 = string "python" -*> Nothing ghci> parseMaybe (chain6 @@ _a._a) "python" Nothing ghci> parseMaybe (chain6 @@ _a._a) "haskell" Nothing Circuit parsing teaserNow we’re ready for some super coolness. We’re going to design a parsing circuit that parses three unique Parse streams simultaneously!

Here is our Circuit definition:

> data Circuit x y z > = Circuit (Maybe x) (Maybe y) (Maybe z) > | CircuitFail > deriving (Show) > mkParams ''CircuitThe x, y, and z type params will hold the Parsers. These Parsers are wrapped within a Maybe. A value of Nothing represents that that parser will not consume any input. A value of (Just parser) means that it will consume input.

The Functor instances are rather interesting because of the Maybe wrapper. We must compose _a with the zoomed lens to make the types work out:

> instance Functor p x => Functor (Param_x p) (Circuit x y z) where > fmap' lens f CircuitFail = CircuitFail > fmap' lens f (Circuit x y z) = Circuit (fmap' (_a . zoom lens) f x) y z > instance Functor p y => Functor (Param_y p) (Circuit x y z) where > fmap' lens f CircuitFail = CircuitFail > fmap' lens f (Circuit x y z) = Circuit x (fmap' (_a . zoom lens) f y) z > instance Functor p z => Functor (Param_z p) (Circuit x y z) where > fmap' lens f CircuitFail = CircuitFail > fmap' lens f (Circuit x y z) = Circuit x y (fmap' (_a . zoom lens) f z)The Applicative instances are where all the action is at. In each case, the pure function is fairly straightforward. It looks just like the other ones we’ve seen except that it applies the _a to the zoomed lens and gives default values of Nothing to the other parsers. The ap function calls ap on the appropriate parser and uses the First Monoid instance on the other two.

> instance > ( Applicative p x > , Monoid y > , Monoid z > ) => Applicative (Param_x p) (Circuit x y z) > where > pure x lens = Circuit (pure x @@ (_a . zoom lens)) Nothing Nothing > ap lens CircuitFail _ = CircuitFail > ap lens _ CircuitFail = CircuitFail > ap lens (Circuit x1 y1 z1) (Circuit x2 y2 z2) = Circuit > (ap (_a . zoom lens) x1 x2) > (getFirst $ First y1 <> First y2) > (getFirst $ First z1 <> First z2) > instance (Monoid x, Applicative p y, Monoid z) => Applicative (Param_y p) (Circuit x y z) where > pure a lens = Circuit Nothing (pure a @@ _a . zoom lens) Nothing > ap lens CircuitFail _ = CircuitFail > ap lens _ CircuitFail = CircuitFail > ap lens (Circuit x1 y1 z1) (Circuit x2 y2 z2) = Circuit > (getFirst $ First x1 <> First x2) > (ap (_a . zoom lens) y1 y2) > (getFirst $ First z1 <> First z2) > instance (Monoid x, Monoid y, Applicative p z) => Applicative (Param_z p) (Circuit x y z) where > pure a lens = Circuit Nothing Nothing (pure a @@ _a . zoom lens) > ap lens CircuitFail _ = CircuitFail > ap lens _ CircuitFail = CircuitFail > ap lens (Circuit x1 y1 z1) (Circuit x2 y2 z2) = Circuit > (getFirst $ First x1 <> First x2) > (getFirst $ First y1 <> First y2) > (ap (_a . zoom lens) z1 z2)We write a nice wrapper so we can parse our circuits:

> parseCircuit > :: Circuit (Parser x) (Parser y) (Parser z) > -> Text > -> Text > -> Text > -> Circuit (Result x) (Result y) (Result z) > parseCircuit CircuitFail _ _ _ = CircuitFail > parseCircuit (Circuit x y z) str1 str2 str3 = Circuit > ( parseMaybe x str1 ) > ( parseMaybe y str2 ) > ( parseMaybe z str3 )And now here is a simple circuit for us to play with:

> circ1 :: Circuit (Parser Text) (Parser Text) (Parser Text) > circ1 = Circuit > (string (pack "haskell") @@ _a._a) > (string (pack "is" ) @@ _a._a) > (string (pack "fun" ) @@ _a._a)When we try to parse our circuit, we just match each word in parallel:

ghci> parseCircuit circ1 "haskell" "is" "fun" Circuit (Just Done "" "haskell") (Just Done "" "is") (Just Done "" "fun")In this example, we compose our circuit only on the first parameter:

ghci> parseCircuit (circ1 *> circ1 @@ _x._a) "haskell" "is" "fun" Circuit (Just Partial _) (Just Done "" "is") (Just Done "" "fun")Notice that (above) we no longer finished after matching the word “haskell”. We’ve got a whole ‘nother haskell to go. Oh Joy!

Here, we match completely:

ghci> parseCircuit (circ1 *> circ1 @@ _x._a) "haskellhaskell" "is" "fun" Circuit (Just Done "" "haskell") (Just Done "" "is") (Just Done "" "fun")In our Circuit type, every parser is—at least so far—acting completely independently. That means one parser can fail while the others succeed:

ghci> parseCircuit circ1 "python " "is" "fun" Circuit (Just Fail "python " [] "Failed reading: takeWith") (Just Done "" "is") (Just Done "" "fun")Let’s create another simple circuit to play with. In this one, only the first parser performs any actions. The other two are noops:

> circ2 :: Circuit (Parser Text) (Parser y) (Parser z) > circ2 = Circuit > (string (pack " with lenses") @@ _a._a) > Nothing > NothingWe can compose circ1 and circ2 exactly as you would suspect. Our original string is now only a partial match:

ghci> parseCircuit (circ1 *> circ2 @@ _x._a) "haskell" "is" "fun" Circuit (Just Partial _) (Just Done "" "is") (Just Done "" "fun")But this matches perfectly:

ghci> parseCircuit (circ1 *> circ2 @@ _x._a) "haskell with lenses" "is" "fun" Circuit (Just Done "" " with lenses") (Just Done "" "is") (Just Done "" "fun")And this fails:

ghci> parseCircuit (circ1 *> circ2 @@ _x._a) "haskell without lenses" "is" "fun" Circuit (Just Fail " without lenses" [] "Failed reading: takeWith") (Just Done "" "is") (Just Done "" "fun")We can simplify the code of circ2 even further (and make it more generic) using the pure function:

> circ3 :: Circuit (Parser Text) (Parser y) (Parser z) > circ3 = pure (string (pack " with lenses") @@ _a) @@ _xcirc3 behaves exactly like circ2 when sequenced with circ1:

ghci> parseCircuit (circ1 *> circ3 @@ _x._a) "haskell with lenses" "is" "fun" Circuit (Just Done "" " with lenses") (Just Done "" "is") (Just Done "" "fun")And that’s enough for today. GHC needs to rest. It’s tired.

Tune in next time…We’ve still go so many tantalizing questions to answer:

- What is that CircuitFail gizmo doing?
- How do I use Alternative to branch my parser?
- Can a Circuit’s parser depend on the other parsers in the Circuit?
- Do fiber optic burritos taste good??!?!

Stay tuned to find out!

### A Year of Functional Programming

### Memory pools for ghc?

I was looking at the binary-trees game and it seems that the C and C++ implementations become 4x faster by using memory pools.

In Haskell, it seems that it should be possible to create a type for an expression where a temporary memory pool is utilized, but after evaluation, the whole memory pool is cleared, instead of using the garbage collector to scan the memory.

A sort of garbage collection will happen by tracing the result, but the user gets to explicitly indicate points in the program flow where lots of garbage exists and thus lots of GC can be avoided.

Because Haskell in general does not allow mutable storage, no reference from an old generation can point into this pool, so for pure code, this should be safe, and fast.

What I am thinking is that a function like this:

data PoolSpec = PoolSpec { ... } poolEval :: NFData a => PoolSpec -> a -> a poolEval spec val = do -- Make the memory allocator use a new pool, or just mark the -- current nursery position if enough memory is available in the -- current generation. let mark = pushMemoryMark spec -- In new pool, evaluate the result let result = deepseq val -- Release the pool. Copy result out of the pool. popMemoryMark mark result data Mark = ... -- Create a new memory pool with the current memory pool -- as parent. pushMemoryMark :: Mark -- Copy a result value from the current memory pool to the -- parent memory pool, destroy the current memory pool, -- and set the parent memory pool to be the current memory -- pool popMemoryMark :: NFData a => Mark -> a -> aHow incompatible are these functions with the current ghc rts, and what would, say a webserver gain by having this?

submitted by hastor[link] [12 comments]