Jacob Carpenter’s Weblog

April 23, 2008

C# abuse of the day: SwitchOnType

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

Today I encountered a situation where I wanted to switch based on a type. Maybe I stayed up a little too late reading Foundations of F#, last night.

While this is certainly no pattern matching, it didn’t seem like terrible C#:

DefinitionBase definitionBase = /*...*/;

var targetProperty = definitionBase.SwitchOnType(
        (ColumnDefinition col) => ColumnDefinition.WidthProperty,
        (RowDefinition row) => RowDefinition.HeightProperty);

Note that the lambdas require type decoration (you really don’t want to explicitly declare the generic parameters on this method).

Here’s the implementation (taking two Func projections—feel free to overload to your heart’s content):

public static TResult SwitchOnType<T, T1, T2, TResult>(this T source,
    Func<T1, TResult> act1, Func<T2, TResult> act2)
{
    if (source is T1)
        return act1((T1) source);

    if (source is T2)
        return act2((T2) source);

    throw new InvalidOperationException("No matching delegate found");
}

As you can see from the implementation, the method returns the result of the first delegate for which source can be converted into a parameter.

For a default case, add a final delegate that takes object.

Advertisements

April 16, 2008

PC#1: A solution

Filed under: challenge, csharp, extension methods, LINQ — Jacob @ 12:21 pm

So, when I initially posed the programming challenge #1 I stated:

… since I intended to output HTML, ASP.NET seemed a logical choice. But I was amazed at the amount of code required for such a seemingly simple task (not to mention how ugly code containing <% and %> is!).

Well, it turns out, using plain old C# with a little LINQ to XML functional construction made my solution a lot nicer.

Prerequisites

I created a few DateTimeExtensions to enhance readability, though I could have easily inlined the implementation of each of those methods without any LOC impact.

public static class DateTimeExtensions
{
    public static DateTime ToFirstDayOfMonth(this DateTime dt)
    {
        return new DateTime(dt.Year, dt.Month, 1);
    }
    public static DateTime ToLastDayOfMonth(this DateTime dt)
    {
        return new DateTime(dt.Year, dt.Month, DateTime.DaysInMonth(dt.Year, dt.Month));
    }
    public static DateTime ToFirstDayOfWeek(this DateTime dt)
    {
        return dt.AddDays(-((int) dt.DayOfWeek));
    }
    public static DateTime ToLastDayOfWeek(this DateTime dt)
    {
        return dt.AddDays(6 - ((int) dt.DayOfWeek));
    }
}

I also relied on the Slice extension method I’ve previously blogged about.

Solution

static void Main(string[] args)
{
    DateTime today = DateTime.Today;
    DateTime firstDayOfMonth = today.ToFirstDayOfMonth();
    DateTime startCalendar = firstDayOfMonth.ToFirstDayOfWeek();
    DateTime lastDayOfMonth = today.ToLastDayOfMonth();
    DateTime endCalendar = lastDayOfMonth.ToLastDayOfWeek();

    var calendarPrefix =
        from day in Enumerable.Range(startCalendar.Day, (firstDayOfMonth - startCalendar).Days)
        select new XElement("td", new XAttribute("class", "prevMonth"), day);
    var calendarMonth =
        from day in Enumerable.Range(1, lastDayOfMonth.Day)
        select new XElement("td", day == today.Day ? new XAttribute("class", "today") : null, day);
    var calendarSuffix =
        from day in Enumerable.Range(1, (endCalendar - lastDayOfMonth).Days)
        select new XElement("td", new XAttribute("class", "nextMonth"), day);

    var calendar = calendarPrefix.Concat(calendarMonth).Concat(calendarSuffix);

    var table = new XElement("table",
        new XElement("thead",
            new XElement("tr",
                from offset in Enumerable.Range(0, 7)
                select new XElement("th", startCalendar.AddDays(offset).ToString("ddd")))),
        new XElement("tbody",
            from week in calendar.Slice(7)
            select new XElement("tr", week)));

    Console.WriteLine(table);
}

I’d love to see more ways to solve this. If you’ve got a simpler or more beautiful implementation in your favorite programming langauge/web application framework, let me know in the comments of the original post.

April 15, 2008

Programming Challenge #1: HTML calendar

Filed under: challenge, web — Jacob @ 1:44 pm

While playing around at lunchtime today, I decided to write a quick little HTML calendar generator.

I consider C# my native programming language, and since I intended to output HTML, ASP.NET seemed a logical choice. But I was amazed at the amount of code required for such a seemingly simple task (not to mention how ugly code containing <% and %> is!).

The challenge

Using your favorite programming language / web application framework output the following html fragment:

<table class="calendar">
<thead>
<tr><th>Sun</th><th>Mon</th><th>Tue</th><th>Wed</th><th>Thu</th><th>Fri</th><th>Sat</th></tr>
</thead>
<tbody>
<tr><td class="prevMonth">30</td><td class="prevMonth">31</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr>
<tr><td>6</td><td>7</td><td class="today">8</td><td>9</td><td>10</td><td>11</td><td>12</td></tr>
<tr><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td><td>18</td><td>19</td></tr>
<tr><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td></tr>
<tr><td>27</td><td>28</td><td>29</td><td>30</td><td class="nextMonth">1</td><td class="nextMonth">2</td><td class="nextMonth">3</td></tr>
</tbody>
</table>

Whitespace is insignificant; class="today" should be applied to the current day’s cell; favor simplicity and elegance over efficiency.

Blog your solution and leave a comment; I’ll link to it from this post.

Please don’t comment suggesting I use some pre-built control. This is about the fun of writing such a thing, not about some specific calendaring need.

To avoid influencing your initial attempt, I’ll post my solution after awhile.

UPDATE:

Will Asrari contributed a submission at http://www.willasrari.com/blog/coding-for-fun—html-calendar-challenge/000298.aspx.

I posted my solution at https://jacobcarpenter.wordpress.com/2008/04/16/pc1-a-solution/.

kick it on DotNetKicks.com

April 4, 2008

Euler 14

Filed under: csharp, Euler, extension methods, LINQ, Ruby — Jacob @ 12:41 pm

When I read Dustin Campbell’s latest post, I couldn’t help but feel a bit like Steve Carrell in this clip from the Office. While his solution is an admirably close port of the original F# solution, it makes me feel a little bit yucky.

Of course, it’s completely hypocritical of me to say so, since I’ve abused C# to make it exhibit F#-like behavior in the past.

But Project Euler invites elegantly simple solutions (like the original F#). Different languages have different idioms, and a literal port typically doesn’t exhibit the same beauty as the original.

If I was solving project Euler 14 in C# (with “elegance and brevity in mind”), my code would look more like:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Euler14
{
    class Program
    {
        static void Main(string[] args)
        {
            var iterativeSequences = from start in 1.To(1000000L)
                select new
                {
                    Start = start,
                    Length = SequenceUtility.Generate(start,
                        n => n % 2 == 0 ? n / 2 : 3 * n + 1,
                        n => n == 1).Count()
                };

            Stopwatch sw = Stopwatch.StartNew();

            var longestSequence = iterativeSequences.Aggregate(
                (longest, current) => current.Length > longest.Length ? current : longest
            );

            sw.Stop();

            Console.WriteLine("Longest sequence starts with {0:#,#} (found in {1:#,#.000} seconds)",
                longestSequence.Start, (float) sw.ElapsedTicks / (float) Stopwatch.Frequency);
        }
    }

    public static class SequenceUtility
    {
        // Can also overload To by changing the end value's type;
        // example: "int excludedEnd" returns "IEnumerable<int>"
        public static IEnumerable<long> To(this int start, long excludedEnd)
        {
            for (long i = start; i < excludedEnd; i++)
                yield return i;
        }

        public static IEnumerable<T> Generate<T>(T first, Func<T, T> getNext, Func<T, bool> isLast)
        {
            T value = first;
            yield return value;

            while (!isLast(value))
            {
                value = getNext(value);
                yield return value;
            }
        }
    }
}

Which runs in an acceptable ~5 seconds on my machine.

[Okay. You caught me: I stole the idea for that To extension method from Ruby’s upto. I’m a huge hypocrite and take back everything I said before.

Do invest time learning the idoms of other programming languages, and try applying them to your native language. You may discover something beautiful, after all.]

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. 🙂

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!

February 20, 2008

Generic abuse: Pattern matching in C#

Filed under: csharp — Jacob @ 1:59 pm

Sorry it’s been so long since a post, dear faithful aggregator. Apart from working, I’ve been busily readying my entry for the WPF in Finance contest (which, coincidentally has inspired a potential post or two).

Yesterday, however, I encountered Dustin’s post on pattern matching in F#. Go read it; I’m not going to reiterate the concepts, and you need to be familiar with the feature for this post to possibly begin to make any sense.

His post inspired the most creative (perhaps twisted) use of generics I’ve ever written. And I have to share.

A couple of caveats though: pattern matching is built into F#. It is therefore much, much cooler than the following experiment. Please don’t comment telling me that mine is lamer than F#’s.

Also, I’m usually morally opposed to screenshots of code (rather than the actual code, itself), but I need to visually highlight some stuff to help explain it. I’ve attached the full source at the bottom of the post.

Intro

If I were writing a pattern matching API in C#, one of my first thoughts would be “fluent interface“. At it’s simplest, pattern matching needs to support:

  1. Some variable number of guard clauses (only at the beginning of the pattern match).
  2. Some variable number of pattern expressions (a predicate of some sort and an associated action).
  3. A single final catch-all expression (action only).

Fluent interfaces can represent this type of constrained chaining pretty nicely. In fact, LINQ sort of supports constrained chaining with OrderBy/ThenBy. OrderBy returns an IOrderedEnumerable, which supports ThenBy (via extension). You can’t call ThenBy on an ordinary IEnumerable; you have to call OrderBy first.

The problem with fluent interfaces for solving this problem, though, is that successive method calls don’t really feel like adding expressions to a pattern match:

image

Note that it’s only whitespace (which the compiler ignores) that communicates that .When(…).Return(…) adds one expression, whereas .Guard(…) and the last .Return(…) each correspond to a single expression.

Also, we haven’t looked at the object model yet, but note that a final call to .Compile is required to transform whatever type the last .Return returns into a Func<int, int>. I hate that.

There are other options. We could write a method that took a params array of loosely typed pattern expressions. But we would sacrifice compile-time expression order constraint.

My crazy solution

Through numerous rewrites and after going around in circles for some time, I decided on the following pattern:

  1. Define an object model of “match contexts” that (similar to LINQ’s OrderBy/ThenBy) return strongly typed contexts defining what operations are supported from the current context.
  2. In my pattern match building method, use Funcs and generics (with type constraints) to allow the strongly typed contexts to flow from parameter to parameter.

Let’s look at the object model:

public abstract class ClosedMatchContext<T, TResult>
{
}

public abstract class MatchContext<T, TResult> : ClosedMatchContext<T, TResult>
{
    public abstract IntermediateMatchResultContext<T, TResult> When(Func<T, bool> condition);
    public abstract ClosedMatchContext<T, TResult> Return(TResult result);
    public abstract ClosedMatchContext<T, TResult> Return(Func<T, TResult> resultProjection);
}

public abstract class OpenMatchContext<T, TResult> : MatchContext<T, TResult>
{
    public abstract OpenMatchContext<T, TResult> Guard(Func<T, bool> failWhen, Func<T, TResult> failWith);
}

public abstract class IntermediateMatchResultContext<T, TResult>
{
    public abstract MatchContext<T, TResult> Return(TResult result);
    public abstract MatchContext<T, TResult> Return(Func<T, TResult> resultProjection);
}

Beginning with OpenMatchContext, we have a context that supports: Guard, When, and Return operations. Moving up the hierarchy, the more general MatchContext supports only When and Return. Finally at the top level, ClosedMatchContext doesn’t support any further operations.

When, defined on MatchContext, returns an IntermediateMatchResultContext which requires a call to Return to get back to a MatchContext.

Now it’s getting interesting…

Or perhaps, difficult to understand?

public static class Match<T, TResult>

… defines a number of On methods that take series of Func arguments. Let’s look at the signature of the 4 parameter one:

image

Now take a deep breath.

The first parameter is a Func<OpenMatchContext, TCtx1>. An open context comes in and some MatchContext (according to the constraint) comes out.

The second parameter takes a Func<TCtx1, TCtx2>. The context returned by the first parameter is given to the second parameter, and some new MatchContext comes out. The third parameter is very similar.

Finally, the last parameter takes a Func<TCtx3, ClosedMatchContext>. That is, we expect to get some closed context as the final output.

Let’s see if a little highlighting can help?

image

My graphic design skillz could use some work, but do you follow the flow of the types?

This means that when you’re using On the parameters are strongly typed:

image

Following a Guard expression, you can add an additional Guard. But…

image

Following a When+Return, you can no longer Guard.

There’s more interesting type stuff going on in this example, but I’ll have to discuss it in a following post.

I hope reading this has produced a pleasantly painful sensation. If not, go read Wes Dyer’s post on Monads.

Source listing

I’ve attached the source to this post, but I have to lie about the extension. Rename the attached Program.cs.REMOVE.DOC to Program.cs.

UPDATE: I’ve made the source more accessible by simply including it after the “more” link.

I’d encourage you to copy it into a ConsoleApplication’s Program.cs and play around with it. Let me know what you think.

Enjoy!

(more…)

February 4, 2008

DispsoseAfter

Filed under: csharp, extension methods — Jacob @ 9:17 am

My development team at work has recently started a technical blog: http://code.logos.com.

I just contributed my first (real) post: DisposeAfter.

Enjoy.

January 28, 2008

Windows Live Writer Plugin: Element tag around

Filed under: Uncategorized — Jacob @ 10:01 pm

Over the weekend, I met Joe Cheng from the Windows Live Writer team. After asking him about the ease (or potential lack thereof) of plugin authoring, he walked me through a couple of scenarios.

It turns out authoring Live Writer plugins is as easy as using the app itself. Pretty remarkable considering the app is designed to be simple enough that my mom could use it (though I did have trouble locating some simple documentation to compellingly illustrate that fact). No offense, mom.

Joe’s demonstration culminated with showing off his powerful Dynamic Template plugin. He’s even shared the source at CodePlex.

However, not being content to use what’s available (and because it was so ridiculously easy), I decided to write my own plugin:

Element tag around

In the textual discussion of code-type stuff, I’m fond of marking up keywords / class names / local variables / etc. with the html code element. See, I just did it.

I wanted a plugin to simplify adding those elements. I wanted it to be fast to use [keyboard shortcuts]. Also, I know there are all these additional HTML computer code phrase elements, but it’s too inconvenient to remember what they are.

Enter Element tag around:

image

image

The most time consuming part of creating the plugin—which took a whopping lunch break—was the layout of the elements on the dialog. Coming from a WPF mindset, dynamically laying out elements in Windows Forms sucks.

As you can see from the screenshot, the available elements are all clearly listed and are insertable via keyboard shortcut (or by simply clicking the associated LinkLabel).

And yes, that was a gratuitous use of my new plugin.

Enjoy.

« Newer PostsOlder Posts »

Blog at WordPress.com.