Browse Author

Mansour

Obligatory Monad Post

I’m taking a break from blogging for a while, but before I go, here’s a (now cliché) blog post on monads.

There are far more precise, formal descriptions out there; however, I’ll give a practical, if imprecise, description of monads that I believe (!) makes them easier to think about:

A monad is a datatype1 that allows us to: represent computations2 that have some structured3 result, and chain such computations together4

  1. The datatype defines two operations, which (in Haskell parlance) are called bind (>>=) and return. return places a value in the monad, and bind is used to pass this monadic value to another function. Implementations of these operations must satisfy certain laws.
  2. Some expression to be evaluated.
  3. The result has some additional context. For example, that context could be that the computation may fail (Haskell’s Maybe monad), or that it is non-deterministic (List), or that some interaction with the outside-world occurs (IO).
  4. We can combine monadic values by passing them between functions that operate on them (using the bind operator)

Here’s an example in Haskell:

Keep Reading

2016 Retrospective Reading List

As the year draws to end, I’ve been reflecting on the all the new things I’ve learnt. Below is a list of some of the good books I’ve read over the last year (a mix of old and new), that I would recommend. I’ve been making full use of my Safari Books subscription, but I’m attaching Amazon links here for simplicity.

Improving Listify

Listify’s latency, while tolerable, could do with some improvement (performance was a secondary concern while building it; I felt that the application functionality was far more interesting).  So I’ve decided to address this issue and blog about it as I go along. 

Quick recap: Listify retrieves BBC radio schedule information in order to create Spotify playlists (aside: unfortunately the BBC don’t provide a clean API to retrieve this information, so there’s a fair bit of scraping going on). In order to retrieve that information, the application needs to send requests to the BBC Radio web site.improving-listify-i1

So, for instance, to create a Spotify playlist, the application must retrieve the radio tracklist for that particular episode of that particular show. This involves making a relatively-expensive external network request to grab that information. Another similar request is then made to create the Spotify playlist. Fortunately the retrieved information is cached in Listify’s local database, so that if the playlist for this episode is requested again, the information is instead retrieved more quickly from the database. But of course, the first user after that playlist still has to take that initial latency hit! Let’s fix this….

Keep Reading

HaskellX Conference & Hackathon

I just spent four days hanging with the (very international) Haskell community in London.

First I attended the two-day Haskell eXchange conference. This was in fact my very first conference! I watched talks on a range of topics, ranging from notation for category theory to the use of Haskell for games and web development, and even got hands-on in a workshop. Good fun! The highlights were of course the keynotes (I was left mind-blown by this one). All the videos are now available online.

After that, there was HaskellXHack, a two-day hackathon focused on improving the Haskell infrastructure (Hackage, Cabal, etc.). I paired up with another developer to contribute to Hackage; we looked at a couple issues around rendering webpage content and raised pull requests to fix them.

Keep Reading

MuniHac Hackathon

I’ve just got back from MuniHac, a three-day Haskell hackathon in Munich, Germany. It was hosted by the good people at TNG and Well-Typed.

There were lots of different projects going on. I contributed to Leksah, an open-source Haskell IDE written in Haskell; specifically by adding functionality to select snippets of code and upload to LPaste (a Pastebin-like service designed with Haskell in mind), returning the URL to the user to share.

The coding was punctuated with talks by guest speakers from the Haskell community, as well as social activities. Plus it was great to catch up with some old friends from Utrecht. I had a blast!

CrgpWNOWEAABJmq
Image by @MuniHac

Higher-rank Polymorphism

On the functional programming course I attended, I learnt about some interesting parts of Haskell’s type system. I figured I’d write a blog post*.

(Standard) Haskell has what’s called let-bound polymorphism. This means that identifiers bound in let’s, where‘s or top-level definitions can be polymorphic, whereas lambda-bound identifiers (function arguments) cannot. Here are some examples, using the (polymorphic) id function:

-- Let (OK)
polymorphicLet :: (Integer, Char)
polymorphicLet = let f = id in (f 3, f 'a')
-- Where (OK)
polymorphicWhere :: (Integer, Char) 
polymorphicWhere = (f 3, f 'a') where f = id
-- Top-level (OK)
f :: a -> a 
f = id
 
polymorphicTopLevel :: (Integer, Char) 
polymorphicTopLevel = (f 3, f 'a')
-- Lambda-bound (not OK)
polymorphicInlineLambda :: (Integer, Char) 
polymorphicInlineLambda = (\f -> (f 3, f 'a')) id

Keep Reading

Applied Functional Programming @ Utrecht

For two weeks in July, I attended the Utrecht Summer School in Applied Functional Programming at Utrecht University in the Netherlands. It was taught by some of the leading academics in the field of functional programming, and combined a good mix of theory and practice. Overall, a very informative and enjoyable experience!

I worked on several theoretical exercises and mini-projects, all implemented in Haskell, and you can find the source code here! I’ve hooked the Github repo up with Travis CI to build the code and run the tests (compilation is a big deal in Haskell). Note: if you setup a Haskell project on Travis, be sure to read this to avoid any GHC version trouble!

Aside: among the code, there is an implementation of the board game Mastermind (with tests written in HUnit and QuickCheck). Amusingly, there is an MTV reality show loosely based on this game!

20160703_165912

Radio => Spotify Playlists

Listify is a Web app that combines information from the BBC radio schedule with the Spotify API, to automate the creation of Spotify playlists from radio shows.

I was motivated to build it because I realised that what I love about the radio shows that I listen to is the music, and not the filler content in between (talk, ad breaks, etc.), and so by using Listify, I could distil those shows and extract that desired essence.

This project was a great way to learn a bunch of technologies from the world of isomorphic Javascript: Node.js, Express.js, React,  moment.js, cheerio and MongoDB (thank goodness for async/await). I also dived into DevOps by using Docker and Ansible.

To use Listify, just login with your Spotify account and get going! Check it out in action here, and find the source code here!

Bloom filter

A cool data structure that I’ve come across in the past, but have not yet had a chance to use directly is a Bloom filter. It’s a probabilistic data structure that can act as a set, and is both space and time efficient (constant!). Bloom filters have found many useful applications, typically in preventing the occurrence of some more expensive lookup or access.

Naturally, I’ve had a go at implementing it myself. You can find the source code here (Python).

The general idea: to insert an element, run it through a number of hash functions, each generating an index into a bit array, and set the bits at those positions in the array. Then, to query for an element (i.e. is a given element a member of this set?), run it through those same hash functions and check whether all the bits at those positions in the array are set. Note: Bloom filters come with two key caveats: (i) when querying, you may get false positives, and (ii) items cannot be removed (which would introduce false negatives).

A wonderful explanation of Bloom Filters can be found here and a neat trick to generate several hash functions can be found here.

 

Eight Queens Puzzle

After reading this inspiring blog by Haseeb Q, I decided to have a go at coding some solutions to the eight queens puzzle. You can find my source code here (alas, no pretty GUI)

I think its really a interesting problem because there are a number of different approaches to solving it; e.g. an exhaustive approach like depth-first backtracking, or an iterative improvement approach such as hill-climbing with the min-conflicts heuristic (which is faster but risks hitting a local optimum).

  • 1
  • 2