News aggregator

Yesod is Fun

Haskell on Reddit - Thu, 05/15/2014 - 6:15am
Categories: Incoming News

language-puppet: 7 Startups - part 3 - An interpreter for the rules

Planet Haskell - Thu, 05/15/2014 - 4:44am
In the [previous episode](/blog/2014/05/12/7-startups-part-2-game-rules-definition/) I implemented the game rules, but did not test them. I also had some reservations about some code I wrote, but predicted it would be mostly right, even without tests. Today's episode is about pretty printing and operational ! ## Minor modifications since last time * I [refactored](https://github.com/bartavelle/7startups/commit/6aa7339d7bda803873c5766817a02d67c34fd381) the `getCardFunding` and `getCardVictory` functions so that they are now pure. I toyed with the idea of having a monad morphism (I learned today it was [called like that](http://www.reddit.com/r/haskell/comments/25gb6d/stateful_computations_in_f_with_update_monads/chgw0wv) to integrate `Reader GameState` actions in the `MonadState GameState` functions, but this was not warranted as the functions are so simple. * I [refactored](https://github.com/bartavelle/7startups/commit/b3caa21bac827f0c1ac531e23b3501cfb3d40029) neighborhood relationship so that it encodes more invariants. A player now must have a left and right neighbor. They might be invalid though. * I [refactored](https://github.com/bartavelle/7startups/commit/b04dbf2c3e491bc5852a516d4f1aa88d7958e463) the type of the interfaces between the game rules and the players, so that you can't pass empty lists where they are forbidden. I was later told this type already existed in [semigroups](https://github.com/bartavelle/7startups/commit/0bdcf97ad490bad3d81b8bd8eb8dd57d3f883a2d). ## Why pretty printing ? I hinted heavily last time that there would be a dedicated pretty printer. An example of such an implementation is in the [ansi-wl-pprint](http://hackage.haskell.org/package/ansi-wl-pprint) package. It introduces functions and combinators that let you easily create a `Doc` value that will look neat on your screen. Unfortunately, in order to properly support all text-based backends (IRC, XMPP, email, console) it doesn't seem to be possible to reuse an existing printer. For example, the color set between all these backends is quite distinct, and some are even capable of printing pictures. I tried to engineer one that would be at the same time flexible, easy to use and good-looking an all backends. Time will tell if this was a success. I will not give a dissertation on the subject, and have copied the interface from other pretty printing libraries. I will just give some implementation details here. ### Basic pretty printing types Speaking of stealing from other pretty printers, I really should have looked at their code too ! Here are my basic types: <figure class="code"> 1 2 3 4 5 6 7 newtype PrettyDoc = PrettyDoc { getDoc :: Seq PrettyElement } deriving (Eq, Monoid) data PrettyElement = RawText T.Text | NewLine | Space | ... </figure> So you basically have all “elements” in `PrettyElement`, and they can be appended in a Monoidal fashion in a `PrettyDoc`, which is just a `newtype` for `Seq PrettyElement`. This is a very inelegant decision, and I will be sure to refactor it for the next episode ! Looking at [another implementation](http://hackage.haskell.org/package/ansi-wl-pprint-0.6.7.1/docs/src/Text-PrettyPrint-ANSI-Leijen.html#Doc), it is clear that a single type was required, and that the Monoidal structure could be achieved by adding `Empty` and `Cat` constructors. There is a reason I wrote my type like this though, and it is related to how I intended to solve the problem of backends with poor or no support for multiline messages, but this will featured in another episode ! ### Specific design choices I decided to directly encode the game entities as part of the pretty printing types. That should be obvious from the list of [elements](https://github.com/bartavelle/7startups/blob/Step3/Startups/PrettyPrint.hs#L25-L45). A `VictoryPoint`, a `Neighbor` or even a `CardType` are directly representable, so that the backends can optimize their rendering. Other than that, the code is pretty boring. ### A pretty-pretty printer ? My first backend will be the console, as it will not have any networking or concurrency problems to solve. I used the aforementionned [ansi-wl-pprint](http://hackage.haskell.org/package/ansi-wl-pprint) package, and wrote a [pretty instance](https://github.com/bartavelle/7startups/blob/Step3/Startups/PrettyPrint.hs#L202-L244) for `PrettyElement` and `PrettyDoc`. This leads to strange code such as `print (PP.pretty (pe something))`. ## Implementing the GameMonad During the last episode, I wrote all the rules in an abstract monad that is an instance of `GameMonad`, meaning it featured a few functions for interacting with the players. I took a typeclass approach so that I could start writing the rules without worrying about the actual implementation of this abstract monad. Now that the rules are written, it is time to give them a try. In order to do so, I ditched the typeclass, and expressed it in terms of `ProgramT`, from the [operational](http://hackage.haskell.org/package/operational) package. It only takes a few steps to refactor : ### The instructions GADT You must start by writing all the operations that must be supported as a GADT. We previously had : <figure class="code"> 1 2 3 4 5 6 7 8 9 10 11 type NonInteractive m = (MonadState GameState m, Monad m, MonadError Message m, Functor m, Applicative m) class NonInteractive m => GameMonad m where playerDecision :: Age -> Turn -> PlayerId -> [Card] -> GameState -> m (PlayerAction, Exchange) askCard :: Age -> PlayerId -> [Card] -> GameState -> Message -> m Card tellPlayer :: PlayerId -> Message -> m () generalMessage :: Message -> m () </figure> And now have : <figure class="code"> 1 2 3 4 5 6 7 8 data GameInstr a where PlayerDecision :: Age -> Turn -> PlayerId -> NonEmpty Card -> GameInstr (PlayerAction, Exchange) AskCard :: Age -> PlayerId -> NonEmpty Card -> Message -> GameInstr Card TellPlayer :: PlayerId -> Message -> GameInstr () GeneralMessage :: Message -> GameInstr () ActionsRecap :: M.Map PlayerId (PlayerAction, Exchange) -> GameInstr () ThrowError :: Message -> GameInstr a CatchError :: GameMonad a -> (Message -> GameMonad a) -> GameInstr a </figure> So … there have been some choices going on here. First of all, we need to support all the features we previously had, namely `MonadState`, `MonadError` and four game-specific functions. You can spot these four functions quite easily (along with a new one, which will be covered in a minute). We get `MonadState` and `MonadError` in the following way : <figure class="code"> 1 2 3 4 5 type GameMonad = ProgramT GameInstr (State GameState) instance MonadError PrettyDoc (ProgramT GameInstr (State GameState)) where throwError = singleton . ThrowError catchError a handler = singleton (CatchError a handler) </figure> I decided to use the monad transformer `ProgramT` over a base `State GameState` monad, but encode the error part with the provided instructions. It would have been easier to encode the state part that way, except I don’t know how to write an instance for `ProgramT` (see [this post comment](http://lpuppet.banquise.net/blog/2014/02/26/moving-from-an-io-based-monad-stack-to-a-pure-program/#comment-1264668498)). The interaction functions no longer have a `GameState` in their types, because the interpreter will have access to the state when decoding this instruction, so it is not necessary to pass it here too. ### Mechanically refactor all mentions of GameMonad Now all you have to do is to replace all type signatures that looked like : <figure class="code"> 1 GameMonad m => a -> b -> m c </figure> Into : <figure class="code"> 1 a -> b -> GameMonad c </figure> ### Write an interpreter I decided to write a generic interpreter, that takes a [group of functions](https://github.com/bartavelle/7startups/blob/Step3/Startups/Interpreter.hs#L13-L18) in some monad `m`, a base `GameState`, and gives you a function that computes any `GameMonad a` expression in the `m` monad. The implementation is pretty obvious, and not very interesting, but it should be easy to write backends now. Perhaps of interest is the fact that the game state is explicitely passed as a parameter all over the place, so it can be passed to the backends at the interpreter level. ### A pure backend The easiest backend to write is a pure one, with no real player interaction. I could have used `Identity` as the base monad, but instead opted for `State StdGen`. That way, I can easily have the “players” play random cards, which will help with testing. The [implementation](https://github.com/bartavelle/7startups/blob/Step3/Backends/Pure.hs) is also nothing special, but made me write a [lot of code](https://github.com/bartavelle/7startups/blob/Step3/Startups/Utils.hs) to support it. In particular, the `allowableActions` function is pretty tricky, and is not entirely satisfying. Given a game state, a player name and a list of cards in his hands, it gives a list of all the non obviously stupid legal actions that are available. It does so in the most direct way, enumerating all possible combinations of resources, neighbor resources, exchanges, etc. that would work. Then it removes all duplicates, and the actions that are obviously too expensive. Fortunately, all this code will also be used by the other backends. ## So … are there bugs yet ? I wrote a simple test that checks for errors. Theorically, the pure backend should always result in games that end well (we should get a `Right …` instead of a `Left rr`. So I wrote a simple property-based test that gets an arbitrary seed and number of players (between 3 and 7), runs a pure game and checks its result. And there were runtime errors ! * The `Monoid` instance for `AddMap` had an [infinite loop](https://github.com/bartavelle/7startups/blob/Step3/tests/tests.hs#L78-L85). * The `allowableActions` function sometimes returned no valid actions. I forgot to always add the possibility to drop a card … To prevent the second case from happening again, I [wrote the “prepend drop actions” before the big case statement](https://github.com/bartavelle/7startups/blob/master/Startups/Utils.hs#L246), and modified the type of the `askCardSafe` function so that [it can’t accept an empty list](https://github.com/bartavelle/7startups/blob/Step3/Startups/GameTypes.hs#L111). This means that if I introduce another bug in `allowableActions`, I should get a `Left …` instead of a runtime exception. There also was a “rule” bug, due to the fact that I had not understood a rule correctly. Basically, I use a fictionnal 7th round to emulate the efficiency capability, but there should be no “hand rotation” before that turn. I fixed it [wrong](https://github.com/bartavelle/7startups/commit/12b87ba3f11c2e4fe5dd9c6f58d760daa79d772a) once, and then [properly](https://github.com/bartavelle/7startups/commit/c4eba8358c304ff7b81ae7a365987c10742d58b9). However, I did not discover nor fix this bug because of tests. ## The console backend Before writing the console backend I needed a bit of code for [pretty printing stuff](https://github.com/bartavelle/7startups/blob/Step3/Backends/Common.hs). Once this was done, the backend was [quickly written](https://github.com/bartavelle/7startups/blob/Step3/src/Console.hs). The opponents still play randomly, which explains the kind of results depicted below, but it is a genuine pleasure to finally play ! ![Crushing victory](/images/7startups-console1.png) I also realized when using the console backends that the messaging functions, while generic, would probably not work well on all backends. I decided to include more specialized functions, such as `ActionsRecap`, which can be passed a map of all the actions the players undertook in a turn. The current version also lacks a way of getting the results of the poacher wars between the ages, but that should be trivial to add. ## Next time Next time should get more interesting, as I will try to write an interesting backend. It will be a bit harder to design because I want players using distinct backends to be able to participate in the same game.
Categories: Offsite Blogs

Mikael Vejdemo Johansson (Syzygy-): Classifying spaces and Haskell

Planet Haskell - Wed, 05/14/2014 - 8:27pm

I’ve been talking with some topologists lately, and seen interesting constructions. I think these may potentially have some use in understanding Haskell or monads.

Simplicial objects

A simplicial object in a category is a collection of objects $C_n$ together with n maps $d_j:C_n\to C_{n-1}$ and n maps $s_j:C_n\to C_{n+1}$ subject to a particular collection of axioms.

The axioms are modeled on the prototypical simplicial structure: if $C_n$ is taken to be a (weakly) increasing list of integers, $d_j$ skips the $j$th entry, and $s_j$ repeats the $j$th entry. For the exact relations, I refer you to Wikipedia.

Classifying spaces

Take a category C. We can build a simplicial object $C_*$ from C by the following construction:

$C_n$ is all sequences $c_0\xrightarrow{f_0}c_1\xrightarrow{f_1}\dots\xrightarrow{f_{n-1}}c_n$ of composable morphisms in $C$.
$d_j$ composes the $j$th and $j+1$st morphisms. $d_0$ drops the first morphism and $d_n$ drops the last morphism.
$s_j$ inserts the identity map at the $j$th spot.

We can build a topological space from a simplicial object: dimension by dimension, we glue the product $\Delta^{n-1}\times C_n$ of an $n-1$-dimensional simplex and the object $C_n$ to the lower dimensional construction — with the face maps dictating the gluing step.

Classifying space of Hask

Consider the category of Haskell types and functions. The classifying space here will have an $n$-dimensional simplex for any sequence of $n+1$ composable functions; glued to the lower-dimensional simplices by composing adjacent functions.

I honestly am not entirely sure what structure, if any, can be found here: this might model $\beta$-reductions; or it might model something utterly trivial — I wonder what, if anything, can be found here, but I currently have no answers.

Classifying space of a Monad

We can do the same thing in the category of endofunctors. Recall that a Monad is an endofunctor $T$ with natural transformations $b:T^2\to T$ and $u:1\to T$. Just like any monoid, there is a category structure that fits in this framework. The simplicial object here is $T_*$ with $T_n=T^(n+1)$. The face maps $d_j$ compose two adjacent applications of $T$ using $b$. Degeneracy maps $s_j$ introduce a new $T$ by applying $u$.

For an example, let’s consider the Writer monad, for a monoid w:

newtype Writer w a = Writer { runWriter :: (a, w) }
return a = (a, mone)
bind ((a, w0), w1) = (a, w0 `mappend` w1)

The endofunctor here is Writer w :: * -> *. Iterating this endofunctor gets us (Writer w)^n a = (((...(a,w),w),w),w)...,w). A typical value would be something like

(((...(a,w0),w1),w2),...,wn) :: (Writer w)^n a

We get a simplicial structure here by letting the $j$th face map apply mappend to wj and w(j+1). The $j$th degeneracy map creates an instance of mone at the $j$th spot.

Let’s get more concrete. Consider Writer Any Bool. Recall that w0 `mappend` w1 = w0 `or` w1. For any value of of type x::a, there are $2^n$ values in (Writer w)^n a: one for each possible sequence of input to the Writer monad. Each of these produces an $n-1$-dimensional simplex, that glues to the lower dimensional simplices by fusing neighboring points.

In (Writer Any Bool)^0 there are two vertices: (x,False) and (x,True).

In (Writer Any Bool)^1 there are four edges: (x,True, True), (x,True, False), (x,False, True) and (x,False, False).
These connect to the vertices like this:

In (Writer Any Bool)^2 there are eight triangles. They glue as follows — each triangle gets its three edges in order:
FFF to FF, FF, FF
FFT to FT, FT, FT
FTF to TF, TF, FT
FTT to TT, TT, FT
TFF to FF, TF, TF
TFT to FT, TT, TT
TTF to TF, TF, TT
TTT to TT, TT, TT

It continues like this as we add higher and higher dimensional faces. Any history of $n$ writes to the monad produces an $n-1$-dimensional object, that connects to lower dimensions by looking at how the history could have been contracted by the monoid action at various points.

For the monad Writer All Bool, the same vertices, edges, triangles, et.c. show up, but they connect differently:
FF to F, F
FT to T, F
TF to F, F
TT to T, T
FFF to FF, FF, FF
FFT to FT, FT, FF
FTF to TF, FF, FF
FTT to TT, FT, FT
TFF to FF, FF, TF
TFT to FT, FT, TF
TTF to TF, TF, TF
TTT to TT, TT, TT

What can we use this for?

And here, at last, is my reason for writing all this. This construction gets us a topological space, where cells in the space (possibly even points in the space) correspond to possible values of the iterated monad datatype, and where connectivity in the space is driven by the monad. This gives us a geometric, a topological, handle on the programming language structure.

Is this good for anything?
Are there any sort of questions we might be able to approach with this sort of perspective?
I’ll be thinking about it, but if anyone out there has any sort of idea I’d love to hear from you.

Categories: Offsite Blogs

ANN: LGtk-0.8

Haskell on Reddit - Wed, 05/14/2014 - 1:33pm
Categories: Incoming News

case, GADTs, Arrows

haskell-cafe - Wed, 05/14/2014 - 11:45am
Hi Café! Are there EXACT rules for desugaring "case" construct in Arrow syntax? The documentation says just "The translation is similar to that of if commands". But that can't be right in case of GADTs. For example, let's say we have data A where A :: Show s => s -> A Then the following would work fine: proc () -> do a <- arr A -< "test" case a of A s -> returnA -< show s But if we abstract part of it: b :: (Arrow a, Show s) => a s String b = proc(s) -> returnA -< show s proc() -> do a <- arr A -< "test" case a of A s -> b -< s then it fails. Now, I'm not asking why exactly does it fail. I understand, that type classes are just data types, and, if arrow is fixed, then the real type of "b" would be b :: Show s -> a s String and that can't be combined with something of type a () (Show s, s). So, the second example shouldn't work at all (although the error message could use some improvement). But I'm surprised that the first one does. Another une
Categories: Offsite Discussion

[GCM 2014] Last CFP : Graph Computation Models

General haskell list - Wed, 05/14/2014 - 9:54am
----------------------------------------------------------------------- Last CALL FOR PAPERS GCM 2014 Fifth International Workshop on Graph Computation Models York, UK, July 21st, 2014 http://gcm2014.imag.fr/ Part of ICGT 2014 http://www.2014.icgt-conferences.org/ Full versions of best papers will be included in an issue of the the international journal of the "Electronic Communications of the EASST" -------------------------------------------------------------------------- Aims The aim of the International Workshop GCM2014 is to bring together researchers interested in all aspects of computation models based on graphs and graph transformation techniques. It promotes the cross-fertilizing exchange of ideas and experiences among researchers and students from the different c
Categories: Incoming News

I have a day to learn haskell.

Haskell on Reddit - Wed, 05/14/2014 - 9:32am

I did a bit of it a few months ago for a college course but I have basically forgotten everything.

Does anybody have any links to some tutorials that will get me up to speed in the next 24 hours?

submitted by mormon-
[link] [10 comments]
Categories: Incoming News

Not about arrows

Haskell on Reddit - Wed, 05/14/2014 - 7:29am
Categories: Incoming News

Get "cabal repl" to dump ghc options?

haskell-cafe - Wed, 05/14/2014 - 6:34am
Hi, The cabal repl command works out a bunch of GHC options. Is there any way to dump these options without actually starting the repl? In particular, things like this: ghcOptPackageDBs = [ GlobalPackageDB , SpecificPackageDB \"/home/carlo/foo/.cabal-sandbox/x86_64-linux-ghc-7.6.3-packages.conf.d\",SpecificPackageDB \"dist/package.conf.inplace\" ] Basically it would be nice to get the contents of replOpts just before this bit of code: https://github.com/haskell/cabal/blob/master/Cabal/Distribution/Simple/GHC.hs#L792-L796
Categories: Offsite Discussion

Any library for writing and composing tree transducers, with examples?

Haskell on Reddit - Wed, 05/14/2014 - 4:39am

The only related library I found was CompData, but the focus is not particularly on the tree transducers and it is lacking any examples.

submitted by SrPeixinho
[link] [11 comments]
Categories: Incoming News

vector and GeneralizedNewtypeDeriving

glasgow-user - Wed, 05/14/2014 - 2:39am
Hello, Prior to ghc-7.8, it was possible to do this: M.MVector is defined as etc. With ghc-7.8 this no longer compiles due to an unsafe coercion, as MVector s Foo and MVector s Int have different types. The error suggests trying -XStandaloneDeriving to manually specify the context, however I don't see any way that will help in this case. For that matter, I don't see any way to fix this in the vector package either. We might think to define but that doesn't work as both parameters to M.MVector require a nominal role (and it's probably not what we really want anyway). Furthermore Data.Vector.Unboxed.Base.MVector (which fills in at `v` in the instance) is a data family, so we're stuck at that point also. So given this situation, is there any way to automatically derive Vector instances from newtypes? tl;dr: I would really like to be able to do: am I correct that the current machinery isn't up to handling this? Thanks, John _______________________________________________ Glasgow-haskell-users mai
Categories: Offsite Discussion

Bryan O'Sullivan: Once more into the teach, dear friends

Planet Haskell - Tue, 05/13/2014 - 11:18pm

Since the beginning of April, David Mazières and I have been back in the saddle teaching CS240H at Stanford again.

If you’re tuning in recently, David and I both love systems programming, and we particularly get a kick out of doing it in Haskell. Let me state this more plainly: Haskell is an excellent systems programming language.

Our aim with this class is to teach both enough advanced Haskell that students really get a feel for how different it is from other programming languages, and to apply this leverage to the kinds of problems that people typically think of as “systemsy”: How do I write solid concurrent software? How do I design it cleanly? What do I do to make it fast? How do I talk to other stuff, like databases and web servers?

As before, we’re making our lecture notes freely available. In my case, the notes are complete rewrites compared to the 2011 notes.

I had a few reasons for rewriting everything. I have changed the way I teach: every class has at least some amount of interactivity, including in-class assignments to give students a chance to absorb what I’m throwing at them. Compared to the first time around, I’ve dialed back the sheer volume of information in each lecture, to make the pace less overwhelming. Everything is simply fresher in my mind if I write the material right before I deliver it.

And finally, sometimes I can throw away plans at the last minute. On the syllabus for today, I was supposed to rehash an old talk about folds and parallel programming, but I found myself unable to get motivated by either subject at 8pm last night, once I’d gotten the kids to bed and settled down to start on the lecture notes. So I hemmed and hawed for a few minutes, decided that talking about lenses was way more important, and went with that.

Some of my favourite parts of the teaching experience are the most humbling. I hold office hours every week; this always feels like a place where I have to bring my “A” game, because there’s no longer a script. Some student will wander in with a problem where I have no idea what the answer is, but I vaguely remember reading a paper four years ago that covered it, so when I’m lucky I get to play glorified librarian and point people at really fun research.

I do get asked why we don’t do this as a MOOC.

It is frankly a pleasure to actually engage with a room full of bright, motivated people, and to try to find ways to help them and encourage them. I don’t know quite how I’d replicate that visceral feedback with an anonymous audience, but it qualitatively matters to me.

And to be honest, I’ve been skeptical of the MOOC phenomenon, because while the hype around them was huge, it’s always been clear that almost nobody knew what they were doing, or what it would even mean for that model to be successful. If the MOOC world converges on a few models that make some sense and don’t take a vast effort to do well, I’m sure we’ll revisit the possibility.

Until then, enjoy the slides, and happy hacking!

Categories: Offsite Blogs

CS240h lecture notes

Haskell on Reddit - Tue, 05/13/2014 - 8:53pm
Categories: Incoming News