[home] [about me] [rss]

Designing a Purely Functional Data Structure

Functional programming nicely leverages constraints on how programs are written thereby promoting a clean and easy to reason about coding style. Purely functional data structures are (surprisingly) built out of those constraints. They are persistent (FP implies that both old and new versions of an updated object are available) and backed by immutable objects (FP doesn't support destructive updates). Needless to say, it's a challenge to design a purely functional data structure that meets performance requirements of its imperative sibling. Fortunately, it's quite possible in most of the cases, even for those data structures whose reference implementations are backed by mutable arrays. This post precisely describes a process of designing a purely functional implementation technique for Standard Binary Heaps, with the same asymptotic bounds as in an imperative setting.

Combinatorial Algorithms in Scala

Combinatorics is a branch of mathematics that mostly focuses on problems of counting the structures of given size and kind. The most famous and well-known examples of such problems might be often asked as job interview questions. This blog post presents four generational problems (combinations, subsets, permutations and variations) along with their purely functional implementations in Scala.

Dual-Pivot Binary Search

In 2009, Vladimir Yaroslavski introduced a Dual-Pivot QuickSort algorithm, which is currently the default sorting algorithm for primitive types in Java 8. The idea behind this algorithm is both simple and awesome. Instead of using single pivot element, it uses two pivots that divide an input array into three intervals (against two intervals in original QuickSort). This allowed to decrease the height of recursion tree as well as reduce the number of comparisons. The post describes a similar dual-pivot approach but for a BinarySearch algorithm. Thus, our modified binary search algorithm has prefix Dual-Pivot.

Finagle Your Fibonacci Calculation

Finagle is an RPC library for JVM that allows you to develop service-based applications in a protocol-agnostic way. Formally, the Finagle library provides both asynchronous runtime via futures and protocol-independence via codecs. In this post I will try to build a Finagle-powered distributed Fibonacci Numbers calculator that scales up to thousands of nodes.

In The Beginning

This is my first post on this blog. Needless to say, I'm really excited about this. This is my first attempt in writing blog posts in English. I was previously posting in Russian at LJ and Tumbler, but it wasn't about technical things. Here, I will try to post only about CS. I have huge plans on posting about Scala and it's application for research of purely functional data structures. I should probably post about algorithms and data structures that I've already implemented in Scalacaster. There are loads of awesome pieces of Scala code that I want to tell about. One of my favorites - QuickSelect in a purely functional setting.