Haskell’s nub function and complexity

Haskell is a purely functional language and efficiency is quite often a major concern. A well designed Haskell program performs on par with Java, but not as fast as C.

The nub function (defined in Data.List) eliminates duplicate values from a list. It is an oft-used function for Haskell programmers. However it has a worst case complexity of O(n²), which means it is almost useless for very large lists. This blog post presents alternative definitions for reducing complexity under different circumstances.

First, let’s look at (one of) the standard definition of the nub function:

nub :: (Eq a) => [a] -> [a]
nub [] = []
nub (x:xs) = x : nub (filter (\y -> x /= y) xs)

This definition compares each element to the (rest of) the list and eliminates the duplicates. The complexity is O(n²), or to be more precise ½O(n²).

The simplest way to reduce the worst case complexity from O(n²) to O(n . log n) is to convert it to a set and then back to a list.

import qualified Data.Set as S
nub' :: (Ord a) -> [a] -> [a]
nub' = Set.toList . Set.fromList

By definition a set contains only unique values, so this will obviously eliminate all duplicates from the list. However this requires the elements of a list to be Orderable (members of the Ord class), as Eq class is not sufficient. Continue reading Haskell’s nub function and complexity

Latex and dash characters

Unicode defines numerous dash characters, some of which are language-specific. It is sometimes confusing to know what character to use when and for what purpose? Here are brief guidelines for properly using dash characters, particularly in LATEX.

The common dash characters are:

  1. a hyphen (-), U+002D
  2. an en-dash (–), U+2013
  3. an em-dash (—), U+2014
  4. a minus sign (−), U+2212

A hyphen is used in compound words, for example ‘son-in-law’, and in hyphenation (which is handled automatically by Latex). In latex source, just type the hyphen character which is found in all Latin keyboards:

son-in-law

The en-dash character is used in number ranges, for example ‘pages 9–13’, and other number contexts like ‘exercise 2.5–8’. To typeset en-dash in Latex, type double hyphens: ‘-‏-’: Continue reading Latex and dash characters

Swedish keyboard with Arabic romanization

Swedish keyboard layout for Microsoft Windows containing features for easily entering special letters used for Arabic romanization/transliteration. Distributed under the GNU General Public License. This program comes with ABSOLUTELY NO WARRANTIES. Use it at your own risk.

Download zip file (359 kb)

Source code is available from Github:
https://github.com/arnizamani/Swedish-ARN

Special letters for romanization of Arabic are based on ALA-LC romanization scheme for Arabic (American Library Association – Library of Congress). This scheme is in wide use today. See Wikipedia on Romanization of Arabic.

Short instructions for installation and use:

  1. Unzip the downloaded file.
  2. Go to swe-arn folder and open setup.exe, follow the instructions to install the program.
  3. Log-out from your computer and log-in.
  4. If the keyboard is not visible in the list of languages in the Taskbar, you can manually install it in Control Panel -> Languages.

The key “-” in standard Swedish layout has been turned into a dead key. Press this key once, then press any of the following keys to get a corresponding character. Continue reading Swedish keyboard with Arabic romanization

Open-source free software for Windows

I use Windows most of my time. Here is a list of open-source free software I often use and recommend to others.

Free software mostly has a deep learning curve, but you get the same functionality (often more) than commercial software. Invest a little time and save money!

flux-icon-smF.lux makes the color of your computer’s display adapt to the time of day, warm at night and like sunlight during the day. It helps you sleep better after using your laptop at night. Available for Windows, Mac and Linux.

FireFoxLogo128x128Firefox: open-source web browser made by people

Thunderbird: free email software (includes good Addons for calendar and tasks)

LibreOffice has all the features that Microsoft Office offers, but is not as user-friendly as the later.

FileZilla is the best software for managing FTP.

Notepad++ is the great notepad application (only for Windows). A haven for programmers!

For the cloud, I recommend Mega.co.nz, a fully encrypted service offering 50GB for free. You cannot share files with others, so use it for personal online backup. It has a desktop application for syncing files similar to Dropbox.

Create Synchronicity can be used to sync files to an external hard drive (or local drive) for backup.

7zip is a lightweight compression program. Can read/write most of the zip formats. Just right-click a compressed file and see options.

FFmpeg is a very powerful audio/video editing tool that can convert, resize, reformat, merge, play, record and stream audio and video files. Hard to use, but very powerful.

ImageMagick contains tools for editing pictures and bitmaps. I used it to batch process scanned pages of books.

WinDjView: A fast and powerful DjVu viewer. DjVu format is a digital document format for digitized (scanned) documents with advanced compression technology (see djvu.org).

RSSOwlRSSOwl is a free and powerful news feed reader. RSSOwl lets you gather, organize and search news in a convenient, easy to use interface with endless flexibility.

Scribus is an open-source desktop publishing software and a free alternative to Microsoft Publisher and Adobe InDesign.

Calibre is a great software for organizing your ebooks. It has features to organize, convert and manage ebooks in various formats.

Cogni

Cogni Apps Organizer
Cogni Apps Organizer

Cogni is an Android app that can list the installed apps on a phone by the frequency of usage. I developed it for fun only as my first mobile app. It uses mathematical formulas to list the most relevant apps first. Relevance is computed from frequency and recency of usage, time and day. Later, I plan to include GPS location and other attributes to the relevance function.

Warning: Do not use it for serious work. It is a rudimentary app and designed for testing.

Download from Playstore