Jack Marchant

Principal Software Engineer @ Deputy

Twitter | GitHub

A Queue is just a Q with 4 silent letters

A Queue is a collection data structure, which uses the FIFO (First In, First Out) method. This means that when you add items to a queue, often called enqueuing, the item takes its place at the end of the queue. When you dequeue an item, we remove the item from the front of the queue.

Both of these methods will change the length of the queue. A peek method can be implemented to look at what the first item is in the queue, without removing the item, leaving the queue unchanged.

Queues are often implemented with list data structures, such as a Linked List. In Elixir, lists are singly-linked lists under the hood. We’re able to access the head and tail of a list, which refer to the first item in the list and the rest of the list, respectively.

[head | tail] = [1, 2, 3]
> head
1
> tail
[2, 3]

If you think about implementing a queue in Elixir, we would need to implement the following methods:

Let’s look at each of these individually.

Enqueue

When adding an item to a list in Elixir, it’s common to prepend to the list, then reverse it when accessing it to preserve order. As lists are singly-linked in Elixir, it is much faster to add to the front of the list, rather than adding to the end and having to re-create all of the links in the list.

For this reason, you could implement an enqueue function in this way:

@spec enqueue(list(), any()) :: list()
def enqueue(queue, item) do
  [item | queue]
end

Dequeue

Now that we have items in a list, we need a way to remove one when we call dequeue. I started having a look at how Elixir deletes items from a list and found List.delete/2 — we can see a few function heads there, but here are the two lines you need to appreciate:

def delete([item | list], item), do: list  
def delete([other | list], item), do: [other | delete(list, item)]

The first argument is the list, and the second argument is the item to be removed. Elixir binds the second argument name as the same value as the head of the list, and if this function is called, it returns the tail (thus removing the item from the list). Otherwise, if the two item variables are not a match, the head is prepended and delete/2 is recursively called on the tail.

That might be a bit to take in, but I recommend trying it out in an interactive Elixir shell iex.

Although we don't need List.delete/2 in this case, we can implement a dequeue function like so:

@spec dequeue(list()) :: {any(), list()}
def dequeue([]), do: nil
def dequeue(queue) when length(queue) <= 2 do
 [item | tail] = Enum.reverse(queue)
 {item, tail}
end
def dequeue(queue) do 
 {Enum.at(queue, -1), Enum.drop(queue, -1)}
end

We return a tuple in this function, because we want to know both the item that was dequeued, and the remaining items in the queue (so we can enqueue more items later). It’s worth noting as well that this is not the most efficient solution, as it is using an O(n) algorithm because the Enum methods we’re using are always going to enumerate of the list to get the last item.

Peek

A peek function is simply a utility to allow looking at the front of the queue, without changing the queue itself. Although, you might want to add some extra function heads to cater for empty lists.

@spec peek(list()) :: any() | nil
def peek([]), do: nil
def peek(queue) do
  [h | _ ] = queue
  h
end

Count

Similarly, count is the number of items still in the queue, and can be implemented as such:

@spec count(list()) :: integer()
def count([]), do: 0
def count(queue), do: length(queue)

These functions are all fine in theory, but when we start to think about implementing a queue in Elixir, we can’t wrap this up in a class that knows about it’s own state. Instead, we could implement these functions as part of a GenServer, which will hold it’s own state and can be updated over time.

Priority Queue

When simple FIFO doesn’t cut it and you need to be able to process items in a queue before others we can implement a Priority Queue. This means that when an item is enqueued, it doesn’t necessarily go to the back of the queue (or front of the list in Elixir), each new item needs to be compared with other items until we find a suitable place for it based on its priority.

Priority could mean integer values, for example the number 10 would have a higher priority than 5, because it is the higher value. Imagine the following queue:

head -> 7 - 3 - 1 <- tail

If we base priority on the higher integer values, and we add 10 to this queue, we would expect it to take priority over all other values because it is highest. So we’re left with the following queue:

head -> 10 - 7 - 3 - 1 <- tail

If the priority of the new item was not higher than any of the existing items, it would simply be added to the end of the queue.

Queue’s have a variety of real-world applications, such as scheduling asynchronous work or handling large amounts of requests. High priority requests can be processed first, and lower priority processed later.

I decided to implement a simple Queue library using a GenServer, and optional priority, you can take a look at the documentation or go straight to the code

. . .

how does a relational database index really work

A common question in software engineering interviews is how can you speed up a slow query? In this post I want to explain one answer to this question, which is: to add an index to the table the query is performed on.

refactoring for performance

I spend most of my time thinking about performance improvements. Refactoring is tricky work, even more so when you’re unfamiliar with the feature or part of the codebase.

exploring async php

Asynchronous programming is a foundational building block for scaling web applications due to the increasing need to do more in each web request. A typical example of this is sending an email as part of a request.

maintaining feature flags in a product engineering team

I have mixed feelings about feature flags. They are part of the product development workflow and you would be hard pressed to find a product engineering team that doesn’t use them. Gone are the days of either shipping and hoping the code will work first time or testing the life out of a feature so much that it delays the project.

technical interviewing

When I first started interviewing candidates for engineering roles, I was very nervous. The process can be quite daunting as both an interviewer and interviewee. The goal for the interviewer is to assess the candidate for their technical capabilities and make a judgement on whether you think they should move to the next round (there’s always a next round). Making a judgement on someone after an hour, sometimes a bit longer, is hard and error prone.

using a dependency injection container to decouple code

Dependency Injection is the method of passing objects to another (usually during instantiation) to invert the dependency created when you use an object. A Container is often used as a collection of the objects used in your system, to achieve separation between usage and instantiation.

3 tips to help with working from home

Working from home has been thrust upon those lucky enough to still have a job. Many aren’t sure how to cope, some are trying to find ways to help them through the day. Make no mistake, this is not a normal remote working environment we find ourselves in, but nonetheless we should find ways to embrace it.

making software a three step process

One of the most useful tips that has guided much of my decision over the years has been this simple principle: three steps, executed in sequential order;

help me help you code review

Code Reviews are one of the easiest ways to help your team-mates. There are a number of benefits for both the reviewer and pull request author:

a pratical guide to test driven development

It’s been a while since I last wrote about why testing is important, but in this post I thought I would expand on that and talk about why not only unit testing is important, but how a full spectrum of automated tests can improve productivity, increase confidence pushing code and help keep users happy.

facade pattern

Design Patterns allow you to create abstractions that decouple sections of a codebase with the purpose of making a change to the code later a much easier process.

the problem with elixir umbrella apps

Umbrella apps are big projects that contain multiple mix projects. Using umbrella apps feels more like getting poked in the eye from an actual umbrella.

broken windows

Ever get the feeling that adding this "one little hack", a couple of lines of code, won't have much of an impact on the rest of the codebase? You think nothing of it and add it, convincing your team members it was the correct decision to get this new feature over the line. In theory, and generally speaking, I would kind of agree with doing it, but every hack is different so it's hard to paint them all with the same brush. If you've been doing software development for long enough you can see this kind of code coming from a mile away. It's the kind of code that can haunt your dreams if you're not careful.

lonestar elixir 2019

Last week was Lonestar ElixirConf 2019 held in Austin, Texas. The conference ran over 2 days and was the first Elixir conference I had been to.

genserver async concurrent tasks

In most cases I have found inter-process communication to be an unnecessary overhead for the work I have been doing. Although Elixir is known for this (along with Erlang), it really depends on what you’re trying to achieve and processes shouldn’t be spawned just for the fun of it. I have recently come across a scenario where I thought having a separate process be responsible for performing concurrent and asynchronous jobs would be the best way to approach the problem. In this article I will explain the problem and the solution.

best practices third party integrations

When we think about what an application does, it's typical to think of how it behaves in context of its dependencies. For example, we could say a ficticious application sync's data with a third-party CRM.

you might not need a genserver

When you're browsing your way through Elixir documentation or reading blog posts (like this one), there's no doubt you'll come across a GenServer. It is perhaps one of the most overused modules in the Elixir standard library, simply because it's a good teaching tool for abstractions around processes. It can be confusing though, to know when to reach for your friendly, neighbourhood GenServer.

offset cursor pagination

Typically in an application with a database, you might have more records than you can fit on a page or in a single result set from a query. When you or your users want to retrieve the next page of results, two common options for paginating data include:

protocols

Protocols are a way to implement polymorphism in Elixir. We can use it to apply a function to multiple object types or structured data types, which are specific to the object itself. There are two steps; defining a protocol in the form of function(s), and one or many implementations for that protocol.

exdocker

Recently, I've been writing a tonne of Elixir code, some Phoenix websites and a few other small Elixir applications. One thing that was bugging me every time I would create a new project is that I would want to add Docker to it either straight away because I knew there would be a dependency on Redis or Postgres etc, or halfway through a project and it would really slow down the speed at which I could hack something together.

working with tasks

While writing Understanding Concurrency in Elixir I started to grasp processes more than I have before. Working with them more closely has strengthened the concepts in my own mind.

understanding concurrency

Concurrency in Elixir is a big selling point for the language, but what does it really mean for the code that we write in Elixir? It all comes down to Processes. Thanks to the Erlang Virtual Machine, upon which Elixir is built, we can create process threads that aren't actual processes on your machine, but in the Erlang VM. This means that in an Elixir application we can create thousands of Erlang processes without the application skipping a beat.

composing ecto queries

Ecto is an Elixir library, which allows you to define schemas that map to database tables. It's a super light weight ORM, (Object-Relational Mapper) that allows you to define structs to represent data.

streaming datasets

We often think about Streaming as being the way we watch multimedia content such as video/audio. We press play and the content is bufferred and starts sending data over the wire. The client receiving the data will handle those packets and show the content, while at the same time requesting more data. Streaming has allowed us to consume large media content types such as tv shows or movies over the internet.

elixir queues

A Queue is a collection data structure, which uses the FIFO (First In, First Out) method. This means that when you add items to a queue, often called enqueuing, the item takes its place at the end of the queue. When you dequeue an item, we remove the item from the front of the queue.

composing plugs

Elixir is a functional language, so it’s no surprise that one of the main building blocks of the request-response cycle is the humble Plug. A Plug will take connection struct (see Plug.Conn) and return a new struct of the same type. It is this concept that allows you to join multiple plugs together, each with their own transformation on a Conn struct.

elixir supervision trees

A Supervision Tree in Elixir has quite a number of parallels to how developers using React think about a component tree. In this article I will attempt to describe parallel concepts between the two - and if you've used React and are interested in functional programming, it might prompt you to take a look at Elixir.

surviving tech debt

Technical debt is a potentially crippling disease that can take over your codebase without much warning. One day, you’re building features, the next, you struggle to untangle the mess you (or maybe your team) has created.

pattern matching elixir

Before being introduced to Elixir, a functional programming language built on top of Erlang, I had no idea what pattern matching was. Hopefully, by the end of this article you will have at least a rudimentary understanding of how awesome it is.

first impressions elixir

Elixir is a functional programming language based on Erlang. I’m told it’s very similar to Ruby, with a few tweaks and improvements to the developer experience and language syntax.

write unit tests

Unit testing can sometimes be a tricky subject no matter what language you’re writing in. There’s a few reasons for this: