Character density using Haskell

In this short tutorial, I’m going to write a simple Haskell program to calculate the density of characters in a given text. For instance, in “hello” we have [('e',0.2),('h',0.2),('l',0.4),('o',0.2)].

The return format of our application would be a list of tuples

String -> [(Char, Float)]

To make the problem easier to solve, I’m going to break it into two programs. One that returns the number of repeats for each character and another program that converts that list to a percentage of repeats.

Count of repeats

freq_letter :: String -> [(Char, Int)]
freq_letter str = [ (x,c) | x <- ['a'..'z'], let c = (length.filter (==x)) str, c>0 ]

This program returns a list of tuples with the Char and Int. First item of tuple is the character in the given text and the second parameter, Int, is the count of repeats in the text. Executing this program will return:

*Main> freq_letter "hello"
[('e',1),('h',1),('l',2),('o',1)]

Percentage of repeats

freq_letter_pc :: String -> [(Char, Float)]
freq_letter_pc str = [ (char, fromIntegral(count) / fromIntegral(length str)) | x <- freq_letter (map toLower str), let (char,count) = x]

Second part of the application uses the previous program to get the list of repeats and then divide them by the length of the given text. This way we can calculate the density of characters in the text. Executing this program returns:

*Main> freq_letter_pc "hello"
[('e',0.2),('h',0.2),('l',0.4),('o',0.2)]

That's it.

Conclusion

In this tutorial, we have learnt how to calculate the density of characters using Haskell. Achieving this goal is much easier in Haskell because of list comprehension and higher order functions.

Optimized solution to calculate first powers of 2

I experienced many programming contests and olympiads but this one was really different. In a programming contest on Hacker Rank, I faced with a challenging problem and it was the main reason I failed the test. That question made me nervous and stressful so I gave up. When I found the solution after the test, I laughed so loud.

The question is:

Calculate sum of first powers of 2 without using any built-in language API to calculate the power. Implement optimized solution.

Well, there are two factors. First, not using built-in functions like Math.pow and second implementing the optimized solution. So, of course a recursive function or for-loop is not the answer.

 Answer

Use bitwise operations. How? Ok, let me show you a trick.

parseInt(10, '2')    == Math.pow(2, 1); //2^1 = 2
parseInt(100, '2')   == Math.pow(2, 2); //2^2 = 4
parseInt(1000, '2')  == Math.pow(2, 3); //2^3 = 8
parseInt(10000, '2') == Math.pow(2, 4); //2^4 = 16
//and so on

So, how to make 10, 100 or 1000? Using shift operations you can make it:

1 << 1 //2
1 << 2 //4
1 << 3 //8
1 << 4 //16

A short explanation of above source code is that the binary of 1 is 00000001 and when you use left shift operator, the result is 00000010, 00000100 and so on.

So the answer is to use a for-loop for N:

var sum = 0;
for (var i = 1;i <= n;i++) {
  sum += 1 << i;
}
console.log(sum);

 Can we make it better?

Yes. Here is the final hack.

The sum of first N powers of 2 is 2^(N + 1) - 2. For instance, n = 3:

(2 ^ (3 + 1)) - 2 = 16 - 2 = 2 + 4 + 8 = 14

And then, using bitwise operations we have:

console.log((2 << n) - 2);

Please note that the binary of 2 is 00000010.

Actually, this is the right answer.

Edit: You can find more interesting examples here: http://www.cs.utsa.edu/~wagner/knuth/fasc1a.pdf

Source: New feed

Using `object` as the keys of another `object` in JavaScript

Sometimes you need to use objects for the keys of a dictionary (let’s say, another object).

Assume this code:

var keys = [{a: 1}, {a: 2}, {a: 3}];
var dic = {};

//add a new key to the dictionary
dic[keys[0]] = 'boo';
dic[keys[1]] = 'foo';

Above code yields this result:

console.log(dic); //Object {[object Object]: "foo"}

So the dictionary doesn’t have two items because object keys cannot be object. You can get the item with [object Object] string:

console.log(dic['[object Object]']); //returns `foo`

Ok, wait. Then how we can set objects as the keys of a dictionary?

 ECMAScript 6 – Map

Map feature in ES6 enables you to assign objects as the keys of a dictionary (or another object).

Here is the ES6 compatible of the previous example:

var keys = [{a: 1}, {a: 2}, {a: 3}];
var map = new Map();

//add a new key to the dictionary
map.set(keys[0], 'boo');
map.set(keys[1], 'foo');

And the map variable should be:

Map {Object {a: 1} => "boo", Object {a: 2} => "foo"}

Besides, you can get the item with get:

map.get(keys[0]); //returns `boo`

Or set a new value for one of items:

map.set([keys[0], 'new value');

Here you can read more about Map feature in ECMAScript 6: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

Source: New feed

Block scope variable – ECMAScript 6

Since some of ECMAScript 6 features looks weird to old-fashioned JavaScripters, I’m going to write a series of blog posts to describe the main idea of some common ECMAScript 6 features.

In this posts I’d like to explain the usage of block scope variables. The keyword let enables you to create a block scope variable in ECMAScript 6:

let boo = 1;

So, what’s the difference between var boo = 1; and let boo = 1;? Assume following example:

function sample() {
  if (true) {
    var boo = 1;
  }
  return boo;
}

console.log(sample()); //returns 1

In the above old-fashioned code, boo variable is defined within the sample function scope so we have the value even outside of the if statement.

With let variable you can create a variable that is available within the if statement block:

function sample() {
  if (true) {
    let boo = 1;
  }
  return boo; //ReferenceError: boo is not defined
}

console.log(sample());

Awesome, isn’t it?

I will write more blog posts about ECMAScript 6 features soon.

Source: New feed

Source: New feed

Python: List and Tuple performance benchmark

Suppose you have two options to implement a solution using a programming language, what are important factors to select one of options? I do believe one of concerns for a programmer would be performance benchmark between those options.

In this short blog post I’d like to share my simple code and results for performance benchmark between Python list and tuple. Two features to create a list, but with this difference, that tuples are immutable and you can’t alter them after initializing.

Following code shows a simple usage of list and tuple to create a series of items:

# this is a list, you can alter it in next lines
l = [1, 2, 3, 4, 5]

# this is a tuple and it's immutable
t = (1, 2, 3, 4, 5) 

Please note that you can store different data types as an item for both tuple and list.

My scenario to make a performance benchmark between list and tuple is retrieving 2,000,000 random items from a list (or tuple) with 1,000,000 items.

Here is the source code for list:

import time
from random import randint


x = 1000000

demo_list = []

# add items to list
while x > 0:
    demo_list.append(x)
    x = x - 1

start = time.clock()

# find random items from list
y = 2000000
while y > 0:
    item = demo_list[randint(0, 999999)]
    y = y - 1

# print the elapsed time
print (time.clock() - start)

Following chart illustrates the performance benchmark between list and tuple on a Mac OS X 10.9.3 and Python 2.7.5:

Benchmark between list and tuple

Elapsed times:

  • Tuple: 5.1217s
  • List: 5.2462s

And it seems tuples are a little bit faster in retrieving items.

You can download the source code for both list and tuple from my Github account:
https://github.com/afshinm/python-list-vs-tuple-benchmark

Source: New feed

Using Redis as session store for ExpressJS + PassportJS settings

Since all other articles about using Redis as a session store for ExpressJS are out of date due to latest update of connect-redis, I’m going to write this short article to show how to use Redis as session store for ExpressJS.

In order to use Redis as session store for ExpressJS, first of all install connect-redis package using npm:

npm install connect-redis

Then, add connect-redis to your dependencies and Following code shows the content of app.js file:

var express = require('express');
var RedisStore = require('connect-redis')(express.session);

app.use(express.session({ store: new RedisStore({
  host: '127.0.0.1',
  port: 6379
}), secret: 'hey you' }));

If you’re using PassportJS for users authentication, you can simply add two following lines to your app.js file to enable PassportJS as well:

app.use(passport.initialize());
app.use(passport.session());

That’s it. Now you have PassportJS for authentication and Redis as session store for ExpressJS.

Furthermore you can use following code to delete the Redis session:

exports.logout = function (req, res) {
  req.session.destroy();
  res.redirect('/');
};

Source: New feed

Why C# is not a good choice for web development?

C# is the main programming language in Iran. I’ve worked with several teams, various projects and developers with different development skills. Earlier I’ve worked with PHP.

There weren’t any motivations to migrate from PHP to C# but the company’s infrastructure. Most of web development companies in Iran work with C# and Microsoft technologies, and here is the reason, because they don’t want to learn more. Companies prefer to stay at the same level and do not pay for improving their developers skills!

If you ask them: “Why you are using C# for web development?” I bet they won’t give you acceptable answer.

I haven’t used C# for my own projects, and I won’t at all. It’s preferable to me to use NodeJS or Python, not only because of their popularity, but because they are scripting languages.

After spending ages with C#-based web apps I want to tell something horrible about this language and why it’s not an appropriate choice for web development.

What I explain here is the issue that I faced with, several times. Before explaining the problem let me tell you something about C# compiler and how it works.

Suppose you have a Service Layer project, like following:

  • UserService.cs
  • GroupService.cs
  • NewsService.cs

All of above files are located in a same project (.csproj file). You can use this project as a dependency for other projects, for instance, the NewsService class to fetch news from database. If you compile it, compiler gives a .dll file. This file is used as a dependency file for other projects, meaning, in order to change only one method in NewsService class, you should replace whole dll file, not only one file.

And yes, I know, it’s not the problem of C#.

Ok, here is the difficulty. We have a C#-based web app in our company, we use MVC for it’s presentation. There are a lot of instances of this app that deployed in different machines. Suddenly, we realized that there is a performance issue in our app. One of our customers reported it to us. The remedy was change the logic of a method in the Service Layer.

The change is easy, change the method, build it and replace new dll with old one. But replacing the new dll file will change other class and methods signature and logic, too.

I realized that the current version of deployed application is a little bit older than last stable version. So, if I decided to replace the fixed Service Layer with the current one, application will break because of the change of other methods.

In this situation you can ask me why you don’t have any versioning system, this kind of issues can be solved using Semver or something. My answer is: we were wrong at the first days of structuring our team, so we missed this part.

But what if we used Python instead of C#? The key was as easy as fixing that method and upload only one file, without touching other files. Additionally, changing a C#-based web app version is a nightmare for me. Conflicts between dll files, their versions, etc.

Despite all great features and nice parts of C#, in my opinion above reasons make it a bad choice for web development.

At the end of nagging I want to show you something:

ASP.NET MVC

Is it cool to use a design pattern name as a name for framework?

Source: New feed

MongoDB singleton connection in NodeJs

In this post, I want to share a piece of useful source code to make a singleton connection in NodeJs. By using this piece of code, you will have always one connection in your NodeJs application, so it will be more faster. Also, if you are using NodeJs frameworks like ExpressJs, it will be useful too.

connection.js:

var Db = require('mongodb').Db;
var Connection = require('mongodb').Connection;
var Server = require('mongodb').Server;
//the MongoDB connection
var connectionInstance;

module.exports = function(callback) {
  //if already we have a connection, don't connect to database again
  if (connectionInstance) {
    callback(connectionInstance);
    return;
  }

  var db = new Db('your-db', new Server("127.0.0.1", Connection.DEFAULT_PORT, { auto_reconnect: true }));
  db.open(function(error, databaseConnection) {
    if (error) throw new Error(error);
    connectionInstance = databaseConnection;
    callback(databaseConnection);
  });
};

And simply you can use it anywhere like this:

var mongoDbConnection = require('./lib/connection.js');

exports.index = function(req, res, next) {
  mongoDbConnection(function(databaseConnection) {
    databaseConnection.collection('collectionName', function(error, collection) {
      collection.find().toArray(function(error, results) {
        //blah blah
      });
    });
  });
};

Now, you will have only one connection in your NodeJs application.

Download codes from Gist:

Let me know what you think 🙂

Source: New feed

Simplified MapReduce

I believe one of the best solutions to solve a programming problem is to find a paper or article and read it as a clue. Well, of course Wikipedia, BMI and other sources are really helpful but somehow reading them is a nightmare for me, because of complexity of explanation. Thus, It’s preferable for me to read a straightforward article to find the clue.

You have a problem you find a paper about it. Now you have one and a half problems. Understanding the paper, and implementing it.

— Amir Mohammad Saied (@gluegadget) February 6, 2014

And now, I want to straightforwardly describe one of usable algorithms, its called MapReduce. Perhaps you have heard that before in Hadoop, MongoDB or NoSQL discussions.

Here is an introduction to what is a MapReduce is:

MapReduce is a programming model for processing large data sets with a parallel, distributed algorithm on a cluster.

From: http://en.wikipedia.org/wiki/MapReduce

Mainly, a MapReduce used to gather information from a massive datasets, faster and easier. The algorithm consists of two main functions, map and reduce. The map function is used to collecting data from the inputs. At this step, map function breaks the input into smaller chunks. In reduce function; we will put or aggregate the map function’s results together, to make a single result.

The reduce function will always performed after the map function.

To understand the process better, I’d like to give an example. Suppose we have a news website, each news is an entity in our database. Each news item has an Array of keywords that describes the news. Following is a sample of a news item:

{
  title: ‘Hello world!’,
  description: ‘Hello world! This is the first post from our awesome news portal; we will publish more news here. Thanks.’
  keywords: [{
    word: ‘hello’,
    count: 1
  }, {
    word: ‘world’,
    count: 1
  }, {
    word: ‘news’,
    count: 2
  }, {
    word: ‘post’,
    count: 1
  }]
}

So, what we want to do? We have a lot of news items, and an Array of keywords inside each one. We are going to determine popular keywords from all news items.

First of all, the map function will break the news item into smaller pieces. Actually, we should emit the keyword and the number of repeat inside the map function. The emit function is used to push new values into a temporary key-value pair, this array will be used in reduce function further to generate a single value.

Following is an example of map function source code:

function () {
  this.keywords.forEach(function (doc) {
    emit(doc.word, doc.count);
  })
}

To understand the map function better, following is an output of this function. When we have “hello” word that repeated twice with out number of 1 and 3, the output will be:

{ “hello”: [1, 3] }

And when we have the word “post” that repeated once, with count number of 2, the output would be:

{ “post”: [2] }

Then, we have the reduce function. Inside the reduce function we will wrap up map function’s result to create a single value. The single value is a keyword with total count of repetition in all news items.

Following is the reduce function source code:

function (key, values) {
  return Array.sum(values);
};

So, following is the output of reduce function:

{ id: “hello”, value: 4 }

And for the second map function’s output, the result will be:

{ id: “post”, value: 2 }

After performing the reduce function, we will have a set of keywords with the total count of repetition amongst all news items, that is, the array of popular keywords.

Of course the above explanation was a briefly look into the MapReduce algorithm. There are a lot of MapReduce frameworks and you can find them in NoSQL databases, MongoDB for instance.

Source: New feed