Jacob Carpenter’s Weblog

March 26, 2008

LINQ to prime numbers

Filed under: csharp, Euler, LINQ — Jacob @ 4:41 pm

Having last Friday off, and finding myself in want of something to do, I decided to learn F#. Once I installed F#, though, I learned that desire and motivation are different things.

So I started killing time by solving Project Euler problems. In LINQPad.

(Which you really should download, if you haven’t already.)

People more eloquent than me can explain how embracing constraints helps creativity flourish. I’m not going to try.

Instead, I’ll share a prime number generator inspired by Euler problem 10 and implemented with LINQ:

var odds =
	from n in Enumerable.Range(0, int.MaxValue)
	select 3 + (long) n * 2;

var primes = (new[] { 2L }).Concat(
	from p in odds
	where ! odds.TakeWhile(odd => odd * odd <= p).Any(odd => p % odd == 0)
	select p);

This certainly isn’t the most efficient prime number generator in the world. But the full query to solve the problem (left as a exercise to the reader) runs in a perfectly acceptable less than six seconds on my machine. And it uses no intermediate storage for the primes!

Now that you’ve downloaded LINQPad—you have downloaded LINQPad, haven’t you?—you can start solving Project Euler problems in a blissfully constrained environment, too!

I’ve got Problem 1 down to 54 characters. 🙂

Advertisements

March 13, 2008

Dictionary To Anonymous Type

Filed under: csharp, extension methods, LINQ — Jacob @ 5:34 pm

There’s some buzz about how cool it is to initialize a Dictionary from an anonymous type instance. Roy Osherove recently wrote about it, though he attributes the technique to the ASP.NET MVC framework. Alex Henderson (whose blog I just subscribed to) also came up with an inspiring use of Lambda expressions to initialize Dictionaries (don’t miss the related posts at the bottom).

But I haven’t seen anyone do the reverse: initialize an anonymous type instance from a Dictionary.

Until now.

Prerequisites

public static class DictionaryUtility
{
    public static TValue GetValueOrDefault<TKey, TValue>(this IDictionary<TKey, TValue> dict, TKey key)
    {
        TValue result;
        dict.TryGetValue(key, out result);
        return result;
    }
}

Show me the code!

public static class AnonymousTypeUtility
{
    public static T ToAnonymousType<T, TValue>(this IDictionary<string, TValue> dict, T anonymousPrototype)
    {
        // get the sole constructor
        var ctor = anonymousPrototype.GetType().GetConstructors().Single();

        // conveniently named constructor parameters make this all possible...
        var args = from p in ctor.GetParameters()
            let val = dict.GetValueOrDefault(p.Name)
            select val != null && p.ParameterType.IsAssignableFrom(val.GetType()) ? (object) val : null;

        return (T) ctor.Invoke(args.ToArray());
    }
}

Notice anonymousPrototype. This is a technique called casting by example, coined by Mads Torgerson (of the C# team) in the comments of this post.

Since you can’t ever explicitly refer to the type of an anonymous type, you have to provide an example instance. Using an undocumented feature of the default keyword, we can strongly type the properties of our prototype object without a bunch of null casting.

Here’s some sample code to get you going:

class Program
{
    static void Main(string[] args)
    {
        var dict = new Dictionary<string, object> {
            { "Name", "Jacob" },
            { "Age", 26 },
            { "FavoriteColors", new[] { ConsoleColor.Blue, ConsoleColor.Green } },
        };

        var person = dict.ToAnonymousType(
            new
            {
                Name = default(string),
                Age = default(int),
                FavoriteColors = default(IEnumerable<ConsoleColor>),
                Birthday = default(DateTime?),
            });

        Console.WriteLine(person);
        foreach (var color in person.FavoriteColors)
            Console.WriteLine(color);
    }
}

And thanks to anonymous types overriding ToString(), our program reasonably outputs:

{ Name = Jacob, Age = 26, FavoriteColors = System.ConsoleColor[], Birthday =  }
Blue
Green

Notice that the types don’t even need to exactly match! The dictionary’s “FavoriteColors” value is a ConosleColor[]. But the anonymous type has an IEnumerable<ConsoleColor> property.

Enjoy!

March 3, 2008

Chained generic argument dependence revisited

Filed under: csharp — Jacob @ 6:36 pm

My last post had a fatal flaw: it looked like it was about F# and pattern matching.

The bit I was most proud of was the interesting application of generic parameters, constraints, and type inference—a sort of chained generic argument dependence. But I tricked you into thinking I was solving a very specific problem (that precious few of you care about).

But just today, I encountered a more generalized case where this type of generic abuse makes perfect sense!

A brief interruption

Raise your hand if you know what “functional composition” is.

For those of you with your hands firmly planted on your mice, functional composition is a really simple concept:

Say you have a function, let’s call it f, that takes an x and returns a y. You have another function, g, which takes a y and returns a z. Using functional composition, you can create a new function (h, for instance) which takes an x and returns a z.

That is, in C#, given:

Func<TX, TY> F;
Func<TY, TZ> G;

F and G can be composed as:

Func<TX, TZ> H = x => G(F(x));

Simple enough, right? Well, pretend we think this is useful enough to abstract to a utility method.

The definition would look something like:

public static Func<T1, TResult> Compose<T1, T2, TResult>(this Func<T1, T2> func1, Func<T2, TResult> func2)
{
    return t1 => func2(func1(t1));
}

Did you notice anything about that method signature?

We’ve introduced a form of chained generic argument dependence. The second parameter’s type depends on the first. Specifically, the second parameter must be a function whose argument matches the type of the return value of the first function.

In the case of Compose, this dependence isn’t a difficult API design decision; it’s merely an outcome of what we’re trying to express. But in some situations harnessing this chained dependence (and the compiler’s type inference capabilities) can result in an interesting API.

Real-world example

I’m surprised more people haven’t included some form of a null propagating operator on their C# 4.0 feature request lists. Well, Ed blogged our take on the operator awhile ago.

Let’s use that definition of IfNotNull to create a “real world” example of chained generic argument dependence. And how much more “real world” can you get than Customers and Orders?

class Customer
{
    public string Name { get; set; }
    public IList<Order> Orders { get; set; }
}

class Order
{
    public string Product { get; set; }
}

public static class IfNotNullExtension
{
    public static U IfNotNull<T, U>(this T t, Func<T, U> fn)
    {
        return t != null ? fn(t) : default(U);
    }
}

Let’s say we want to get the name of the first product of the first order. Using the above IfNotNull extension method, the code would look something like:

static void Main(string[] args)
{
    var customers = new[] {
        new Customer { Name = "Alejandro C. Dazé", Orders = new [] { new Order { Product = "Widget" } } },
        new Customer { Name = "Brad S. Grahne", Orders = null },
        null,
    };

    foreach (Customer cust in customers)
    {
        string productName = cust.IfNotNull(c => c.Orders)
            .IfNotNull(orders => orders.FirstOrDefault())
            .IfNotNull(o => o.Product);

        Console.WriteLine(productName ?? "<null>");
    }
}

The output of which is:

Widget
<null>
<null>

Works great! But we have an opportunity here to use chained generic argument dependence to remove a couple of those calls to IfNotNull.

Chained generic argument dependence

Using our previous definition of IfNotNull, we can add the following (naively implemented) overload:

public static TResult IfNotNull<T1, T2, T3, TResult>(this T1 t,
    Func<T1, T2> fn1, Func<T2, T3> fn2, Func<T3, TResult> fnResult)
{
    return t.IfNotNull(fn1).IfNotNull(fn2).IfNotNull(fnResult);
}

Then, our calling code can become:

string productName = cust.IfNotNull(c => c.Orders,
    orders => orders.FirstOrDefault(), o => o.Product);

And I know I keep showing this, but because of generic type inference, intellisense helps out as you write each lambda expression:

capture

I think that’s pretty cool.

Conclusion

I hope this post held your interest a little longer than the last one did. And I hope you can start to see uses for this sort of chained generic argument dependence in your APIs.

I’d be really interested if you’re already doing something like this or if you have a better name for this pattern. Let me know in the comments.

And finally, if this post was somehow unfulfilling and you still feel like you need to learn something cool, check out how to calculate square roots by hand!

Create a free website or blog at WordPress.com.