Building a prefix trie

Prefix trie‘s are cool data structures that let you compress a dictionary of words based on their shared prefix. If you think about it, this makes a lot of sense. Why store abs, abbr, and abysmal when you only need to store a,b,b,r,s,y,s,m,a,l. Only storing what you have to (based on prefix) in this example gives you a 70% compression ratio! Not too bad, and it would only get better the more words you added.

The classical way of dealing with prefix tries is to store the suffixes using a map, but for fun I tried something different and used a list.

Data

The main data structure I had was like this

type Key a = [a]

data Trie key = Node (Maybe key) [Trie key] Bool deriving (Show, Eq, Read)

So a trie is really just a node that has a list of other tries … Read more

Avoiding nulls with expression trees

I’ve blogged about this subject before, but I REALLY hate null refs. This is one of the reasons I love F# and other functional languages, null ref’s almost never happen. But, in the real world I work as a C# dev and have to live with C#’s… nuisances.

In the other post, a big problem with the dynamic proxy was that it only worked with virtual methods, so it wasn’t really all that practical. This time around I decided to try a different route and leverage expression tree’s to actually build out the if checks automatically.

For the impatient, full source available at my github and the library is available on nuget

Demonstration

Let me demonstrate the final usage first. If all of users properties and methods return null, executing this whole chain would fail starting at the null result of GetSchool(). But, by using the Option static … Read more

Strongly typed powershell csv parser

Somehow I missed the powershell boat. I’ve been a .NET developer for years and I trudged through using the boring old cmd terminal, frequently mumbling about how much I missed zsh. But something snapped and I decided to really dive into powershell and learn why those who use it really love the hell out of it. After realizing that the reason everyone loves it is because everything is strongly typed and you can use .NET in your shell I was totally sold.

My first forays into powershell included customizing the shell environment. First I got conemu and made it look nice and pretty. Next was to get an ls highlighting module, since I love that about unix shells.

I set up a few fun aliases in my profile and felt ready to conquer the world! My next experiment was to try and create an actual binary cmdlet. I figured, what … Read more

A simple templating engine

I wanted to talk about templating, since templating is a common thing you run into. Often times you want to cleanly do a string replace on a bunch of text, and sometimes even need minimal language processing to do what you want. For example, Java has a templating engine called Velocity, but lots of languages have libraries that do this kind of work. I thought it’d be fun to create a small templating engine from scratch with F# as an after work exercise.

The goal is to give the templating processor a set of lookup bags that can be resolved by variables. For example, if I use a variable $devshorts.isgreat that should correspond to a bag that is keyed first off of devshorts which returns a new bag, and then a new bag that has a key isgreat which should return a value.

Getting the AST

First, lets parse the … Read more

RxJava Observables and Akka actors

I was playing with both akka and rxjava and came across the following post that described how to map rxjava observables from messages posted to akka actors.

Since my team works in java, I decided to try mapping the concept to java directly, but found that there was an issue. When I tried to have multiple subscribers listen on the stream I’d get an exception since more than one subscriber would send the “subscribe” message and try to modify the akka receive context.

I also wanted to make it easier to extend the actors to be able to process a piece of work, and then resubmit it for consumption by the observable.

The subscribe command messages

First, let me show the commands we can send to the actors. This is just mapping the scala union type that the original blog post had. The @Data attribute is part of project lombokRead more

Debugging F# NUnit equals for mixed type tuples

Twitter user Richard Dalton asked a great question recently:

Twitter question

And after a bit more digging he then mentioned

Twitter question

Interesting. I downloaded the NUnit source and saw this:

public bool AreEqual(object x, object y, ref Tolerance tolerance)
{
    this.failurePoints = new List<FailurePoint>();

    if (x == null && y == null)
        return true;

    if (x == null || y == null)
        return false;

    if (object.ReferenceEquals(x, y))
        return true;

    Type xType = x.GetType();
    Type yType = y.GetType();

    EqualityAdapter externalComparer = GetExternalComparer(x, y);
    if (externalComparer != null)
        return externalComparer.AreEqual(x, y);

    if (xType.IsArray && yType.IsArray && !compareAsCollection)
        return ArraysEqual((Array)x, (Array)y, ref tolerance);

    if (x is IDictionary && y is IDictionary)
        return DictionariesEqual((IDictionary)x, (IDictionary)y, ref tolerance);

    //if (x is ICollection && y is ICollection)
    //    return CollectionsEqual((ICollection)x, (ICollection)y, ref tolerance);

    if (x is IEnumerable && y is IEnumerable && !(x is string && y is string))
        return EnumerablesEqual((IEnumerable)x, (IEnumerable)y, ref tolerance);

    if (x is string && … Read more
Single producer many consumer

When I’m bored, I like to roll my own versions of things that already exist. That’s not to say I use them in production, but I find that they are great learning tools. If you read the blog regularly you probably have realized I do this A LOT. Anyways, today is no different. I was thinking about single producer, multiple consumer functions, like an SNS Topic, but for your local machine. In reality, the best way to do this would be to publish your event through an Rx stream and consume it with multiple subscribers, but that’s no fun. I want to roll my own!

BlockingCollection in .NET supports thread safe multiple consumers, but only 1 item will ever get dequeued from your collection. That means that if you have multiple threads waiting on a consuming enumerable, only one of them will get a result (not all of them). That’s … Read more

Building LINQ in Java pt 2

In my last post I discussed building a static class that worked as the fluent interface exposing different iterator sources that provide transformations. For 1:1 iterators, like take, skip, while, for, nth, first, last, windowed, etc, you just do whatever you need to do internally in the iterator by manipulating the output the stream.

But if you want to do a transformation like a map, you need to project the input source to something else. Now the base class each iterator inherits from isn’t good enough. But thankfully we can just add another generic parameter and create a new mappable base class that can handle transformations.

The following iterator handles projecting from a source to a result type and yields an enumerable iterator of the result type.

package com.devshorts.enumerable.iterators;

import java.util.function.Function;

public class MapIterator<TSource, TResult> extends EnumerableIterator<TResult> {

    private Function<TSource, TResult> projection;

    /***
     * Need this constructor for flatMap
     * … Read more
Logitech mx mouse zoom button middle click on Ubuntu

Any good engineer has their own tools of their trade: keyboard, mouse, and licenses to their favorite editors (oh and a badass chair).

I work now on an Ubuntu box and I wanted to get my logitech MX mouse’s zoom button to act as middle click. I really like this functionality since its easy to copy, paste, close windows, and open new links with this button.

However, the button mapping in Ubuntu isn’t trivial. On windows you used the setpoint program to do it and called it a day. But in linux land you need to put more work into it.

Here is a great tutorial describing how to do it, but for the lazy, here is the mapping you need.

"xte 'mouseclick 2'"
  b:13+Release

What this says is “when button 13 is clicked, then released, issue a mouseclick 2 command”. xte is a program that simulates mouse and … Read more

Filter on deep object properties in angularjs

AngularJS provides a neat way of filtering arrays in an ng-repeat tag by piping elements to a built in filter filter which will filter based on a predicate. Doing it this way you can filter items based on a function, or an expression (evaluated to a literal), or by an object.

When filtering by an object you can pass in a javascript object that represents key value items that should match whats in the backing data element. For example:

$scope.elements = [{ foo: "bar" }, { foo: "biz" }]

--

<div ng-repeat="foos in elements | filter: { foo: "bar" }">
  {{ foos.foo }} matches "bar"
</div>

Here I filtered all the objects whose foo property matches the value “bar”. But what if I have a non-trivial object? Something with lots of nested objects? I found that passing in the object to the filter was both unweidly, and error prone. I … Read more