what is a functor

Quick intro to categories

Category theory is a topic from pure math but don’t fear – the basic stuff is not that hard to grasp.
And the domain (Types in programming languagues or Haskell in this case) should be well known to us
developers.

Basic definition

A category \(\mathcal{C}\) consists of two collections (or classes) of stuff: Objects \(Obj_{\mathcal{C}}\) and Arrows \(Hom_{\mathcal{C}}\).
For a first intuition it might be benefical to just think of objects as just mathematical sets
and arrows as just mathematical mappings (functions).

To make it a bit easier to read we will use upper-case letters like \(A\), \(B\) and \(C\) for objects and lower-case letters like \(f\), \(g\) and \(h\) for arrows.

You know it’s math so those classes will come with a few extra stuff and their elements have to fullfill some laws (I will stop to write the category in there for now – it’s always the same):

  • Every Arrow \(f\) is given a domain \(dom(f) \in Obj\) and codomain \(codom(f) \in Obj\) and we write a short-form of this as \(f: A \rightarrow B\) if \(f\)s domain is \(A\) and its codomain is \(B\). Often the collection of all arrows from domain \(A\) to codomain \(B\) is written as \(\mathcal{C}(A,B)\).
  • There is an operation \(\circ\) you we can use to compose two arrows: if we have \(f: A \rightarrow B\) and \(g: B \rightarrow C\) we get another arrow \(g \circ f: A \rightarrow C\).
  • There is a special arrow \(id_A: A \rightarrow A\) for each object \(A\). And yes – this will be just what you think it is.
  • Here are the laws: for all arrows you have \(f \circ (g \circ h) = (f \circ g) \circ h\) and \(f \circ id = id \circ f = f\) (and yeah you have to choose the right domains/codomains and even the \(id\) functions used there will be two different ones for this to work out – you can try this as an exercise or just read on and do it as an exercise in Haskell)

Chances are good, that this all looks very familiar to you. Indeed not only do arrows look like functions between set, the collection of all sets and the functions between them form a category \(\mathcal{Set}\).

Categories in Haskell

Now we want to transfer this into Haskell-World: We can get a category (usually called \(\mathcal{hask}\)), where the objects are the haskell-types (Int, [Char], Maybe Float, Int -> Int, whatever) and the arrows are just your usual haskell functions.

Easy isn’t it? It’s just new names for your stuff ;)

What is a functor

Now we climb the ebony-tower one more level: we look at the structure-preserving-maps between categories – and yes those we will call functors.

So what exactly does structure-preserving mean here?

Well for a functor \(\mathcal{F}\) between two categories \(\mathcal{C}\) and \(\mathcal{D}\) we need two mappings: one that maps objects in \(\mathcal{C}\) to objects in \(\mathcal{D}\) and one that will map their arrows so that domains, and codomains match.
We will be lazy here and just use the same symbol \(\mathcal{F}\) for both of them.
So we have $$\mathcal{F}: Obj_{\mathcal{C}} \rightarrow Obj_{\mathcal{D}}$$ and
$$\mathcal{F}: Hom_{\mathcal{C}} \rightarrow Hom_{\mathcal{D}}$$
Structur-preserving now just means that everything has to fit:

Imagine you have an arrow in \(\mathcal{C}\): \(f: A \rightarrow B\). For \(F(f)\) we demand that
$$
F(f): F(A) \rightarrow F(B)
$$
that is the functor maps the domain and codomain just right.

Of course the composition needs to be compatible as well – meaning
$$
\mathcal{F}(f \circ_{\mathcal{C}} g) = \mathcal{F}(f) \circ_{\mathcal{D}} \mathcal{F}(g)
$$
(Note that there are two different compositions involved here).

And what about Haskell?

Well in Haskell we cannot just use the same symbols for different stuff – and indeed this was something
I first struggled with a bit. So I hope to make this clear here.

We already saw that the objects are just types, and now we need something to map types to types.
Type-constructors with kind * -> * do just this.
That would include Maybe, [], … – and yes these are the things we call functors in Haskell.

Remember: there is a type-class called Functor in Haskell defined like this:

class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b

(There is another operator, defined with fmap in there that is not important for us here).

If you look carefully you see that fmap seems to be just what we need for our second mapping – the one that takes arrows to arrows (or types to types for us).

Maybe you did not see it till now – but we did not really change the categorie we are working in. Those
functors don’t change the category they go from \(\mathcal{hask}\) to \(\mathcal{hask}\) – in math these are called endo-functors.

What about the laws?

If you have a look at the documentationFunctors in Haskell should obey these laws:

fmap id  ==  id
fmap (f . g)  ==  fmap f . fmap g

Look closely – these are exactly the laws the categorial functors need to obay for \(\mathcal{hask}\).

Of course your usual instances of Functor all obey these laws – but they are not
checked by the compiler. So you have to be carefull when writing new functors.

What about other languagues

As you might know I work in .net/F#/C# in my day-job. It has no type-classes and so there nobody really
talks about functors there – but of course they are there.
F#s Option, most collection types with LINQ and so forth all have what you need for it.
Yes there is no common fmap but you have Option.map and List.map and of course LINQs .Select.
And the mapping between the types is just done through generics.

markdown plugins … oh my

I just saw that my old markdown-plugin (markdown on save) broke … sadly the new one that should be compatible with it (jetpack markdown) does not really care about my old posts and so you will see lot’s of issues.

Right now I don’t know how exactly I can get everything working with haskell-syntax highlighting again.

Any recommendations are appreciated :(

babysteps in using Persistent to interact with PostgreSQL

Introduction

as I mentioned I want to try some real-life Haskell and of course this means using some kind of database.
I looked around a bit and found the really great Persistent package from Micheal Snoyman.
Not only is this wonderfuly documented – no you get an yesod integration and a online-book(chapter) explaining it for free – thank you Micheal!

This post will only detail the setup and installation I had to do on top of my PostgresSQL installation and it’s more or less my notes I wrote along the way (I hope you enjoy this experiment).

So here we go – with opened SublimeText and console we start…

Set up the playground

  • made a directory and initialized a git repository in it git init
  • copied my generic haskell .gitignore into it
  • initialized cabal cabal init setting up the basic names and stuff
  • added persistent, persistent-sqlite and persistent-postgresql as dependencies
  • shamelessly copied the code from here into main.hs:

{-# LANGUAGE EmptyDataDecls    #-}
{-# LANGUAGE FlexibleContexts  #-}
{-# LANGUAGE GADTs             #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE QuasiQuotes       #-}
{-# LANGUAGE TemplateHaskell   #-}
{-# LANGUAGE TypeFamilies      #-}
import           Control.Monad.IO.Class  (liftIO)
import           Database.Persist
import           Database.Persist.Sqlite
import           Database.Persist.TH</p>

<p>share [mkPersist sqlSettings, mkMigrate &quot;migrateAll&quot;] [persistLowerCase|
Person
    name String
    age Int Maybe
    deriving Show
BlogPost
    title String
    authorId PersonId
    deriving Show
|]</p>

<p>main :: IO ()
main = runSqlite &quot;:memory:&quot; $ do
    runMigration migrateAll</p>

<pre><code>johnId &amp;lt;- insert $ Person &amp;quot;John Doe&amp;quot; $ Just 35
janeId &amp;lt;- insert $ Person &amp;quot;Jane Doe&amp;quot; Nothing

insert $ BlogPost &amp;quot;My fr1st p0st&amp;quot; johnId
insert $ BlogPost &amp;quot;One more for good measure&amp;quot; johnId

oneJohnPost &amp;lt;- selectList [BlogPostAuthorId ==. johnId] [LimitTo 1]
liftIO $ print (oneJohnPost :: [Entity BlogPost])

john &amp;lt;- get johnId
liftIO $ print (john :: Maybe Person)

delete janeId
deleteWhere [BlogPostAuthorId ==. johnId]
</code></pre>

<p>

  • obviously wanting a sandbox: cabal sandbox init
  • get the stuff from the net and write this here in the meantime ;) cabal install --dependencies-only

the usual cabal oddysee starts.. (but do not fear – Penelope does not have to wait long)

So this was the first thing that failed – persistent-sqlite went like a charm but persistent-postgresql had a issue.

Ok – comment out the postgres part for now – the code does not need it.

But as cabal build showed I had a missing module Database.Persist.TH – and as I could not find the right package at once, let’s comment it out for now.

Yeah that got me another missing module Control.Monad.IO.Class – but this time ghc (and me) knows where to find it: transformers – so in it.

Now I get some more information – as you could guess the .TH stands for TemplateHaskell and sure enough ghc complains about things like share and mkPersist.

And sure enough there is a persistent-template package with those functions and the missing module – so another cabal install later, we finally have a compiling program.

Yes there are a few warnings (unused constructors and so forth) but let’s forget about this right now.

let’s run

a cabal run yields

Migrating: CREATE TABLE "person"("id" INTEGER PRIMARY KEY,"name" VARCHAR NOT NULL,"age" INTEGER NULL)
Migrating: CREATE TABLE "blog_post"("id" INTEGER PRIMARY KEY,"title" VARCHAR NOT NULL,"author_id" INTEGER NOT NULL REFERENCES "person")
[Entity {entityKey = Key {unKey = PersistInt64 1}, entityVal = BlogPost {blogPostTitle = "My fr1st p0st", blogPostAuthorId = Key {unKey = PersistInt64 1}}}]
Just (Person {personName = "John Doe", personAge = Just 35})

Which looks like just what the copied code should do … great!

back to postgres

But of course I want to run this in my local postgresql db – so there’s still one thing left before I could call it a day – so remove let’s get it back in there.

Retrying the install I saw this nice little helper-message:

setup: The program pg_config is required but it could not be found.

And indeed – I did not have this on my system – running openSUSE it’s no big deal to find out where the bugger lives: cnf pg_config – voila postgresql92-devel so give it to me sudo zypper install postgresql92-devel (note: of course you might have to do some sudo apt-get or something similar if you are on a debian based system – but I’m sure you get it – if you are on windows … well let’s say I keep this task for another day and propably ms-sql or mysql instead of postgres).

After this little intermezzo persistent-postgresql builds/installs and we can look at how to use it with our “copy&paste” example.

Turns out that this too is already mentioned in the book chapter I linked earlier – right at the bottom of the doc.
The changes are very slight:

  • import Database.Persist.Postgresql instead of .Sqlite
  • get a connection string for the database:
        connStr = "host=localhost dbname=test user=??? password=**** port=5432"
        

<

p>(fill in whatever you need – obviously you should use a known user/password).

  • run withPostgresqlPool with runSqlPersistMPool instead of just runSqlite like this:

main = withPostgresqlPool connStr 10 $ pool -> do 
    flip runSqlPersistMPool pool $ do

The rest may stay untouched.

And YEAH – cabal run yields

Migrating: CREATe TABLE "person"("id" SERIAL PRIMARY KEY UNIQUE,"name" VARCHAR NOT NULL,"age" INT8 NULL)
HINWEIS:  CREATE TABLE erstellt implizit eine Sequenz »person_id_seq« für die »serial«-Spalte »person.id«
HINWEIS:  CREATE TABLE / PRIMARY KEY erstellt implizit einen Index »person_pkey« für Tabelle »person«
Migrating: CREATe TABLE "blog_post"("id" SERIAL PRIMARY KEY UNIQUE,"title" VARCHAR NOT NULL,"author_id" INT8 NOT NULL)
HINWEIS:  CREATE TABLE erstellt implizit eine Sequenz »blog_post_id_seq« für die »serial«-Spalte »blog_post.id«
HINWEIS:  CREATE TABLE / PRIMARY KEY erstellt implizit einen Index »blog_post_pkey« für Tabelle »blog_post«
Migrating: ALTER TABLE "blog_post" ADD CONSTRAINT "blog_post_author_id_fkey" FOREIGN KEY("author_id") REFERENCES "person"("id")
[Entity {entityKey = Key {unKey = PersistInt64 1}, entityVal = BlogPost {blogPostTitle = "My fr1st p0st", blogPostAuthorId = Key {unKey = PersistInt64 1}}}]
Just (Person {personName = "John Doe", personAge = Just 35})

Checking my test database with pgAdminIII I see that indeed I now have a person and a blog_post table with the right columns set up. The first having an “John Deo” entry and the second beeing empty.

Rerunning again adds another “John Doe” with id “3″ as it should.
As a last test I removed the “delete” so I can check for a blog post … and yes I now have yet another “John 5″ who has 2 posts … so yes it’s working as it should.

This should wrap up the first tests – rather painless which is great!

Installing PostgreSQL on openSUSE

Introduction

I want to try some real life style CRUD applications with Haskell and co.
To do this I wanted to install PostgreSQL as I heard lot’s of good stuff about it.

Disclaimer

I am in no way an expert or even competent with PostgreSQL but this got me a working instance together with an UI tool to administrate it.

Packages to install

I installed the followig packages following this and some other tutorials on the net:

  • postgresql-init
  • libpq5
  • postgres92
  • libqt4-sql-postgresql
  • postgresl92-server
  • postgresql
  • postgresql-server
  • libwx-gtk2u_stc-2_8-0-wxcontainer
  • libwx-gtk2u_xrc-2_8-0-wxcontainer
  • pgadmin3
  • pgadmin3-lang
  • libreoffice-base-drivers-postgresql

Obviously some of those got auto-selected (using YAST) and I added pgadmin3 and the plugin for libre-office as I saw it in the repose ;)

Post-Install (setting up the user, password, authentication method and data-path)

Following the short guide I

  • created a data-directory mkdir /usr/local/pgsql/data
  • made (already configured user) postgres the owner of this chown postgres /usr/local/pgsql/data
  • switched to this user su - postgres
  • initialised the database initdb -D /usr/local/pgsql/data
  • started postgres using this folder postgres -D /usr/local/pgsql/data
  • created a test database createdb test

(do not forget using godmode for this before you go – su)

Next I had to change the default password (again as su) – following the steps here:

  • start postgres (if not already) rcpostgresql start
  • switch to the user postgres and open the master-db: su postgres -c psql postgres
  • in the sql-command alter the defaultusers password: ALTER USER postgres WITH PASSWORD '****' (of course using you password instead of the stars)

Next on the checklist is changing the authentication mode (I guess this is only a good idea for your local test-instance – but this way it’s much easier to get everything going – indeed pgAdminIII will propose the same if it has problems connecting).
So open the file /var/lib/pgsql/data/pg_hba.conf (you will need administrative rights to access it) and change the uncommented occurrences of ident to md5.
Save the file and restart the database with rcpostgresql restart

Now everything should be fine to use pgAdminIII.

Setting up pgAdmin III

Start pgAdminIII and add a new server using

  • Host = localhost
  • Port = 5432 (this is configured in /var/lib/pgsql/data/postgres.conf),
  • User = postgres (of course you can create another user with createuser -D -p <username> – without -p if you do not need a password)
  • Passwort = whatever you choose in the last step

That’s it – now you should be able to access everything using this tool or the sql-command (pgsql)

Useful Links

As always: have fun :D

fold and accumulate

(You can also look at this post using the great my FPComplete tutorial for this)

what is this about?

Recently I played a bit with threepenny-gui and soon ran into the situation where I wanted to update a behavior (my state) using the old state and certain events.
Not having to much real functional approach to reactive programming my mind at once cried “give me some fold man” … but alas: there is nothing that has a close shape to a fold in this library.

So I skimmed through the libraray and could really not get how I could ever get to use “old-state” together with an event …

After a while I finally saw some “accumulate” functions in there, and as I knew their close relationship with folds (for example in .net/linq fold is named Accumulate) I knew I might have found a way out … but wait this is the type-signature of the one I finally used:

accumB :: MonadIO m => a -> Event (a -> a) -> m (Behavior a)

let’s rephrase that a bit and you get basically

accum :: acc -> [acc -> acc] -> acc

It’s quite a bit away from

foldl :: (acc -> b -> acc) -> acc -> [b] -> acc

And I really struggled to finally see how you could use accum to get foldl.

If you like me don’t see how you could possible to this read on – if you find this trivial better close the site now.

the idea

After 20 minutes or so (searching around for other stuff, coming back, scratching my head, …) I finally saw how to do it:

Just map the bs into functions acc -> acc and vóila: done.

let’s implement this

So let’s try – here is functional version of the basic accum function:

accum :: acc -> [acc -> acc] -> acc
accum acc []     = acc
accum acc (f:fs) = accum (f acc) fs

main = do
    putStrLn $ show . accum 0 $ [(+1), (+2), (+3), (+4)]

And of course, using f :: acc -> b -> acc and given a b we map this into \acc -> f acc b or flip f b:

fold :: (acc -> b -> acc) -> acc -> [b] -> acc
fold f acc = accum acc . map (flip f)

Seems to be correct (at least the compiler is happy and the results math).

a bit eq. reasoning

So let’s get a bit further by actually showing that this is correct. Using the definition of accum we see that (abusing the syntax highlighter and eq. reasoning here – so == is meta-equals instead of a lang. construct):

fold f acc [] == accum acc . map (flip f) $ []
              == accum acc []
              == acc

So the base-case is the same as foldl – check.

The non-empty list case is not much more:

fold f acc (b:bs) == accum acc . map (flip f) $ (b:bs)
                  == accum acc $ ((\a -> f a b) : map (flip f) bs)
                  == accum ((\a -> f a b) acc) $ map (flip f) bs
                  == accum (f acc b) $ map (flip f) bs
                  == fold f (f acc b) bs

That’s it – qed ;)

and vice versa?

Well this is just as simple: having a fold like above you can define a accum by:

accum :: acc -> [acc -> acc] -> acc
accum = fold (flip ($))

coin-change kata

the task

given a list of coins \([c_1,..,c_n]\) and a amount of money \(A\) we shall find a list \([a_1,..,a_n]\) of integers such that \(\sum_i a_i c_i = A\) – but not just any: We want to minimize the number of coins given: \( minimize \sum_i a_i\)

See here for more on this problem.

I stumpled on this reading twitter, where Mike Bild solved this using various LINQ-like expressions (well the first version of what I give you here) … as I could not stand the not-optimal solution I had to brute-force a better solution (… and maybe I come back and try to improve on that some time)

remark (shameless plug)

You can find the same article on school of haskell – where you can even play with it.
But make sure to give me some nice comments here :D

a trivial algorithm (that does give you correct change but not with fewest coins)

First define the coins used (as a Integer-list):

coins :: [Integer]
coins = [100, 25, 10, 5, 1]

Then the idea is to fold over the coins using the remaining amount we have to change and the count of used coins so far (so a 3 at position 2 will mean 2 – 25ct coins used)

change :: Integer -> [Integer]
change n = reverse . snd $ foldl next (n, []) coins
    where next (remaining, cs) coin
            | coin <= remaining = (r', cnt:cs)
            | otherwise         = (remaining, 0:cs)
            where r' = remaining `mod` coin
                  cnt = remaining `div` coin

Why this might fail in the general case

Well sometimes … let’s change the coins and look for 30cts …

change :: Integer -> [Integer]
change n = reverse . snd $ foldl next (n, []) coins
    where next (remaining, cs) coin
            | coin <= remaining = (r', cnt:cs)
            | otherwise         = (remaining, 0:cs)
            where r' = remaining `mod` coin
                  cnt = remaining `div` coin

so 6 coins (1x25ct and 5*1ct) – WTF … well the algorithm is too stupid in this case (the answer is of course 2x15ct) … stay tuned – I gonna fix it … soon

brute-forcing our way

An easy way to fix this is to try every possible combination for small cases like the samples it’s still ok

import Data.List(minimumBy)
import Data.Maybe(mapMaybe)
import Control.Applicative ( (<$>) )

findChange :: [Coin] -> Cents -> Maybe [Integer]
findChange coins amount = snd <$> calc amount coins
    where calc r []
            | r == 0    = Just (0, [])
            | otherwise = Nothing
          calc r (c:cs)
            | r < 0     = Nothing
            | otherwise = findMinimum . mapMaybe try $ [0 .. r `div` c]
                where try n = do
                        (n', ns) <- calc (r-n*c) cs
                        return (n + n', n:ns)
                      findMinimum [] = Nothing
                      findMinimum vs = Just . minimumBy (\ (a,_) (b, _) -> compare a b) $ vs

As you can see, the code has changed a bit – but produces the right answer (2x15ct)!

Instead of trying to find the right fold-function I went for manual recursion for now:
You will find the algorithm inside of calc. The first few guards handle the edge-cases (nothing more to change, no-coins left to try, to much change given).
But in the case that there is still something to give-back and where there are coins left to change with the algorithm tries every combination and finaly turns back the one with fewest coins given recursivley.

brute-force brakes down

Remember: I told you “it’s still ok”?
Well I lied – try the brute-force algorithm for your normal coins [100, 50, 25, 10, 5, 2, 1] and (say) 2$34ct … this will take the algorithm on my machine almost 10seconds!
Try the same for 100$ and get yourself some coffee…

What can we do…

If you look carefully you’ll see that we do the recursive-call not one time but two times – and just as with fibonacci numbers we will sureley hit the same spot more than once – but every time we calculate the thing again.
Just write the algorithm down as a tree and you will see that we recalculate the same branches time-and-time again…

So how can we change this?

We have to memoize the caluclated values! This is more or less the basic idea in dynamic programming (DP) – and while I will not give a complete introduction here I will try to show how you can change the algorithm to use this.

First step towards DP

The first thing we are going to do is modify the algorithm a bit so that we can see better where the recursion is (the case expression below):

-- | tries change (using coins form the first parameter) to the amount of money in the second parameter with the fewest number of pieces in the change
-- | the first parameter should be a decreasing list of distinct values
takeCoin :: [Coin] -> Cents -> Maybe (Integer, [Coin])
takeCoin [] cents
    | cents == 0   = Just (0, [])
    | otherwise    = Nothing
takeCoin coins@(coin:coins') cents
    | cents < 0    = Nothing
    | coin > cents = takeCoin coins' cents
    | otherwise    = case (takeCoin coins (cents-coin), takeCoin coins' cents) of
                        (Just (n, t), Just (n',t')) -> Just $ if n+1 <= n' then (n+1, coin:t) else (n', t')
                        (Nothing,     Just (n',t')) -> Just (n', t')
                        (Just (n,t),  Nothing)      -> Just (n+1, coin:t)

This will still take long (indeed it will do slightly worse) but you can see better where the magic (aka recursion) is and where the edge-cases gets handled.

enter lazy-arrays

Now how to memoize … well the easiest thing I can think of (and indeed almost the same as with real DP) is to use an array.
Well now you cannot mutate arrays in Haskell but as Haskell is lazy this will be no problem!
How so? Well we just put lots of chunks into the array and let the algorithm lazily evalute those at needed.
BTW: this is the point where this algorithm can break down: the chunks need quite some memory and if your DP-table is large this will exhaust your memory (look for the knapsackproblem with large data-sets …) but again (this time for sure): for this it will be sufficient (for me)!

So here it is – the final (quite quick) DP-solution to the problem

import Data.Array
takeCoinDP :: [Coin] -> Cents -> Maybe (Integer, [Coin])
takeCoinDP coins cents = get ltCoin cents
    where arr = array ((0,0), (ltCoin, cents)) [((i,c), takeC i c) | i <- [0..ltCoin], c <- [0..cents]]
          get i c
            | i < 0 && c == 0 = Just (0, [])
            | i < 0 || c < 0  = Nothing
            | otherwise      = arr!(i,c)
          ltCoin = length coins - 1
          takeC cNr cts
            | coin > cts          = get (cNr-1) cts
            | otherwise           = case (get cNr (cts-coin), get (cNr-1) cts) of
                                       (Just (n, t), Just (n',t')) -> Just $ if n+1 <= n' then (n+1, coin:t) else (n', t')
                                       (Nothing,     Just (n',t')) -> Just (n', t')
                                       (Just (n,t),  Nothing)      -> Just (n+1, coin:t)
                                       (Nothing,     Nothing)      -> Nothing
            where coin = coins !! cNr

main :: IO ()
main = do
    putStrLn "let's change 2$34ct"
    let coins = defaultCoins
    let amount = 234

    putStrLn "here we go ... this should be alot quicker..."
    let res = takeCoinDP coins amount
    print res

I hope you see the similarity to the version above.
The only trick here is to move the edge cases to the selection from the array (to avoid index-out-of-range exceptions and stuff).

Enjoy!

Installing GLPK and GLPK-hs on Windows

As I want to try some LP (looking into a coursera-course) I tried to setup GLPK on Windows. (BTW: doing this in Linux is trivial: apt-get or you friendly packet-manager).

The goal was to get this simple skript:

import Control.Monad.LPMonad
import Data.LinearProgram
import Data.LinearProgram.GLPK

objFun :: LinFunc String Int
objFun = linCombination [(10, "x1"), (6, "x2"), (4, "x3")]

lp :: LP String Int
lp = execLPM $ do   
    setDirection Max
    setObjective objFun
    leqTo (varSum ["x1", "x2", "x3"]) 100
    leqTo (linCombination [(10, "x1"), (4, "x2"), (5, "x3")]) 600
    leqTo (linCombination [(2, "x1"), (2, "x2"), (6, "x3")]) 300
    varGeq "x1" 0
    varBds "x2" 0 50
    varGeq "x3" 0
    setVarKind "x1" IntVar
    setVarKind "x2" ContVar

main = print =<< glpSolveVars mipDefaults lp

running.

Well here are the steps that got me going:

  • Download and extract the executables
  • in the /w32 folder edit the Build_GLPK_with_VC10.bat file to update your installation folder for VS2010 (mine was under Programm files (x86))
  • run the batch-file and make sure you are in the right environment (I put it into programm files so I had to run the developers console from VS2010 tools as administrator!)
  • copy the build version of glpk dll and lib without it’s version (for example copy glpk_4_52.dll glpk.dll)
  • use cabal install with extra-libs and extra-sources like this:
cabal install glpk-hs --extra-lib-dirs="c:\Program Files (x86)\GNU\glpk\w32" --extra-include-dirs="c:\Program Files (x86)\GNU\glpk\src" 
  • now runhaskell example.hs should run and result in \( x_1 = 40 \), \( x_2 = 50 \) and \( x_3 = 0 \).

BangPatterns in Haskell

I’ve seen syntax like:

let !s = f x

from time to time (for example in Marlows Book) but I never reall knew what this really is, nor where I should look for it.

Today I stumpled upon the Bang patterns extension to GHC – and voila – here we go.

So what is it?

If we add the extension we can force evalutation wo WHNF (weak head normal form – more or less evaluated “one step”) by just adding a !(Bang) in front of an identifier – and this extents to pattern-matching as well (this and the fact that is’s shorter to write and better to read makes it so much better then seq).

Here are a few examples showing a bit of it’s power/capabilities:

let makeTuple() = (1+1, 2+2)
let f = makeTuple()
:sprint f
>> f = _

let !f = makeTuple()
:sprint f
>>f = (_,_)