2048 – Type Provider Edition

by Pezi 3. July 2014 11:36


I’m sure you would have all seen the highly addictive and annoying game 2048 by now (if not, follow the link and have a go now, don’t forget to come back here though! ).  Fellow F#er  @brandewinder wrote a bot that wins the game for you, subsequently turning it into an cool F# dojo.  It is London’s turn for this dojo next Thursday, so I figured before then I would have a go myself and do the obvious thing which is to turn it into a type provider :)

2048 TP Edition is available as part of my type provider abstraction the Interactive Provider.  You will want to set your tooltips to a fixed-width font for this to render for you properly. Here is a picture of it in action !


2048 Implementation

I will start by saying that I have not looked at any other implementations of either the game or any automated bots, so if this is terrible then please forgive me.  I had also not played the game at all until recently and as such the rules implemented here are from my brief analysis of playing it.  There might be some subtleties I have overlooked.

I first implemented this using arrays as it seemed like a natural fit for the 4 x 4 board, but although I got it to work, it was horrible and instead I replaced it with this much more functional version.

type data = Map<int * int, int> 
type direction = Up | Down | Left | Right

That covers the entire domain :)  Each location of the grid is stored in the map along with the value, if one exists. 

let shift (x,y) = function 
    | Up    -> (x,y-1) 
    | Down  -> (x,y+1) 
    | Left  -> (x-1,y) 
    | Right -> (x+1,y)

let moves = function 
    | Up -> 
        [for x in 0..3 do 
         for y in 0..3 do 
            yield x,y]        
    | Down -> 
        [for x in 0..3 do 
         for y in 3..-1..0 do 
            yield x,y] 
    | Left -> 
        [for y in 0..3 do 
         for x in 0..3 do 
            yield x,y]  
    | Right ->  
        [for y in 0..3 do 
         for x in 3..-1..0 do 
            yield x,y]

A couple of utility functions.  The first is pretty obvious, the second returns a list of tuples indicating the order that the cells should be processed.  The order is very important for a number of reasons as will become clear.

let rec move direction data (x,y) (px,py)  = 
    match x, y with 
    | -1, _ 
    | _, -1 
    | 4, _ 
    | _, 4 -> (px,py) 
    | x, y when Map.containsKey (x,y) data -> (px,py) 
    | _ -> move direction data (shift (x,y) direction) (x,y)

This function takes a location and attempts to move it in the specified direction until either it goes out of bounds, or it finds the location is already taken in the map. In either case, it returns the last good position that can be moved to.

let replace direction data inputs = 
    let move = move direction 
    ||> List.fold(fun m p -> 
        match move m (shift p direction) p with 
        | newpos when newpos = p -> m 
        | newpos -> let v = m.[p] in m |> Map.remove p |> Map.add newpos v)

let compress direction data = 
    |> moves 
    |> List.filter(fun k -> Map.containsKey k data) 
    |> replace direction data

These functions effectively “compress” the map in a specified direction.  What this means is that if we are going Up, it will start from the top row, and moving downwards it will move each cell up as far as it can go, resulting in a new compressed map.  You can think of this much like defragging memory, but with a direction bias.  It’s like applying gravity from different directions :)

let merge direction data =   
    let moves = direction |> moves |> Seq.pairwise |> Seq.toList    
    ||> List.fold( fun data ((x,y), (x',y')) -> 
            match Map.tryFind (x,y) data, Map.tryFind(x',y') data with 
            | Some first, Some second when first = second -> 
                |> Map.remove (x,y) 
                |> Map.remove (x',y') 
                |> Map.add (x,y) (first*2)                
            |_ -> data)

This one is a little more fun :)  The idea of the merge function is to, based on the direction, merge any pair cells that are touching and have the same value, replacing them with one cell (based on the “gravity” direction) that has double the value.  This code uses pairwise to serve up each pair of locations – the order that the cells are generated from the moves function is critical here

let step direction =  (compress direction) >> (merge direction) >> (compress direction)

Using function composition, I can now say that one step of the simulation consists of compressing the map in a certain direction, merging the resulting cells together where appropriate, and then compressing again to fill in any blanks that appeared from the merge step.  I think this is pretty awesome :)

Type Provider

As mentioned before, this uses my Interactive Provider so there is no gnarly provided types code.  Instead, I have a very simple state that gets passed back and forth

type ``2048State`` = 
    | NewGame 
    | GameOn of Map<int*int, int> 
    | GameOver of bool 
    interface IInteractiveState with 
        member x.DisplayOptions: (string * obj) list = 
            match x with 
            | NewGame  -> ["Begin Game", box ""] 
            | GameOn(data) -> ["# Show Grid", box "show";"Up", box "up";"Down", box "down";"Left", box "left";"Right", box "right";] 
            | GameOver(true) -> [] 
            | GameOver(false) -> [] 
        member x.DisplayText: string =  // omit drawing code for brevity 

Very simple .. at the start it shows “Begin Game” and from then on displays the directional choices as properties along with a “# Show Grid” property that shows  the current state of the grid.

type ``2048``() = 
    interface IInteractiveServer with 
        member x.NewState: IInteractiveState = NewGame :> IInteractiveState        
        member x.ProcessResponse(state: IInteractiveState, response: obj): IInteractiveState = 
            let (|Win|Lose|Continue|) (data:Map<int*int,int>) = 
                ((true,0),[for x in 0..3 do 
                           for y in 0..3 do 
                           yield x,y]) 
                ||> List.fold(fun (b,highest) k -> 
                    match Map.tryFind k data with 
                    | Some v -> if v > highest then (b,v) else (b,highest) 
                    | None -> (false,highest)) 
                |> function 
                    | (_, 2048) -> Win 
                    | (true, _) -> Lose 
                    | _ -> Continue data

            match (state:?>``2048State``), (response :?> String).ValueOption() with 
            | NewGame, _ -> 
                let x, y = rnd.Next(0,4), rnd.Next(0,4) 
                GameOn( Map.ofList[(x,y),2])                
            | GameOn(data), Some "show" -> GameOn(data) 
            | GameOn(data), dir -> 
                let dir = 
                    match dir with 
                    | Some "left" -> Left 
                    | Some "right" -> Right 
                    | Some "up" -> Up 
                    | Some "down" -> Down 
                    | _ -> failwith "" 
                match step dir data with             
                | Win -> GameOver true 
                | Lose -> GameOver false 
                | Continue data -> 
                    let rec aux () = 
                        let x, y = rnd.Next(0,4), rnd.Next(0,4) 
                        if Map.containsKey (x,y) data then aux() 
                        else x,y 
            | _, _ -> failwith "" 
            |> fun x -> x :> IInteractiveState

There is really not a lot to this.  The active pattern at the top cycles through all the possible grid states, collecting the highest cells and whether or not all the cells are populated. With this information it can return if the game has been won, lost, or should continue.

When the game is running, it simply looks at the direction that was selected, and pattern matches on the results of calling the composed step function using the active pattern above.  Assuming the game is still running, it finds a random location to put a new 2 in, and returns the new data map.



Now you can really spend time in Visual Studio playing games instead of working, because this is a lot more fun than minesweeper!  2048 Type Provider Edition for the win!


F# | type providers

CRUD Operations and Experimental ODBC support in the SQLProvider

by Pezi 18. May 2014 05:22

The SQL provider now supports basic transactional CRUD functionality and an ODBC provider. A new nuget package is up for you to grab here. As always, you can download and build from source here.

The nuget package is still pre-release. You can find it in Visual Studio by toggling the search filter to include pre-release packages. I'm sure Xamarin has a similar feature.  Once this work has been tested well enough,  I will likely upgrade the SQL Provider to a proper release.

Experimental ODBC Support

We now have support for general ODBC connectivity in the SQL provider.  This provides us with awesome power to connect to almost anything, including Excel spreadsheets.  However, because each driver can vary substantially, not all drivers may work, and others may have reduced functionality. ODBC is provided in the .NET core libraries, although you will of course need the appropriate ODBC driver installed on your machine for it to function.

ODBC has Where, Select and Join  support.  If  the source in question provides primary key information, you will also get Individuals. Although explicit joins are supported, foreign key constraint information and navigation are not yet available. The new CRUD operations are also supported, where appropriate.  We will see how this works from ODBC later in the post.

let excelCs = @"Driver={Microsoft Excel Driver (*.xls)};DriverId=790;Dbq=I:\test.xls;DefaultDir=I:\;" 
type xl = SqlDataProvider<excelCs, Common.DatabaseProviderTypes.ODBC>

You can use the new features with the following providers :

  • SQL Server
  • SQLite
  • PostgreSQL
  • MySQL
  • Oracle
  • ODBC (limited)

The following examples will use SQLite, but the mechanics are identical for all the providers.

CRUD Operations


The CRUD operations will only work for tables that have a well-defined, non composite primary key.  Identity keys are fully supported.

The data context is the core object that enables CRUD. It is important to understand that each data context you create from the type provider will track all entities that are modified from it.  In a sense, the data context “owns” all of the entities returned by queries or that you have created.  You can create more than one data context that have different connection strings at runtime.  You can pass a different connection string in the GetDataContext method.  This is an important concept as it allows you to connect to multiple instances of the same database, and even replicate data between them fairly easily.

type sql = SqlDataProvider< ConnectionString, Common.DatabaseProviderTypes.SQLITE, ResolutionPath > 
let ctx = sql.GetDataContext() 
let ctx2 = sql.GetDataContext("some other connection string")

whenever you select entire entities from a data context, be that by a query expression or an Individual, the data context involved will track the entity.  You can make changes to the fields by setting the relevant properties.  You do not need to do anything else, as the data context handles everything for you. 

let hardy = ctx.``[main].[Customers]``.Individuals.``As ContactName``.``AROUT, Thomas Hardy`` 
hardy.ContactName <- "Pezi the Pink Squirrel"


Note the call to SubmitUpdates() on the data context.  This will take all pending changes to all entities tracked by the data context, and execute them in a transaction.  An interesting property of the above code is that after Thomas Hardy has had his name changed, the first line will no longer compile! Go F#!

Similarly, you can delete an entity by calling the Delete() method on it.  This action will put the entity into a pending delete state.



After the deletion is committed, the data context will remove the primary key from the entity instance.

Creation is slightly different.  You will find various Create methods on the IQueryable Set types that represent the tables.  Up to 3 different overloads of this method will be available.  The first takes no parameters and will return a new entity which are you expected to populate with at least the required fields.  A second version will accept the required fields as parameters – this is only available if there are any columns marked as NOT NULL.  The final version will create an entity from a (string * obj) sequence – it is potentially unsafe but very handy for copying entities or creating them from some stream of data, if you know the attribute / column names are correct.

A note on primary keys – presently the SQL provider does not detect identity columns, although it does deal with them on the insert appropriately.  You will never see a primary key field as a parameter to the Create method.  If your primary key is an identity column, you can simply not include it.  Upon insert, the provider will automatically update the instance of the entity with the ID it has been assigned.  If on the other hand your key is not an identity column, you will be expected to assign it an appropriate value before attempting to submit the changes to the database.

// create an employee 
let pez = ctx.``[main].[Employees]``.Create("Pezi","Squirrel") 

printfn "Pezi's new employee id is %i" pez.EmployeeID

//update something 
pez.Address <- "the forest" 

// delete 

Now let’s see how we can effortlessly combine different SQLProviders together in order to perform "extract, transform, load" type processes.

type sql = SqlDataProvider<northwindCs, UseOptionTypes = true> 
type xl = SqlDataProvider<excelCs, Common.DatabaseProviderTypes.ODBC>

let northwind = sql.GetDataContext() 
let spreadsheet = xl.GetDataContext()
// load our tasty new employees from our lovely spreadsheet 
let newEmployees = 
    |> Seq.map(fun e -> 
        let emp = northwind.``[dbo].[Employees]``.Create() 
        emp.FirstName <- e.FirstName 
        emp.LastName <- e.LastName 
    |> Seq.toList

// save those puppies away 

In this sample we use the ODBC type provider to gain instant typed access to an Excel spreadsheet that contains some data about new employees.  the SQL Server type provider is also used to connect to a Northwind database instance.

We then very simply pull all the rows from the spreadsheet, map them to an Employee database record, and save them away.  It doesn’t get much easier than this!

Or does it?  Actually, in this case we know up front that the spreadsheet contains identical field names to that of the target database.  In this case we can use the overload of Create that accepts a sequence of data – this method is unsafe, but if you know that the names match up it means you don’t have to manually map any field names :)

let newEmployees = 
    |> Seq.map(fun e -> northwind.``[dbo].[Employees]``.Create(e.ColumnValues)) 
    |> Seq.toList

I think we can agree it really does not get much easier than that!  You can also use this technique to easily copy data between different data contexts, as long as you watch out for primary and foreign keys where applicable.

Data Binding

The SQLProvider, with a fair amount of trickery, supports two-way data binding over its entities.  This works together very well with the CRUD operations. 

open System.Windows.Forms 
open System.ComponentModel

let data = BindingList(Seq.toArray ctx.``[main].[Customers]``) 
let form = new Form(Text="Edit Customers") 
let dg = new DataGridView(Dock = DockStyle.Fill,DataSource=data) 
form.Controls.Add dg 


This is all the code you need to create a fully editable data grid.  A call to SubmitUpdates() afterwards will push all the changes to the database.

Other Bits

The data context now has a few new methods on it that you can use.

  1. ClearPendingChanges()  :  Ronseal.  Remove any tracked entities that have changed. Use this with caution, as subsequent changes to the entities will be tracked, but the previous changes will have been lost.
  2. GetPendingChanges() : This function will return a list of the entities the data context has tracked.  This is useful in a variety of situations, and it also means you do not have to bind to created or updated entities in order to not “lose” them in your program.
The SQL Provider does not currently have any support for transactionally creating heirarchies of data - that is, where you are able to create foreign-key related entities within the same transaction.  This feature may be added at a later date.
Shout outs to @simonhdickson for this work on the ODBC provider, and @colinbul for the Oracle CRUD implementation, thanks guys!
Now I have done this, I can finally get on with my really important type providers, such as the interactive provider of which I was stuck with my current extension to it as I had no way to create data in my sqlite database! :)