Stackage LTS and GHC 8.0

The release of GHC 8.0.1 has recently been announced. Hooray! People are already asking about when LTS Haskell will include the new GHC. While I’m also excited for this to happen as soon as possible, it’s worth taking a look at what happened last time in order to set realistic expectations.

Here’s the rough timeline as observed last year:

It took about 4.5 months from the release of GHC 7.10 until its inclusion in Stackage LTS.

I’d like to see this time span shortened, but I don’t expect it to be much shorter this time around. Here’s an optimistic estimate of how I expect it to go down. This is just my personal estimate; specific timeline decisions are still being discussed amongst the Stackage curators.

* May 21: GHC 8.0.1 release announced
* June: Stackage LTS 6.0 released using GHC 7.10.3 (again)
* June: Stackage nightly switched to GHC 8.0.1
* Sept: Stackage LTS 7.0 released with GHC 8.0.1

There are a few reasons we might delay the release of LTS 7.0 with GHC 8.0.

First and foremost is the obvious: the whole package ecosystem needs to be ready. I am optimistic that this can be accomplished by September. Perhaps sooner. I expect some nightly snapshots to be available in the next few weeks that will be quite useable, if not the full Stackage experience.

Another reason to delay an LTS is because each LTS lasts for a minimum of 3 months before we start the next one (except in the case of LTS 4 which we cut short due to issues with aeson-0.10). LTS 5 has been around for about 4 months, and we’re itching to make a new LTS with aeson-0.11. So we intend to release LTS 6 soon, and then it’ll be at least 3 months until LTS 7.

One more reason to delay an LTS is because each LTS is also pegged to a particular compiler version. If GHC 8.0.2 is close to being released, we’ll probably want to delay the next LTS until it is released, like we did last year with GHC 7.10.2.

I hope this sets some clear expectations and explains some of the reasons why LTS Haskell is probably going to take a couple months to adopt GHC 8.0. LTS Haskell isn’t on bleeding edge, and that’s the whole point. LTS Haskell lags a little behind the latest and greatest in order to deliver a stable and cohesive Haskell experience.

Posted in Uncategorized | 1 Comment

Stackage is reverting to aeson-0.9

Starting immediately, Stackage nightly builds will be stepping back from aeson-0.10.0.0 to aeson-0.9.0.1. Due to issues with aeson-0.10, we are planning to discontinue LTS 4. Next Sunday (2016-01-24) we will begin LTS 5, which will ship with aeson-0.9.

Under normal circumstances, the support duration of an LTS Haskell series is 3 months at minimum. We believe that, in retrospect, the inclusion of aeson-0.10 in LTS Haskell was premature, and we felt it necessary to take quick action to reverse this mistake. We anticipate that LTS 5 and onward will be supported for the usual 3+ months.

Looking forward, we hope that LTS 6 (around April/May 2016) will be able to incorporate ghc-8. Several patches for aeson can be seen in the pipeline, so we also hope that LTS 6 will be able to include a new version of aeson with all of these improvements. Aeson is a key component of the Haskell ecosystem, and we thank Bryan O’Sullivan and aeson contributors for the hard work that has gone into it. We also thank all of the downstream package authors that have been working hard to keep pace.

Posted in Uncategorized | 1 Comment

What to do with aeson-0.10?

aeson-0.10.0.0 has been out since September 2015. Aeson is widely used, and adoption of the new version was fairly slow. The changelog claims, “the API changes below should be upwards compatible from older versions of aeson. If you run into upgrade problems, please file an issue with details.”

An issue was immediately filed: Breaking changes on 0.10 regarding Null field parsing on Maybe types. (This issue remains open.)

Not long after, another issue was filed: 0.10 causes Couldn’t match expected type `Data.Text.Internal.Text’ with actual type `Data.ByteString.Builder.Internal.Builder’ (This issue was addressed fairly quickly.)

I’m not going to rehash every single issue and bugfix, but the point is that a handful of bugs have been fixed since the 0.10.0.0 release, and a few regressions still haven’t been fixed. However, what bugfixes there are have not yet been published to Hackage.

When LTS Haskell 4.0 was released with aeson-0.10, one particularly nasty regression came back into the spotlight: GHC Killed with out of memory when using generics.

Stackage curators tend to agree that including aeson-0.10.0.0 in LTS Haskell was a mistake. So, where do we go from here? We have a few options.

* Revert to aeson-0.9
* Use a “compatibility layer” package
* Wait for a patch to aeson-0.10

How have you been dealing with aeson-0.10? Did its inclusion in LTS Haskell have any impact on you and your projects? How can we improve the way we deal with situations like this in the future?

Posted in Uncategorized | Leave a comment

An informal explanation of stackage-sandbox

Works on my machine, will it work on yours?

Suppose there’s a Haskell project called stackage-cli that I’d like to share with you. It builds just fine on my machine, but will it build on yours? If we have different versions of installed Haskell packages, we might run into cabal hell trying to sort things out.

To start off, let’s first agree on using ghc-7.8.4 and cabal-install-1.20.0.3. (In this blog post, I’ll assume you are able to install these somehow. Next time I might have some more to say about how to get this far.)

Next, let’s agree to use the same package versions for the dependencies. Cabal provides a handy command to help with this: cabal freeze. This creates a file called cabal.config which lists package constraints. Here’s what I got when I did a cabal freeze on the project as built on my machine: http://lpaste.net/130815.

It would be rather tedious for you to blow away your entire package database, start fresh, and install these exact versions of dependencies. Thankfully, there’s a better way.

cabal sandbox

You don’t have to blow away your whole package database just to build this project I want to share with you. You can instead create a “cabal sandbox” just for this project. Then you can install the dependencies there.

I did a cabal freeze when I was on git commit 9b68a74, so let’s check out that particular version.

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.8.4
$ cabal --version
cabal-install version 1.20.0.3
using version 1.20.0.0 of the Cabal library 
$ git clone git@github.com:fpco/stackage-cli
$ cd stackage-cli
$ git checkout 9b68a74
$ wget -O cabal.config http://lpaste.net/raw/130815
$ cabal sandbox init
$ cabal install --only-dependencies -j && cabal build

And now we wait for the dependencies to install. Maybe take a bathroom break, grab a coffee. This took about 8 minutes on my machine. Presumably, it worked, and we have successfully avoided a trip through cabal hell. Not bad, but we can do even better.

shared sandboxes

Local cabal projects can share local sandboxes. So, if you happen to be working on different projects that have the exact same dependency versions, you can safely share one sandbox between the various projects. If they have differing dependency versions, then you’re in cabal hell territory. You might get it to work. You might have some butterflies to battle. It’s probably easier to just have different sandboxes in that case.

Let’s check out the same project and rebuild it against the same sandbox.

$ git clone git@github.com:fpco/stackage-cli
$ cd stackage-cli
$ git checkout 9b68a74
$ cp ../cabal.config ./cabal.config
$ cabal sandbox init --sandbox ../.cabal-sandbox
Writing a default package environment file to
/home/dan/stackage-cli/stackage-cli/cabal.sandbox.config
Using an existing sandbox located at /home/dan/stackage-cli/.cabal-sandbox

See how it said “using an existing sandbox”, because we told it which sandbox to reuse?

$ cabal install --only-dependencies
Resolving dependencies...
All the requested packages are already installed:
Use --reinstall if you want to reinstall anyway.
$ cabal build

No need to reinstall the dependencies. They’re all there. The build itself took under 30 seconds on my machine.

The exact same dependencies? Really?

Suppose someone else wants your help developing a different project. It seems pretty unlikely that she and I would just happen to be using the exact same dependency versions.

Suppose you’re starting up your own project. How do you pick dependency versions that will work together? Just cabal install dependencies as they arise and cross your fingers?

Stackage

FP Complete has developed a project called Stackage.org that is meant to help with these concerns. The main service provided by Stackage.org that we will make use of in this blog post is the cabal.config files it provides. Remember how we got our cabal.config via cabal freeze, which allowed me to share with you the dependency versions that worked for me? Stackage provides cabal.config files that include dependency constraints for a very large subset of Hackage. These dependency versions are known to all work together. New builds are calculated nightly, but to provide a more stable point of reference, LTS Haskell is also available.

So here’s an idea: create a shared sandbox on your machine with only LTS Haskell packages inside. Let’s create a location for lts-2.3 and install things there. We’ll make sure to use the lts-2.3 cabal.config with our project, so that only lts-2.3 packages get installed into the shared sandbox.

$ git clone git@github.com:fpco/stackage-cli
$ cd stackage-cli
$ git checkout 9b68a74
$ mkdir -p ~/.stackage/sandboxes/ghc-7.8.4/lts-2.3/
$ wget -O cabal.config http://stackage.org/snapshot/lts-2.3/cabal.config
$ cabal sandbox init --sandbox ~/.stackage/sandboxes/ghc-7.8.4/lts-2.3/
$ cabal install --only-dependencies -j

Since this is the first time anything has been installed to that sandbox, it will take the same 8 minutes as before. But only the first time. Now, any of my other projects that can be developed against lts-2.3 can share those same dependencies! No need to reinstall the same dependencies over and over into fresh sandboxes for each project.

The stackage command line interface

Installation

The stackage-cli project provides a tool that automates some of these processes for you. Move out of these sandboxed project directories and do cabal install stackage-cli to install it to your usual place. If that fails, then use the sandbox tricks I’ve described above to install it into a sandbox:

$ mkdir sandboxed-dir
$ cd sandboxed-dir
$ wget -O cabal.config http://stackage.org/lts/cabal.config
$ cabal sandbox init
$ cabal update
$ cabal install stackage-cli

You can see where the binaries got installed with cabal exec, which lets you execute commands “in the sandbox context”:

$ cabal exec which stackage
/home/dan/sandboxed-dir/.cabal-sandbox/bin/stackage

Copy the various binaries named stackage and stackage-* onto your path, or add that bin directory to your path. Let’s review the functionality provided by the stackage command-line tool.

Managing cabal.config and a pre-configured sandbox

First off, is stackage purge, which deletes your current cabal.config and prompts you to unregister everything in your sandbox. If you don’t have a sandbox configured, it will instead prompt you to unregister from your global package database.

$ stackage purge
(Sandbox) /home/dan/.stackage/sandboxes/ghc-7.8.4/lts-2.3/x86_64-linux-ghc-7.8.4-packages.conf.d
Detected 221 packages to purge from this database
Unregister 221 packages (y/n)? [default: n] 

I don’t actually want to purge that shared sandbox, so I chose the default: no. As you can see, I’ve installed a lot of packages in there that I’d rather not purge. If you have a non-shared project sandbox, you may want to purge it prior to stackage init.

Indeed, next up is stackage init. This just downloads the appropriate cabal.conig for you.

$ stackage init lts-2.3

Leave off the lts-2.3 argument and it will just download the latest LTS. You can also use stackage upgrade which is simply purge followed by init.

These three commands are not particularly aware of shared sandboxes. You can use stackage sandbox to automatically set up and use LTS-based shared sandboxes.

Managing cabal.config, cabal.sandbox.config and shared sandboxes

$ stackage sandbox delete

This command deletes both your cabal.config and your cabal.sandbox.config. It doesn’t touch your actual sandbox unless you give it an argument. There are certian sandboxes that are managed by stackage sandbox, and it can help you delete them so you don’t have to go looking to see where they are.

$ stackage sandbox delete lts-2.3

I didn’t actually run that command, though, because I don’t actually want to delete my precious lts-2.3 sandbox, because it has 221 packages that I really don’t want to bother reinstalling until the next LTS release.

$ stackage sandbox init lts-2.3

This does a couple things.

  • It downloads the lts-2.3 cabal.config
  • It creates a folder for the lts-2.3 shared sandbox, if it doesn’t already exist
  • It calls cabal sandbox init with the --sandbox argument set to the lts-2.3 shared sandbox

In other words, it readies your project to be built with your shared lts-2.3 sandbox.

You can easily do a delete followed by an init by using:

$ stackage sandbox upgrade lts-2.3

This leaves your old sandbox intact, wherever it was, but replaces your cabal.config and cabal.sandbox.config with the appropriate configurations for the lts-2.3 shared sandbox (which it also sets up if necessary). stackage sandbox upgrade is the command I recommend using most of the time.

Build it again

Remember this example from before?

$ git clone git@github.com:fpco/stackage-cli
$ cd stackage-cli
$ git checkout 9b68a74
$ mkdir -p ~/.stackage/sandboxes/ghc-7.8.4/lts-2.3/
$ wget -O cabal.config http://stackage.org/snapshot/lts-2.3/cabal.config
$ cabal sandbox init --sandbox ~/.stackage/sandboxes/ghc-7.8.4/lts-2.3/
$ cabal install --only-dependencies -j

We can replace the wget and cabal sandbox init commands with stackage sandbox upgrade, and accomplish the same thing.

$ git clone git@github.com:fpco/stackage-cli
$ cd stackage-cli
$ git checkout 9b68a74
$ stackage sandbox upgrade lts-2.3
$ cabal install --only-dependencies -j

Again, since we’ve already installed this package’s deps there, there should be nothing new to install.

Summary

Let’s recap the main ideas behind stackage sandbox upgrade.

  • LTS Haskell provides a common platform of dependency versions for developers to develop against. It stays fresh enough to remain relevant, but stable enough to provide a solid point of reference.
  • Shared sandboxes allow you to develop your various projects against the same platform. No more reinstalling all-the-things for every single project.
  • stackage sandbox upgrade helps you to easily manage your shared sandboxes based on LTS Haskell

Upgrade your sandboxes to Stackage! Or if you want to customize the workflow, then mix and match whichever commands provided by stackage that you find convenient. You can even develop your own executable as a “stackage-cli plugin”. Any executable on your path with a name that starts with “stackage-” will be treated as a plugin, and you’ll notice that stackage-init, stackage-purge, stackage-upgrade, and stackage-sandbox are all simply plugins.

How is this different than Halcyon?

Halcyon is a project focused on installation of Haskell executables. In contrast, the stackage command line tool is focused on aiding development of Haskell projects.

Future work

We still haven’t gotten rid of all of the tedium in this process yet. For example, imagine that we both remotely log in to the same machine; we could share build artifacts! But that’s unrealistic. Instead, we can agree on using the same kernel or VM; that way we can share build artifacts between machines.

That’s roughly the idea behind docker, and FP Complete is working on docker-based build tools. It’s also roughly what Halcyon does, and we want to extend this benefit to development, not just installation.

Your feedback is more than welcome on the issue tracker.

https://github.com/fpco/stackage-cli/issues

Further reading

For a more nuanced example of stackage-cli, check out the project wiki on github:

https://github.com/fpco/stackage-cli/wiki/Example

Posted in Uncategorized | 1 Comment

Similarities: Monoid, MonadPlus, Category

This is perhaps obvious to anyone who has thoroughly studied category theory, but the similarities between Monoid, MonadPlus, and Category, have really struck me lately. I’m going to take a smidgeon of artistic license to present this train of thought.

class Monoid (a :: *) where
  mempty :: a
  (<>) :: a -> a -> a

class MonadPlus (m :: * -> *) where
  mzero :: forall x. m x
  (<+>) :: forall x. m x -> m x -> m x

class Category (c :: * -> * -> *) where
id :: forall x. c x x
(>>>) :: forall x y z. c x y -> c y z -> c x z

These classes all come with the same set of laws.

id >>> x = x -- left identity
x >>> id = x -- right identity
(x >>> y) >>> z = x >>> (y >>> z) -- associativity

I’d like to present three structures, which correspond to some sort of “free” instance. Notice how they all have the same shape. (I added a superfluous unit to the Nat to make the parallel just a little clearer.) I put “free” in quotes because I do not claim to actually understand what this means in category theory, nor do I claim to be using that term correctly in the category theoretic sense. I’m pretty sure I’m somewhat close to that definition, though.

My “free” Monoid is the natural numbers. Inexplicably, I’m going to do something weird and hide an arbitrary value inside the succ constructor. Just pretend that “v” isn’t there if it confuses you. It’s just the nats.

data Nat where
  Zero :: Nat
  Succ :: v -> Nat -> Nat
instance Monoid Nat where
  mempty = Zero
  Zero y = y
  Succ v x <> y = Succ v (x <> y)

My “free” MonadPlus is homogeneous lists.

data List x where
  Nil :: List x
  Cons :: x -> List x -> List x
instance MonadPlus List where
  mzero = Nil
  Nil my = my
  Cons x mx <+> my = Cons x (mx <+> my)

My “free” category is… a little more abstract than the last two. It’s extending any type relation with reflexivity and transitivity (regardless of whether the original relation includes reflexivity and transitivity).

data ReflTrans (rel :: * -> * -> *) :: * -> * -> * where
  Refl :: ReflTrans rel x x
  Trans :: rel x y -> ReflTrans rel y z -> ReflTrans rel x z
instance Category (ReflTrans rel) where
  id = Refl
  Refl >>> yz = yz
  Trans rwx xy >>> yz = Trans rwx (xy >>> yz)

Also note an added similarity between the three:

unity :: v -> Nat
unity v = Succ v Zero

singleton :: x -> List x
singleton x = Cons x Nil

liftRel :: rel x y -> ReflTrans rel x y
liftRel r = Trans r Refl

infinity :: () -> Nat
infinity () = Succ () (infinity ())

repeat x :: x -> List x
repeat x = List x (repeat x)

wat :: rel x x -> ReflTrans rel x x
wat r = Trans r (iterate r)

So what’s my point? If you erase all of the types, then the code I have written for all three of these is identical modulo alpha renaming.

data Nat       data List      data ReflTrans
Zero Nil Refl
Succ v Nat Cons x List Trans r ReflTrans

Succ v x <> y = Succ v (x <> y)
Cons x xs <+> ys = Cons x (xs <+> ys)
Trans rwx xy >>> yz = Trans rwx (xy >>> yz)

And this begs the question: why should I write this code over and over, just to appease the type system? Is there a good way to unify these abstractions instead? How might we adjust Haskell’s type system to alleviate this redundancy?

Posted in Uncategorized | 4 Comments

Two implementations of Seers

Last time, we implemented a bowling game scorer by using a Tardis. If you aren’t yet familiar with the Tardis’s interface, then I recommend you check out the explanation on Hackage. (tl;dr it’s a State monad with get and put, except there are two streams of state, one forwards and one backwards, so there are four operations: getPast, getFuture, sendPast, and sendFuture.)

Today, we’ll take another large step in the esoteric drection, and implement a Seer by using a Tardis. Why, you ask? My response: why not? There may be some deep motivating reasons for you to study this, but I don’t pretend to know what those might be.

> {-# LANGUAGE MultiParamTypeClasses #-}
> {-# LANGUAGE FunctionalDependencies #-}
> {-# LANGUAGE FlexibleInstances #-}
> {-# LANGUAGE FlexibleContexts #-}
> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
> {-# LANGUAGE DoRec #-}
> {-# OPTIONS_GHC -Wall #-}
> import Control.Applicative (Applicative)
> import Control.Monad (liftM)
> import Control.Monad.Fix (MonadFix, mfix)
> import Control.Monad.Trans.Class (lift)
> import Control.Monad.Trans.Tardis
> import Control.Monad.Trans.Reader (ReaderT, ask, runReaderT)
> import Control.Monad.Trans.Writer (WriterT, tell, runWriterT)
> import Data.Monoid

What is a Seer?

A seer is someone that foretells the future.1 But how do seers know the future? Suppose you are writing a novel, and you want to devise a semi-believable “system” for how seers work. What would the rules be?

Well, rule number one for me is that in a legitimate system, all seers must agree about the future. If different seers predict different outcomes for the same future period, then there is reason to doubt such a system. I decided that in my seer system, all seers see “the whole universe”. All seers see the same thing, regardless of when or where in space and time they decide to “see” it.

Now, where does this information come from? Are there separate people that send information to these seers? My first idea was that the seer system could be a network of seers, and all information comes from within the network itself. All seers are therefore required to provide accurate information about their “present” in order to tap into the reservoir of mystical information about their past and future.

We therefore come to the main operation that I have devised for seers.

contact :: Monoid w => w -> Seer w

A seer provides their worldview in exchange for the grand worldview. The “whole” world should be of the form past <> present <> future, where present is whatever value is provided as the argument to contact.

Remember when I wondered about whether those that “see” the universe and those that “send” information about the universe might be different people? It turns out that we can easily write operations see and send in terms of contact. Or, alternatively, given see and send, we can easily write contact in terms of those.

> class (Monad m, Monoid w) => MonadSeer w m | m -> w where
>   see :: m w
>   send :: w -> m ()
>   contact :: w -> m w
>   
>   see = contact mempty
>   send w = contact w >> return ()
>   contact w = send w >> see

I’ve created a typeclass for the Seer interface, because we are going to implement a seer in two different ways.

Seer in terms of a Tardis

The Tardis allows us to both get and send messages to both the past and future. Given the timey-wimey nature of seers, a tardis seems like the perfect candidate for implementing them.

> newtype SeerT w m a = SeerT { unSeerT :: TardisT w w m a }
>                     deriving (Functor, Applicative, Monad, MonadFix)

A single contact consists of a seer getting in touch with both the past and the future. It seems only fair that this seer should share with the future his newfound knowledge of the past, and with the past his knowledge of the future. The past is inquiring the present about its (the past’s) future, which includes both the present and the future, or in other words present <> future. The future is inquiring the present about its (the future’s) past, which includes both the present and the past, or in other words, past <> present. The result of the contact is the whole universe, spanning all of time, in other words, past <> present <> future. In all cases, we want to make sure to keep things in “chronological” order.

Did you follow all of that? In short, information from the past should be sent forwards to the future, and information from the future should be sent backwards to the past. We can encode this flow of information easily using the Tardis operations:

> instance (Monoid w, MonadFix m) => MonadSeer w (SeerT w m) where
>   contact present = SeerT $ do
>     rec past <- getPast
>         sendPast (present <> future)
>         sendFuture (past <> present)
>         future <- getFuture
>     return (past <> present <> future)

Now, in order to “run” a seer operation, all we have to do is provide mempty at both ends of the time continuum, and run the tardis as usual.

> runSeerT :: (MonadFix m, Monoid w) => SeerT w m a -> m a
> runSeerT = flip evalTardisT (mempty, mempty) . unSeerT

Here is a dumb example demonstrating how it works.

> dumbExample :: MonadSeer [Int] m => m [Int]
> dumbExample = do
>   world1 <- see
>   send [world1 !! 2]
>   send [1]
>   world2 <- see
>   send [world2 !! 1]
>   world3 <- see
>   return world3
ghci> runSeerT dumbExample
  [1,1,1]

It is actually unnecessary to see more than once, since it is always the unchanging truth of past <> present <> future. The following is equivalent:

dumbExample = do
  world <- see
  send [world !! 2]
  send [1]
  send [world !! 1]
  return world

Seer in terms of a Reader/Writer

The astute observer should have noticed an odd similarity between see and ask, send and tell. They embody practically the same concept! The only nuance is that when you ask, what you will get is everything that you have tell’d, and everything you will tell. It turns out that this is quite easy to write in terms of the Reader and Writer monad transformers, which happen to be instances of MonadFix.

> newtype RWSeerT w m a = RWSeerT { unRWSeerT :: ReaderT w (WriterT w m) a }
>                       deriving (Functor, Applicative, Monad, MonadFix)

As I said before, see is simply ask, while send is simply tell. We merely lift and wrap the operations as necessary to keep the type system happy:

> instance (Monoid w, Monad m) => MonadSeer w (RWSeerT w m) where
>   see = RWSeerT ask
>   send w = RWSeerT (lift (tell w))

Now, to run a Seer built on top of a Reader/Writer pair, all we have to do is feed the results of the Writer straight back into the Reader. We accomplish this via mfix.

> runRWSeerT :: (Monoid w, MonadFix m) => RWSeerT w m a -> m a
> runRWSeerT (RWSeerT rwma) = liftM fst $
>   mfix (\ ~(_, w) -> runWriterT (runReaderT rwma w))

Here is a dumb example demonstrating that it works

ghci> runRWSeerT dumbExample
  [1,1,1]

So why use a Tardis?

For fun, obviously!

More seriously, notice that we can “run” SeerT differently, depending on whether we implemented it with Tardis or with Reader/Writer. With Tardis, we can supply “bookends”, the further past and the further future.

> runSeerTWith :: (MonadFix m, Monoid w) => w -> w -> SeerT w m a -> m a
> runSeerTWith past future = flip evalTardisT (future, past) . unSeerT

Exercise: Predict the output of runSeerTWith [10, 11, 12] [16, 17, 18] dumbExample.

Whereas with the reader/writer pair, we can fool the seers by giving them a false reality.

> runRWSeerTWith :: (Monoid w, Monad m) => w -> RWSeerT w m a -> m a
> runRWSeerTWith falseReality (RWSeerT rwma) = liftM fst $
>   runWriterT (runReaderT rwma falseReality)

Exercise: Predict the output of runRWSeerTWith [10, 11, 12] dumbExample.

What the ramifications of these are, I really don’t know. I just follow the types, lean on the laziness, and things just seem to work in Haskell, even mystical things like time travel and seers.

Download this code and play with it! Don’t forget to cabal install tardis first.

Posted in Uncategorized | 1 Comment

Bowling on a Tardis

> {-# LANGUAGE DoRec #-}
> import Control.Monad.Tardis

A few months ago, I released the tardis package. I promised a few blog posts about it, but put it off until now. If you haven’t heard of my "tardis" package yet, then you should probably take a look at the hackage documentation I’ve already written up for Control.Monad.Tardis.

Bowling

Let’s whip up a contrived example to which Tardis is applicable. Bowling scores is one such example, because the score you have on a given frame depends on both the past score as well as up to two future throws. Any time you need to know something from both the past and the future, Tardis might be able to help.

Let’s first define a data type that captures the essence of a bowling game. A game consists of 10 "frames". Although we model a single Frame as a data type, there are special rules that apply to the final frame, so we will model it separately as LFrame.

> data BowlingGame = BowlingGame
>   { frames :: [Frame]  -- should be 9, too tedious to type restrict
>   , lastFrame :: LFrame }
> 
> data Frame = Strike
>            | Spare { firstThrow :: Int }
>            | Frame { firstThrow, secondThrow :: Int }
> 
> data LFrame = LStrike { bonus1, bonus2 :: Int }
>             | LSpare { throw1, bonus1 :: Int }
>             | LFrame { throw1, throw2 :: Int }

For details on how bowling is scored, see Wikipedia > Bowling # Scoring.

Sample data

Here’s a few games’ worth of sample bowling data.

> --    X  9/ X  X  X   81  7/  X   X   XXX
> -- 0  20 40 70 98 117 126 146 176 206 236
> -- this guy is really good.
> sampleGame = BowlingGame
>   { frames =
>     [ Strike    , Spare 9
>     , Strike    , Strike
>     , Strike    , Frame 8 1
>     , Spare 7   , Strike
>     , Strike
>     ]
>   , lastFrame = LStrike 10 10
>   }
> 
> perfectGame = BowlingGame
>   { frames = replicate 9 Strike
>   , lastFrame = LStrike 10 10
>   }
> 
> worstGame = BowlingGame
>   { frames = replicate 9 (Frame 0 0)
>   , lastFrame = LFrame 0 0
>   }
> 
> main = mapM_ (print . toScores) [sampleGame, perfectGame, worstGame]

Using a Tardis

Well now we want to write the function toScores :: BowlingGame -> [Int]. We’ll do this by stepping through each Frame and creating the appropriate score. Whenever using a Tardis, I recommend you create separate newtypes for the backwards- and forwards-travelling state so you don’t get them mixed up.

> newtype PreviousScores = PreviousScores [Int]
> newtype NextThrows = NextThrows (Int, Int)

Here I’ve chosen the newtype PreviousScores for the forwards state, (because coming from the past to the present is moving "forwards" in time) and NextThrows as the backwards state (because coming from the future to the present is moving "backwards" in time).

> toScores :: BowlingGame -> [Int]
> toScores game = flip evalTardis initState $ go (frames game) where
>   go :: [Frame] -> Tardis NextThrows PreviousScores [Int]

First, we handle the case where we have another frame to process. We begin by assuming we have access to the next two throws (nextThrow1 and nextThrow2), as well as the previous score.

>   go (f : fs) = do
>     rec
>       let (score', throws') = case f of
>             Strike    -> (score + 10 + nextThrow1 + nextThrow2, (10, nextThrow1))
>             Spare n   -> (score + 10 + nextThrow1,              (n, 10 - n))
>             Frame n m -> (score + n + m,                        (n, m))

We need to determine the new state for each of the two streams of state. score' is determined by a combination of the previous score, the current frame, and future throws. This is the new score that we will send forwards in time. throws' is determined only by the current frame and future throws. This is the new "next two throws" that we will send backwards in time, which is why we put the current frame’s first throw as the earliest.

Now that we’ve got that figured out, we just use the tardis’s capabilities in order to retrieve and send information along its correct time stream. A good rule of thumb seems to be, if you want to get information from the past, then send the past some information first. Likewise, if you want info from the future, then send it some info first. However, I have no idea if this rule of thumb is necessary at all; the Tardis will sometimes Just Work even if you jumble it up a little.

>       sendPast $ NextThrows throws'
>       PreviousScores scores@(score : _) <- getPast
>       sendFuture $ PreviousScores (score' : scores)
>       NextThrows ~(nextThrow1, nextThrow2) <- getFuture

Great! Finally, we move on to the rest of the frames.

>     go fs

Once we run out of frames, we need to handle the last frame. There is no future to be concerned about, and we can just set up the values to be sent to the recent past via initState, so all we have to do is look at the past score, add the final frame’s score, and we’re done.

>   go [] = do
>     PreviousScores scores@(score : _) <- getPast
>     return $ (finalFrameScore + score) : scores

All that’s left is to figure out how to determine the final frame’s score, as well as the initial state. The former is easy, given the specifications of how to score a bowling game.

>   finalFrameScore = case lastFrame game of
>     LStrike b1 b2 -> 10 + b1 + b2
>     LSpare  t1 b1 -> 10 + b1
>     LFrame  t1 t2 -> t1 + t2

The "initial state" fed into a tardis is the farthest past for the forwards-travelling state, and the farthest future for the backwards-travelling state. The farthest past is a score of zero, while the farthest future is the final two throws of the game. Well, not quite. It’s the final two throws that come before the second-to-last frame. The last frame is guaranteed to consist of at least two throws. In the case of LStrike or LSpare, there are always three throws in the last frame, so the final throw is ignored. Remember, we’re sending the past its "closest" future two throws.

>   initState = (NextThrows $ case lastFrame game of
>     LStrike b1 b2 -> (10, b1)
>     LSpare t1 _b1 -> (t1, 10 - t1)
>     LFrame t1 t2  -> (t1, t2)
>     , PreviousScores [0])

And… that’s it! All we had to do was encode the rules of Bowling into a Tardis, and via some timey-wimey trickery, the Tardis assembles all of the information into a list of bowling scores, from the last frame to the first.

ghci> main
  [236,206,176,146,126,117,98,70,40,20,0]
  [300,270,240,210,180,150,120,90,60,30,0]
  [0,0,0,0,0,0,0,0,0,0,0]

Exercise: download this code, and remove the tilde (~) from line 133. What happens? Why?

Next time

Bowling was a rather simple example, to warm you up to the idea of what a Tardis is and what it can do. Next time, we’ll get even more timey-wimey by sketching out the concept of "seers" with nothing more than tardis primitives and a vague idea of some ground rules to rationally explain how you might describe a believable system of "seers" in a fictional setting.

Posted in Uncategorized | 1 Comment