News aggregator

language-puppet: 7 Startups - part 2 - Game rules definition

Planet Haskell - Mon, 05/12/2014 - 12:59pm

Whew, I just added a big pile of code to what was done previously. I wrote all the missing game types and rules. It took about 4 or 5 hours.

In this post, I will describe how I decided to define the main game types, and some various details of interest.

Choosing the rules monad

I will describe the rules using a monad, mainly because I am used to work with them, and because they are mighty convenient in Haskell, with the do notation and the numerous libraries. As is often the case with games, there will be a state, containing the game state at a given time. But while I will just write the rules, I need to graft user interaction at some point. The goal of this project is to write a 7 Wonders clone that might work with multiple backends. To achieve this, I will try not to constraint my implementation any more than necessary.

Player identification

The first important type is to find a way to identify each players. I wrote this :

<figure class="code"> 1 type PlayerId = T.Text </figure>

I currently am not sure this is sufficient / precise enough, but the backends I have in mind (IRC, XMPP, console and email) all have string based identifiers, so it should work for at least those three. Anyway, the backends will probably have to keep a relationship between a player nickname and his actual identity in the system, so this will probably turn out OK.

Game state <figure class="code"> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 data GameState = GameState { _playermap :: M.Map PlayerId PlayerState , _discardpile :: [Card] , _rnd :: StdGen } data PlayerState = PlayerState { _pCompany :: CompanyProfile , _pCompanyStage :: CompanyStage , _pCards :: [Card] , _pFunds :: Funding , _pNeighborhood :: M.Map Neighbor PlayerId , _pPoachingResults :: [PoachingOutcome] } makeLenses ''GameState makeLenses ''PlayerState </figure>

This might look pretty obvious, and it might be (as it is my first version), but this model has several shortcomings, the worst of them being the way that neighboring information is encoded. This is originally a tabletop game, and each player has two neighbors : on his left and on his right. Unfortunately, the Map Neighbor PlayerId only means that a player can have up to two neighbors (there are only two constructors in the Neighbor type), and it doesn’t even garantee they have a corresponding state in the GameState.

A type that would properly model this property would be to store [(PlayerId, PlayerState)] in GameState, interpreted as a circular list (the first player in the list being the right neighbor of the last one). But this would be a major PITA to manipulate.

Another idea would be to store the neighboring information in a read-only structure. That way, we can make sure that no invariants are being violated, as the structure can’t be modified, but this also might be too much of a hassle. I will probably refactor some of this for the next episode with something less challenging : a simple pair.

And now, the monad !

As we have seen, we will need a MonadState GameState to model most of the rules. Some parts of the game might also throw errors, so it might be a good idea to have our monad be an instance of MonadError. Finally, we need some user interaction. In order to be able to write any backend, I decided to keep it abstract for now :

<figure class="code"> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 type GameStateOnly m = ( MonadState GameState m , Monad m , Functor m , Applicative m) 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 -- | Tell some information to a specific player tellPlayer :: PlayerId -> Message -> m () generalMessage :: Message -> m () -- ^ Broadcast some information </figure>

First of all are two constraints synonyms :

  • GameStateOnly : basically MonadState State with all the implied constaints, which will be used in all the functions that can’t fail and that don’t require user interaction.
  • NonInteractive : just like the previous constraint, but for functions that can throw errors.

Finally, a GameMonad typeclass. The monad our game will work in must implement these four functions, which are all I found was needed for player communication :

  • playerDecision: this is the main interaction. Given all kinds of data, it asks the player to decide what he will do in the current turn.
  • askCard: there are two effects where a player must chose a card over a list (copy community, and play for free a card from the discard pile). This is what this function is about, at least for now.
  • tellPlayer: tells a specific message to a given player.
  • generalMessage: tells a message to all players. This might not be necessary, as we could just iterate over the list of players and use tellPlayer. On the other hand, for IRC or XMPP backends, it might make sense to display this information on a conversation channel, so that watchers can follow the game.

The reason why it might make sense to have such granularity (pure, GameStateOnly, NonInteractive, GameMonad) is twofold :

  • It is easier to reason about the functions.
  • The less “powerful” a function is, the easier it is to test.

What is important to note is that I can’t write arbitrary effects with just the GameMonad constraint. Even better, I know I should be careful only when using the first two functions, as they are the only ones where user input can creep in. This explains why the part of the code that deals with playerDecision is so full of checks.

The choice of a typeclass is debatable, as there probably will only be a single implementation. I chose to do so because it will let me write code without worrying about how the monad itself will be implemented. I will probably ditch the typeclass later.

One problem so far is that these functions don’t have the proper type. Indeed, what happens when I pass askCard an empty list ? How is the player supposed to provide a card ? The other problem now is what to do with this Message type. Right now, it’s a type synonym to String, but it will change for the next episode !

Various notes No error recovery

I decided not to have error recovery in the game rules description. This is the responsability of the “driver” (which will be described in a later post) to make sure sore losers can’t DoS the game. The game will just end on the first error it encounters.

Lenses everywhere

This code uses the lens library all over the place. This is not surprising, as it involves a lot of mangling of nested structures in the State monad. But the prisms are even better ! Here is an example :

<figure class="code"> 1 2 3 4 5 6 7 8 -- | Compute the money that a card gives to a player getCardFunding :: GameStateOnly m => PlayerId -> Card -> m Funding getCardFunding pid card = do stt <- use playermap -- note how we exploit the fact that ^. behaves like foldMap here let funding = card ^. cEffect . traverse . _GainFunding . to computeFunding computeFunding (n, cond) = countConditionTrigger pid cond stt * n return funding </figure>

The choice of writing this option in GameStateOnly is debatable, as it just needs a read only access to the state once, and might just have been like that :

<figure class="code"> 1 getCardFunding :: GameState -> PlayerId -> Card -> Funding </figure>

However, what is interesting is how it is working. Here is an anotated of how the funding function is composed :

<figure class="code"> 1 2 3 4 cEffect :: Traversal' Card [Effect] cEffect . traverse :: Traversal' Card Effect cEffect . traverse . _GainFunding :: Traversal' Card (Funding, Condition) cEffect . traverse . _GainFunding . to computeFunding :: Fold Card Funding </figure>

So basically we wrote a traversal that goes through all effects of a card, keeping those with the GainFunding constructor, extracting its arguments, and finally using them to compute a Funding.

Now, if I had written funding = card ^.. ..., I would have obtained a [Funding], that I could add with sum. But remember that we made sure that our numerical newtypes, such as Funding and Victory, had a monoid instance for addition. In that case, ^. (or view) will make a monoidal summary, meaning it will give me 0 if there were no matches, or the sum of these matches, which is exactly what I wanted.

Order of execution

In this game, order of execution is really important, as most actions are supposed to happen simultaneously, and some only at very specific steps. In particular, a players can “trade” a resource belonging to a neighbor in exchange for money. A naïve implementation would be something like :

<figure class="code"> 1 2 playermap . ix playerid . cFunds -= x playermap . ix neighbor . cFunds += x </figure>

But this would create a (risky) exploit : namely declaring that you want to trade more resource than what you have money for, hoping somebody else will trade with you and that this transaction will be processed before yours.

In order to fix this, the resolveExchange function only removes money from the current player, returning the set of bought resources and an AddMap PlayerId Funding, listing the money that needs to be given to the neighbors.

The AddMap newtype

The resolveAction function also returns this AddMap PlayerId Funding, and the payouts are only processed after all actions are resolved. In order to make the code nicer, we need this AddMap k v newtype to be Traversable and have a Monoid instance that does unionWith (+).

The code is here and is an example on how this is done. I also derived the Ix and At instances, even though I didn’t end up using them. Strangely, someone asked on the cafe mailing list how to do this.

The 7th turn

There are only 6 turns for each age. But there is a company stage that let players use the 7th card, at the end of an age. Instead of having a special case, this is done by having an optional 7th turn.

No tests

Despite my claim that my rules are easy to test, tests are horrible to write, as they need a big setup. For this reason I postponed writing them ;) This will be a good test of the “Haskell code almost works the first time it runs” theory.

Next time

I will refactor a bit, and introduce a custom pretty-printer that will work with multiple backends, so that it is possible to have a nice view of what is going on during play.

Categories: Offsite Blogs

How can I install a second version of GHC?

Haskell on Reddit - Mon, 05/12/2014 - 9:59am

I'm currently using Fedora 19 and have GHC 7.4 installed from the system package manager. I'd like to also install GHC 7.8 and was wondering what the best way to go about installing it was such that my current working GHC wasn't affected.

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

Philip Wadler: The EFF, Oracle, Google, and me: A Dangerous Decision

Planet Haskell - Mon, 05/12/2014 - 6:42am
Previously, I wrote of an amicus brief filed by the EFF in a case between Oracle and Google, of which I am a co-signatory. The decision is out, and it is worrying.
When programmers can freely reimplement or reverse engineer an API without the need to negotiate a costly license or risk a lawsuit, they can create compatible software that the interface’s original creator might never have envisioned or had the resources to create. Moreover, compatible APIs enable people to switch platforms and services freely, and to find software that meets their needs regardless of what browser or operating system they use. The freedom to reimplement APIs also helps rescue “orphan” software or data—systems whose creators have either gone out of business or abandoned their product in the marketplace. Today's decision puts all of that at risk, potentially handing Oracle and others veto power over any developer who wants to create a compatible program. What is worse, if today's decision is taken as a green light to API litigation, large and small software tech companies are going to have to divert more and more resources away from development, and toward litigation. That will be good for the legal profession—but not so good for everyone else. The case is far from over. Google may seek a hearing from the full court, or appeal to the Supreme Court. Alternatively, Google can focus on asserting its fair use defense, and hope that fair use can once again bear the increasing burden of ensuring that copyright spurs, rather than impedes, innovation.  We're confident that it can, but it shouldn't have to.
Categories: Offsite Blogs

Skills Matter - Mon, 05/12/2014 - 4:14am
Categories: Offsite Blogs

Is there a name for defining recursive functions as infinite lists of input/output pairs by zipping two inductive datatypes?

Haskell on Reddit - Mon, 05/12/2014 - 2:14am

Recursive functions are usually defined by directly calling a function inside its own body.

Nat = Z | S Nat double Z = Z double (S x) = S (S (double x)))

What if, instead of defining them this way, we just enumerated two recursive datatypes and zipped them?

To be more descriptive, mind the following functions:

enum Nat = [Z, S Z, S S Z, S S S Z ...] # a b = \x -> (zip (enum a) (enum b)) !! (elem x (enum a))

That is, enum enumerates elements of a recursive datatype. Now, using #, there is an interesting way to define some recursive functions.

Even = Z | S (S Even) double = Nat # Even

This makes double equivalent to:

double x = [(0,0),(1,2),(2,4),(3,6)...] !! x

In other words, instead of defining the function recursively, we just created an infinite list with the input/output pairs of that function, by zipping two recursive datatypes together. I never heard of this approach being used, so my question is: this there a name for this? Any relevant papers? What kinds of functions can be defined this way?

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

FP Complete: GHC 7.8, transformers 0.3, and lenient lower bounds

Planet Haskell - Mon, 05/12/2014 - 2:00am

In the Stackage maintainer's agreement, there's a section about keeping your package compatible with the newest versions of all dependencies. What the maintainer's agreement doesn't (yet) discuss is when it's important to be compatible with old versions of a package. The reasons for this are not immediately obvious, especially as it affects a smaller subset of the Hackage author population. This blog post will cover some of the reasons for this goal.

The original impetus for writing this was to get one specific message across: please continue supporting transformers-! For the explanation of why, please keep reading.

Non-upgradeable packages

The simplest case to discuss is packages like base and template-haskell. Not only are these packages shipped with GHC, but they cannot be upgraded. As a result, if you have a package that says base >= 4.7, it will only work with GHC 7.8 and later. Users who are still using 7.6 (or 7.4... or earlier... yes, those people do in fact exist) will have no means of using your package.

That of course brings up a question of how many versions of GHC you want to support. I'd highly recommend always supporting the most recent Haskell Platform release, as many users (especially Windows users) stick to that. Going back an extra version as well isn't a bad idea either, especially as some distributions (e.g., Ubuntu) tend to ship relatively old GHC versions.

Upgradeable, GHC-shipped packages

This issue is more subtle. In addition to non-upgradeable packages, GHC includes a number of packages which can be installed separately, resulting in one copy of the package in your global database, and one in your user database. (Yes, you can also install into the global database, but I'm covering the common case here.) Examples of these packages are bytestring, binary, and containers.

The first problem with this is that it can lead to end-user confusion. How many of you have tried working in GHCi, or just compiling code with ghc --make, and gotten a message along the lines of "Could not match type ByteString with ByteString"? That usually comes from two versions of a package being available.

Now that's just a bit of an annoyance, and building your code with cabal will almost always avoid it. But there's a second, more serious problem. Some of these upgradeable packages are in turn depended upon by non-upgradeable packages. For example, template-haskell depends on containers. As a result, imagine if you try to use containers 0.5 and template-haskell when on GHC 7.4. Since template-haskell depends on containers-, you'll run into issues.

Another problem is the ghc package (aka GHC-the-library). With GHC 7.8.2, I have the following dependencies for the installed ghc package:

depends: Cabal- array- base- bin-package-db- bytestring- containers- directory- filepath- hoopl- hpc- process- template-haskell- time-1.4.2-b47642c633af921325b5eb4d5824b9de transformers- unix-

So if I try to use- for example- transformers and a package requiring ghc at the same time, I'll run into a conflict. And there are actually a large number of such packages; just doctest has over 100 dependencies.

Haskell Platform

The last reason is the one I hear the most pushback about from package authors. The Haskell Platform pegs users at specific versions of dependencies. For example, the most recent HP release pegs text at Now imagine that you write a package that depends on text >= 1.0. A user with the Haskell Platform installed will likely get warnings from cabal when installing your package about conflicting versions of text, and possibly breaking other packages that depend on it.

I can tell you what I've personally done about this situation. For my open source packages, I make sure to keep compatibility with the Haskell Platform released version of a package. Sometimes this does lead to some ugliness. Two examples are:

  • streaming-commons has to have a copy of some of the streaming text code, since it was not available before text 1.1. (And due to an issue with cabal, we can't even conditionally include the code.)
  • In chunked-data, I wasn't able to rely upon the hGetChunk function, and instead needed to use CPP to include a far less efficient backup approach when using older versions of text.

In the Stackage project, I run versions of the build both with and without Haskell Platform constraints. There are actually a whole slew of conditionals in the version selection which say "if you're using HP, then use this older version of a dependency." However, as time goes on, more and more packages are simply not supporting the HP-pegged versions of packages anymore.

Future changes

I'm not commenting here on the value of HP-pegged versions, but simply pointing out a reality: if you want your users to have a good experience, especially Windows users, it's probably a good idea to keep compatibility with the older HP-provided versions. I also think the ramifications of the HP approach really need to be discussed by the community, it seems like there's not much discussion going on about the impact of the HP.

Also, regarding the packages shipped with GHC: there have certainly been discussions about improving this situation. I know that removing the Cabal dependency from ghc has been discussed, and would certainly improve the situation somewhat. If others want to kick off a conversation on improving things, I'd be happy to participate, but I frankly don't have any concrete ideas on how to make things better right now.

Categories: Offsite Blogs

Error when trying to use Hashable

haskell-cafe - Mon, 05/12/2014 - 1:58am
Hi Haskell Cafe, I have some code that compiles when running on GHC on OS X, but not on Ubuntu: No instance for (hashable- (GHC.Generics.Rep Point)) arising from a use of `hashable-$gdmhashWithSalt' Possible fix: add an instance declaration for (hashable- (GHC.Generics.Rep Point)) In the expression: (hashable-$gdmhashWithSalt) In an equation for `hashWithSalt': hashWithSalt = (hashable-$gdmhashWithSalt) In the instance declaration for `Hashable Point' Anyone know what's happening here? Cheers, -John
Categories: Offsite Discussion

Installation of package text failing installation onghc 7.6.3

haskell-cafe - Sun, 05/11/2014 - 9:46pm
I just downloaded the latest Haskell platform (I realize that ghc might not be up-to-date in this) for my macbook. I installed it, which appeared to go without problems. However, when I tried to update the package text, I get the errors below. I suspect that the first error (not recognizing ' in a comment) cascades through the rest. How do you suggest fixing this (other than getting Bryan do drop the apostrophe :-))? Victor Configuring text- Building text- Preprocessing library text- Data/Text.hs:9:52: warning: missing terminating ' character [-Winvalid-pp-token]
Categories: Offsite Discussion

ANNOUNCE: jhc-0.8.1

General haskell list - Sun, 05/11/2014 - 9:20pm
After a hiatus, jhc 0.8.1 is released. - New license, jhc is now released under a permissive BSD style licence rather than the GPL. The license is compatible with that of ghc allowing code mixing between them. - New library layout based around the standards, there are now haskell98 and haskell2010 packages that are guarenteed to be future proof strictly compatible with the respective standards. A package haskell-extras contains the additonal libraries from ghc's base. - Native support for complex and vector SIMD primitives, exposed via type functions. for instance 'foo :: Complex_ Float32_' for hardware accelerated complex 32 bit floats for instance. These are unboxed only for now, full library Num support in the works. - support for android as a target, you must install the android NDK to use this. - Support for embedded ARM architectures imported from Kiwamu Okabe's branch allowing targeting bare hardware with no OS. - user defined kinds, introduced
Categories: Incoming News

Why doesn't cabal compile once and manage binary packages?

Haskell on Reddit - Sun, 05/11/2014 - 5:19pm

Someone was asking about cabal on #haskell just earlier tonight, specifically what it does do and what it does not do, and a discussion ensued. I commented that once I understood why sandboxes were needed at all, I had somewhat of an epiphany in the sense that now I cannot begin to fathom why cabal was implemented the way it was to begin with.

That is to say, as cabal is a tool that is (with caveats) used for downloading libraries to use in development of software, it makes practically 0 sense for it to install packages to a global repository, when the very nature of software development means that you might need to be working on different programs that require different versions of the same package.

One guy in IRC(timthelion) pointed out that there had been a project called hellno( that manages cabal packages by only building them once and then copying binary packages of the correct versions around as needed.

So, I was wondering: why doesn't cabal do this? Is there an effort to do something like this, etc? I ask here because it wouldn't surprise me there are some parts of the picture I might be missing completely, as I don't really know much about the intricacies of package management. I know that with sandboxes, we basically get the same thing, but we have to build the packages from scratch. But IMO, that is more than a minor inconvenience, considering the dependency graphs of some packages.

submitted by IceDane
[link] [22 comments]
Categories: Incoming News

cabal install lens fails

haskell-cafe - Sun, 05/11/2014 - 3:29pm
Hi Haskell Cafe, Anyone know about this error? Installing library in /Users/johnky/Library/Haskell/ghc-7.6.3/lib/reflection-1.4/lib Registering reflection-1.4... Installed reflection-1.4 Configuring mtl- Building mtl- Preprocessing library mtl- [ 1 of 21] Compiling Control.Monad.Writer.Class ( Control/Monad/Writer/Class.hs, dist/build/Control/Monad/Writer/Class.o ) [ 2 of 21] Compiling Control.Monad.State.Class ( Control/Monad/State/Class.hs, dist/build/Control/Monad/State/Class.o ) [ 3 of 21] Compiling Control.Monad.Reader.Class ( Control/Monad/Reader/Class.hs, dist/build/Control/Monad/Reader/Class.o ) [ 4 of 21] Compiling Control.Monad.RWS.Class ( Control/Monad/RWS/Class.hs, dist/build/Control/Monad/RWS/Class.o ) [ 5 of 21] Compiling Control.Monad.Identity ( Control/Monad/Identity.hs, dist/build/Control/Monad/Identity.o ) [ 6 of 21] Compiling Control.Monad.Error.Class ( Control/Monad/Error/Class.hs, dist/build/Control/Monad/Error/Class.o ) Control/Monad/Error/Class.hs:93:18
Categories: Offsite Discussion

Dominic Steinitz: Hölder’s and Minkowski’s Inequalities

Planet Haskell - Sun, 05/11/2014 - 2:45pm

I have seen Hölder’s inequality and Minkowski’s inequality proved in several ways but this seems the most perspicuous (to me at any rate).

Young’s Inequality

If and such that


A and satisfying the premise are known as conjugate indices.


Since is convex we have

Substituting in appropriate values gives


Now take exponents.

Hölders’s Inequality

Let and be conjugate indices with and let and then and


By Young’s inequality

By applying a counting measure to we also obtain

Minkowski’s Inequality


By Hölder’s inequality


and is finite since is a vector space.

Categories: Offsite Blogs