News aggregator

language-puppet: 7 Startups - part 1 - Introduction and types

Planet Haskell - Sat, 05/10/2014 - 2:14am

There have been recently complaints that there wasn’t any resource available for bridging the gap between beginner and experimented Haskeller, and some posts on “Haskell program architecture” have been written to help with this transition. I have found these posts to be pretty interesting, and while I can hardly be called an expert, I would like to contribute to this effort by documenting a few advanced Haskell features, as well as my design decisions, applied to a simple, yet fun, project.

Now that this is out of the way, let’s start !

The project

In this series of posts, I will describe how to model the rules of a well known board game, and how to turn them in an enjoyable program. If time permits, quite a few topics should be discussed, including key design decisions, how to interface a pure description of the rules with multiple backends, concurrency with the STM, and the advantage of always pretty printing your data structures.

The game itself is a shameless clone of the excellent 7 Wonders game (you can find the rules on the official web site), but with Internet giants instead of antique wonders. The theming took me a long time, and I am not particularly satisfied with it, so if you feel like contributing, please give me better names for the cards and resources.

All the code is on github. I will document my decisions and actions as I go, and will tag the repository accordingly. The relevant version for this article is tag Step1.1.

The types Startups.Base

The Startups.Base module contains all the base elements of the game, with the relationship with the original game written the comments. While all the types are more or less directly transcribed from the rules book, the newtyped numerical types might not be obvious :

<figure class="code"> 1 2 3 4 5 6 7 8 9 10 11 newtype Poacher = Poacher { getPoacher :: Integer } deriving (Ord, Eq, Num, Integral, Real, Enum, Show) newtype VictoryPoint = VictoryPoint { getVictory :: Integer } deriving (Ord, Eq, Num, Integral, Real, Enum, Show) newtype Funding = Funding { getFunding :: Integer } deriving (Ord, Eq, Num, Integral, Real, Enum, Show) newtype PlayerCount = PlayerCount { getPlayerCount :: Integer } deriving (Ord, Eq, Num, Integral, Real, Enum, Show) </figure>

All the derived instances let you use them just like a standard Integer in your code, and the newtype prevents you from mixing them. But the main advantage is that it will make functions type signatures a lot more informative.

Startups.Cards

I usually would have merged this module with the previous one, but for the sake of blogging about it I separated the two. This module is all about modeling the cards. Fortunately, the cards have an obvious representation. But what about the Effect type ?

Modeling the effects

With a functional language, there are several ways to go :

  • Have some big case statements all over the code that depend on the card names, the effects being encoded where they are needed. This is obviously bad, as it will lead to a lot of verbose code, and it will be a pain to refactor the code.
  • Have the effect described as a state-changing function (ie. type Effect = PlayerId -> GameState -> GameState). This is the most versatile option, as it lets you add new cards with funky effects without modifying other parts of the code. Unfortunately, your program no longer have an easy way to “observe” the effect, so you will need to write a human-readable description for each card. It might be hard to write an AI for this game too (this point is debatable). There is also the problem of reasoning about new effects, especially concerning the order of application of the effects. A common workaround is to add a “priority” field, so that the order of application is known.
  • Fully describe all effects with a data type. This is the approach we are going to take, as it has obvious advantages in this particular case : most cards can be described with a handful of distinct “effect components”, where the components are orthogonal. This means they should be implemented in the part of the code that are relevant. It will be quite easy to describe arbitrary effects to the user too.

All the possible effects components can be seen here. Some components have no parameters (such as Recycling), meaning they model a specific rule. But what is nice about this data type is that it models the effects of the cards, but also of the company building stages.

Precise types

The following types are not as obvious as they appear :

<figure class="code"> 1 2 3 4 5 6 7 data Neighbor = NLeft | NRight deriving (Ord, Eq, Show) data EffectDirection = Neighboring Neighbor | Own deriving (Ord, Eq, Show) </figure>

My first version was something like :

<figure class="code"> 1 2 3 4 data EffectDirection = NLeft | Own | NRight deriving (Ord, Eq, Show) </figure>

This was simpler, but some effects have no meaning when applied to the current player (such as reduced exchange rates). This will make pattern matching a bit more cumbersome, but it will probably prevent some mistakes.

Modeling the cost

What is more interesting is the Cost data type.

<figure class="code"> 1 2 data Cost = Cost (MS.MultiSet Resource) Funding deriving (Ord, Eq, Show) </figure>

A MultiSet is a collection of objects that can be repeated but for which order is not important (you can also think of it as a sorted list). It perfectly models a resource cost, such as “3 operations, and a marketing”, and it provides us with a isSubsetOf operation that can directly tell whether a player has enough resources to play some card. There is an obvious Monoid instance for it :

<figure class="code"> 1 2 3 instance Monoid Cost where mempty = Cost mempty 0 Cost r1 f1 `mappend` Cost r2 f2 = Cost (r1 <> r2) (f1 + f2) </figure>

I don’t think this instance will be too useful, except for writing this cleanly :

<figure class="code"> 1 2 3 4 5 6 7 8 9 10 11 12 instance IsString Cost where fromString = F.foldMap toCost where toCost 'Y' = Cost (MS.singleton Youthfulness) 0 toCost 'V' = Cost (MS.singleton Vision) 0 toCost 'A' = Cost (MS.singleton Adoption) 0 toCost 'D' = Cost (MS.singleton Development) 0 toCost 'O' = Cost (MS.singleton Operations) 0 toCost 'M' = Cost (MS.singleton Marketing) 0 toCost 'F' = Cost (MS.singleton Finance) 0 toCost '$' = Cost mempty 1 toCost _ = error "Invalid cost string" </figure>

When the OverloadedStrings extension is enabled, the compiler will accept strings in places where another type is expected, by adding a call to the fromString function. For example, "YYY" :: Cost will be replaced by fromString "YYY" :: Cost.

I don’t think this is good practice to advise others to write partial IsString instances, but it greatly helped with writing the card list, speaking of which …

Tests

Writing the first card list was the most tedious and error prone part of this endeavor. In order to make sure I did not introduce a typo, I performed a couple of tests on the card list :

  • All cards are distinct (got a bug).
  • For every number of players and ages, there are 7 cards for each player (there were three errors).
What could have been better Ord instances

Most data types now have Ord instances that are not particularly meaningful. They are here so that the data structures can be used in the standard containers types, such as Data.Map.Strict and Data.Set. It might have been a better idea to use unordered-containers, but this would have meant more boilerplate (for deriving all the Hashable instances).

Why not use an external DSL for describing the cards ?

This indeed would have been a good idea, and wouldn’t have been particularly hard to write. I don’t think it would have added much to the project at this stage though.

Modeling the “Opportunity” effect

This effect currently looks like this : Opportunity (S.Set Age). It is used to describe the fact that a given player can build for free any card, once per age. The Set will contain the set of Ages for which this capacity has not been used. This means that when the player decides to use this capacity, this effect will need to be updated. If this wasn’t for this effect, a player card list would only be modified by adding a card to it, which would have been more pleasant.

Card and Company stages

When I started writing this post, the Card type had a single constructor, and there was a CardType that was not part of the rules used to describe a company stage. I did that because I thought it was more elegant to unify cards and company stages, as they were pretty similar (both have costs and effects that work the same way).

It turned out that I had to enter dummy values for player count, age, card name, etc. for these “cards”. Now there is an additional constructor for company building stages, as can be seen in this commit.

Next time

In the next episode, I will start writing the game rules, starting with choosing (or not) the proper abstraction for describing them. In the meantime, do not hesitate commenting (reddit link) !

Categories: Offsite Blogs

Using mutable array after an unsafeFreezeArray, and GC details

glasgow-user - Fri, 05/09/2014 - 7:21pm
A couple of updates: Edward Yang responded here, confirming the sort of track I was thinking on: http://blog.ezyang.com/2014/05/ghc-and-mutable-arrays-a-dirty-little-secret/ And I can report that: 1) cloning a frozen array doesn't provide the benefits of creating a new array and freezing 2) and anyway, I'm seeing some segfaults when cloning, freezing, reading then writing in my library I'd love to learn if there are any other approaches I might take, e.g. maybe with my own CMM primop variants? Thanks, Brandon
Categories: Offsite Discussion

[TFPIE2014] final call for participation

haskell-cafe - Fri, 05/09/2014 - 2:37pm
[FINAL CALL FOR PARTICIPATION] 3rd International Workshop on Trends in Functional Programming in Education (TFPIE 2014) May 25, 2014 Utrecht University Soesterberg, The Netherlands (http://www.cs.uwyo.edu/~jlc/tfpie14/) The 3rd International Workshop on Trends in Functional Programming in Education, TFPIE 2014, will be co-located with the Symposium on Trends in Functional Programming (TFP 2014) at Soesterberg, at the “Kontakt der Kontinenten” hotel in the Netherlands on Sunday, May 25th. TFP will follow from May 26-28. The goal of TFPIE is to gather researchers, teachers and professionals that use, or are interested in the use of, functional programming in education. TFPIE aims to be a venue where novel ideas, classroom-tested ideas and work-in-progress on the use of functional programming in education are discussed. The one-day workshop will foster a spirit of open discussion by having a review process for publication after the workshop. The program chair of TFPIE 2014 will screen submis
Categories: Offsite Discussion

Templates as typeclasses?

haskell-cafe - Fri, 05/09/2014 - 11:55am
Tobias Dammers wrote: In this regard it is worth mentioning HSXML http://okmij.org/ftp/Scheme/xml.html#typed-SXML The document in HSXML is a monoid rather than a monad. It is hard to find a good reason for the document be a monad except for using a do notation, which is not needed in HSXML. The above "Hello, World!" example looks in HSXML as h1 (span "Hello") (span "world!") (Note that we don't need the space after `Hello'.) This produces the desired output (in plain text, HTML or XML). If we don't need span, we can just write h1 "Hello" "world!" The main difference from Blaze shows up if we attempt h1 (p "Hello") "world!" It will be a type error. The error message says No instance for (Build (DC CT_inline d0) (DC CT_block d0) t) arising from a use of `h1' No instance for (Build (DC CT_inline d0) (DC CT_block d0) (DC CT_inline d0)) arising from a use of `p' That is, (p "Hello") produces block-level content and h1 requires its ch
Categories: Offsite Discussion

Brazilian type checking

del.icio.us/haskell - Fri, 05/09/2014 - 1:11am
Categories: Offsite Blogs

Using mutable array after an unsafeFreezeArray, and GC details

glasgow-user - Fri, 05/09/2014 - 12:18am
I have an unusual application with some unusual performance problems and I'm trying to understand how I might use unsafeFreezeArray to help me, as well as understand in detail what's going on with boxed mutable arrays and GC. I'm using the interface from 'primitive' below. First some basic questions, then a bit more background 1) What happens when I do `newArray s x >>= \a-> unsafeFreezeArray a 2) And what if a do a `cloneMutableArray` on `a` and likewise use the resulting array? Background: I've been looking into an issue [1] in a library in which as more mutable arrays are allocated, GC dominates (I think I verified this?) and all code gets slower in proportion to the number of mutable arrays that are hanging around. I've been trying to understand how this is working internally. I don't quite understand how the "remembered set" works with respect to MutableArray. As best I understand: the remembered set in generation G points to certain objects in older generations, which objects hold references to ob
Categories: Offsite Discussion

New gtk2hs 0.12.4 release

gtk2hs - Wed, 11/21/2012 - 12:56pm

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

~d

Categories: Incoming News