Functional Programming 101 - With Haskell

In this blog post, I'll attempt to explain some basic concepts of Functional Programming, using Haskell. This blog post isn't about Haskell per-se, but about one way of approaching this problem, which demonstrates the benefits of functional programming.

You can run most of these examples in ghci, by saving the contents of the example into a .hs file, loading up ghci and running :load file.hs.

Many thanks to Mattox Beckman for coming up with the programming exercise, and Junjie Ying for coming finding a better data structure for this explanation than I came up with.

The Problem

You are Hercules, about to fight the dreaded Hydra. The Hydra has 9 heads. When a head is chopped off, it spawns 8 more heads. When one of these 8 heads is cut off, each one spawns out 7 more heads. Chopping one of these spawns 6 more heads, and so on until the weakest head of the hydra will not spawn out any more heads.

Our job is to figure out how many chops Hercules needs to make in order to kill all heads of the Hydra. And no, it's not n!.

Prelude: Simple Overview Of Haskell Syntax

Before we dive into code, i'll explain a few constructs which are unique to Haskell, so it's easy for non Haskellers.

  • List Creation: You can create a list / array using the : operator. This can even be done lazily to get an infinite list.
  • Defining Function: Looks just like defining a variable, but it takes parameters. One way they are different from other languages is the ability to do pattern matching to simplify your code. Here, I define a method that sums all the elements of a list.
  • More List Foo: Adding lists can be done with ++. Checking if a list is empty can be done with null. You can use replicate to create a list with the same elements over and over.

Choosing a data structure

Let's choose a simple data structure to represent the hydra. We'll pick an array to represent the heads of the Hydra, using the level of each head as the value. The initial state of the Hydra (with 9 level 9 heads) can be represented as follows: [9, 9, 9, 9, 9, 9, 9, 9, 9].

Chopping off a head

The whole point of functional programming is to build small functions and compose them later. We'll build a few functions, specific to our domain, and a few more general ones to orchestrate.

Let's first build a specific function to chop off the Hydra's head. We know that chopping off one level 9 head should result in 8 level 8 heads (and 8 of the original level 9 heads). This is represented as [8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9]

Let's build the chop function. It takes a single argument, and the current levels of the all live heads. It will return the state of the heads after chopping the first one.

The three lines of code below map to these rules:

  • If there are no heads left, just return []
  • If we find that there is a level 1 head at the start of our list, just chop it off and return the rest of the array
  • If we find that there is a higher level head at the start of our list, spawn n – 1 heads in it's place

chop []       = []
chop (1:xs) = xs
chop (n:xs) = (replicate (n – 1) (n – 1)) ++ xs
——————————————————————————
chop [1]
— []
chop [4]
— [3, 3, 3]
chop [3, 3, 3]
— [2, 2, 3, 3]
chop [9,9,9,9,9,9,9,9,9]
— [8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9]

Repeatedly chopping heads

Our function chop is a pure function as, given some input, it always returns the same output, without any sort of side effects. Side effects is a general term for modifying inputs / IO Operations / DB Calls, and so on.

Since chop is pure function, we can safely call it over and over. Let's build a list where each element is the result of chopping the previous element.

repeatedlyChop heads = heads:repeatedlyChop (chop heads)
—————————————————————————————
repeatedlyChop [3]
— [[3],[2,2],[1,2],[2],[1], [], [], [] …]
— this is an infinite list

This paradigm is so common, that we have a functional construct that does this: iterate. We can replace the above code with the following:

repeatedlyChop heads = iterate chop heads

Truncate that infinite list

Great, we now have built a list of all the states the Hydra is in while Hercules is busy chopping away at it. However, this list goes on forever (we never put in a termination condition in the earlier code), so let's do that now.

We can use a simple empty check (null) to test if the hydra is still alive. Let's keep items as long as the Hydra is alive

takeWhileAlive (x:xs) = if null x then [] else x:(takeWhileAlive xs)

Putting the two together

repeatedlyChopTillDead heads = takeWhileAlive (repeatedlyChopTillDead heads)
——————————————————————————————————————
repeatedlyChopTillDead [4]
— [[4],[3,3,3],[2,2,3,3],[1,2,3,3],[2,3,3],[1,3,3],[3,3],[2,2,3],[1,2,3],[2,3],[1,3],[3],[2,2],[1,2],[2],[1]]

Again, these patterns are so common, that we can replace the entire thing with a single line. takeWhile keeps things in the list until the first element that doesn't match.

repeatedlyChopTillDead heads = takeWhile (not.null) (iterate chop heads)

Finishing up

Now that we have the sequence of chops needed to kill that Hydra, figuring out the number of chops is just a matter of figuring out how long the sequence is.

countOfChops heads = length (repeatedlyChopTillDead heads)
—————————————————————————
countOfChops [1] — 1
countOfChops [3] — 5
countOfChops [9,9,9,9,9,9,9,9,9] — 986409 (this takes a while)

Extending

Now that we've solved the problem, what next? How easy is it to extend this? Let's add a new requirement: Hercules, though a half god, can only fight at most n Hydra heads at a time. If the number of Hydra heads goes above n, then hercules dies. Let's make a function willHerculesDie which takes two parameters, n and the Hydra.

Turns out, this is pretty simple. We just need to count all the heads that are alive. If the count is more than n at any point, then we return true, and Hercules dies.

willHerculesDie n heads = any (> n) (map length (repeatedlyChopTillDead heads))
——————————————————————————————————————
willHerculesDie 37 [9,9,9,9,9,9,9,9,9] — False
willHerculesDie 36 [9,9,9,9,9,9,9,9,9] — True

So what next?

We've built a bunch of really composable functions, and we can look at each one independently to tune the system.

You can get Haskell set up with the Haskell Platform and play around with the code here.

Some great books you can check out:


If you liked this post, you could:

upvote it on Hacker News

<i>Original post by <a href="http://twitter.com/tdinkar">Tejas Dinkar</a> - check out <a href="http://blog.gja.in/">Side Effect Free Rants</a></i>

How to Disable the Google Hangouts Menu Bar Icon on OS X

This has been annoying me for weeks now. Google Hangouts would place an menu-bar icon for each instance of Chrome I had running. Repeatedly quitting them didn’t have much effect; they’d keep coming back.

Menu Bar Screenshot

Luckily, there’s an easy way to turn off the menu-bar icons.

  • Open Chrome
  • Menu Bar > Chrome > Preferences
  • Click on Extensions, scroll down to Hangouts, and click on Options
  • Uncheck Show system tray icon
  • Click OK

And that’s it.

Original post by Timothy Andrew - check out Timothy's Blog

Building an Offline Survey Tool for Rural India

At Nilenso, we’ve helped Ashoka accomplish their initiative in building infrastructure for the citizen sector.

Infiniti is a suite of products envisioned for social entrepreneurs, the fellows at Ashoka and other citizen sector organizations to get a variety of quality data through crowd sourcing, surveys and market research.

Field agents responsible for carrying out these organized surveys face problems where there is often severe lack of proper mobile connectivity and even basic amenities. The data capturing tools therefore need to be really effective offline and should have the capability to synced to the central server once the agents return back to camp.

It is currently very much in use at Ashoka around these verticals:

  • Nutrition and Wellness – for addressing malnutrition problem among children in India
  • Affordable Housing – for enabling access to housing in the informal sector
  • Rural Innovation and Farming – to understand the role of women in Agriculture

And is largely composed of these ideas:

Infiniti Suite

As a part of this, we built Ashoka Survey Web – one of the arms that takes care of data collection, validation, integrity and reporting.

How does Survey Web work?

It is a collection of these 4 applications:

Process

The fellows at Ashoka first identify the problem sets based on the verticals mentioned above and create a questionnaire that will effectively capture the data necessary. Once that is done, they use the survey builder to quickly digitise them. These surveys can be shared with different registered organisations or shared publicly.

The responses are then collected by the field agents of the respective organizations using the survey-mobile application that can take validated answers client-side and store them offline. These can be synced to survey-web, once the field agents get internet connectivity.

Here’s a figure explaining the roles and interfaces of each of these applications:

Architecture Diagram

We created a quick one-minute screencast that describes a simple workflow on how a survey is created, how a response is taken on that survey on the web and some basic reports you can see around it.

Need for a separate auth app

The user-owner app was built to serve as a centralized auth provider for all of Ashoka’s web services. It is implemented using the doorkeeper gem.

Survey Builder amongst the alternatives available

Wufoo and Google Forms aren’t designed for long surveys. They work well for short forms/questionnaires that can be answered on the web, but they do not have support for nesting questions or collecting responses from a mobile app offline.

OpenDataKit doesn’t have a good interface for building long surveys or nested questions. It requires working with XLS files for many complex operations.

SurveyMonkey is a good tool, but we couldn’t use it since we needed complete ownership of the survey and response data.

Survey Builder V2

The current survey builder works well and is pretty functional, but it fails on a few usability aspects.

  • Being able to switch between one question type to another. Simply using a drop-down bar instead of individual buttons to solve this.

  • Editing concerns are shared across both panes, fine-grained question (question options, sub-questions etc.) level editing is on the left pane, more general editing and meta-information (type of question, maximum/minimum values for answers etc.) about the questions is on the right.

We worked together with Accenture to come up with new designs and started working on rebuilding it last month. It is still in progress, and can be viewed from the create-v2 menu. The new visual designs are here.

The Native Android App

The survey-mobile app is built with Titanium. We’re looking to move away from this to a native android app. You can read a bit about where we’re at in this post and checkout the mockups here.

Data Portal

Each survey conducted by Ashoka typically has about 300 responses. We currently have some basic reports built with google charts. But we don’t have the ability to say, interpret data of similar/same respondents across multiple surveys.

This is a separate project where the idea is to build connections between disparate sources of data and make sense out of them.

Contribution

Each of these applications are entirely open-source, feel free to check them out on the nilenso GitHub page!