Intersection of 3 sets

Let’s say we have a bunch of CSV files and we want to find all the common columns between these files.

We are goint to use the following data for testing:

let headersByFile = seq{
    yield [ "id"; "name"; "date"; "color" ]
    yield [ "id"; "age"; "date" ]
    yield [ "id"; "sex"; "date"; "animal" ]
}
// val headersByFile : seq<string list>

And we want to have as result:

[ "id"; "date" ]

As the Intersection operation is associative:

(A ∩ B) ∩ C = A ∩ (B ∩ C)

We can compute the intersection of the first list and the second list and then use the result to compute the intersection with the third list and so on.

That sounds like a familiar high order function: Seq.reduce.

In F# we don’t have a built-in function to compute the intersection of two lists or sequences — as we do in C# with Enumerable.Intersect — but we do have an intersection function in the Set module to work with sets, so we will use it.

First we need to transform our sequence of lists in a sequence of sets (working directly with our data):

let headersByFileSet = Seq.map Set.ofList headersByFile
// val headersByFileSet : seq<Set<string>>

We have now a sequence of sets in which we can apply a ‘reduction’ using the Set.intersect function.

let commonHeaders = Seq.reduce Set.intersect headersByFileSet 
// val commonHeaders : Set<string> = set ["date"; "id"]

And that is all!

A way to gather all this together is using the ‘pipeline‘ operator:

let commonHeaders = 
      headersByFile
      |> Seq.map Set.ofList
      |> Seq.reduce Set.intersect
// val commonHeaders : Set<string> = set ["date"; "id"]

Or making even a generic function using ‘function composition‘ and ‘function partial application‘:

let commonIntersection = Seq.map Set.ofList >> Seq.reduce Set.intersect
// val commonIntersection : (seq<string list> -> Set<string>)

let commonHeaders = commonIntersection  headersByFileSet 
// val commonHeaders : Set<string> = set ["date"; "id"]

[Update]
There is built-in function in the Set module to calculate directly the common intersection of a sequence of sets: Set.intersectMany, so we only need to transform our sequence of lists to a sequence of sets.

let commonHeaders = 
      headersByFile
      |> Seq.map Set.ofList
      |> Set.intersectMany
// val commonHeaders : Set<string> = set ["date"; "id"]

We would like to display the data as follow:

Hierarchical display data

But when it comes to display the raw data it is hard to identify the hierarchical form.

Not hierarchical display

Let’s build a very simple data model for the sake of example.

Create table Tree(
	nodeId int not null primary key,
	parentNodeId int null foreign key references Tree(nodeId),
	name nvarchar(max)
)

And insert some data.

insert into Tree values
(1, null, 'Root A'),
	(2, 1, 'Child A1'),
		(3, 2, 'Child A11'),
		(4, 2, 'Child A12'),
	(5, 1, 'Child A2'),
		(6, 5, 'Child A21'),
			(7, 6, 'Child A211'),
			(8, 6, 'Child A212'),
		(9, 5, 'Child A22'),
(10, null, 'Root B'),
(11, null, 'Root C'),
	(12, 11, 'Child C1'),
		(13, 12, 'Child C11'),
		(14, 12, 'Child C12'),
	(15, 11, 'Child C2')

Let’s use a Common Table Expression (CTE):

;with orderedTree (name, nodeId, depth, location)
as
(
	select 
		name,
		nodeId,  
		0 as depth,
		CAST(nodeId AS nvarchar(max)) AS location
	from tree 
	where parentNodeId is null

	union all

	select 
		cast(concat(space(parent.depth * 5), '|__', child.name) as nvarchar(max)), 
		child.nodeId, 
		parent.depth + 1,
		cast(concat(parent.location, '.' ,child.nodeId) AS nvarchar(max)) AS location
	from tree child
	inner join orderedTree parent
		on child.parentNodeId = parent.nodeId

)

select * from orderedTree
order by location

Now we can easily see the hierarchical structure of our data.

Let’s say we have a main form that displays another form as a Modal dialog to finally display some information from that form.

Choose favorite pet form

public partial class ChoosePetDialogForm : Form
{
    public string ChosenPet { get; private set; }

    public ChoosePetDialogForm()
    {
        InitializeComponent();
        ChosenPet = "Nothing";
    }

    private void choosePetButton_Click(object sender, EventArgs e)
    {
        var petRadioChecked = this.petListGroup
                                    .Controls
                                    .OfType<RadioButton>()
                                    .FirstOrDefault(r => r.Checked);
        if (petRadioChecked != null)
        {
            ChosenPet = petRadioChecked.Text;
        }
    }
}

The choosePetButton is associated to a DialogResult of value DialogResult.OK:

Button Dialog Result

That makes the ChoosePetDialogForm “return” the value DialogResult.OK when called as a Dialog Box when the choosePetButton is clicked.

And the code for the caller form:

public partial class PetTestForm : Form
{
    public PetTestForm()
    {
        InitializeComponent();
    }

    private void takeTestButton_Click(object sender, EventArgs e)
    {
        ChoosePetDialogForm dialog = new ChoosePetDialogForm();
        if (dialog.ShowDialog() == DialogResult.OK)
        {
            MessageBox.Show(dialog.ChosenPet, "Pet Chosen:");
        }
    }
}

Let’s say now that I want to make some validation before the Modal Dialog form closes, for example allow only “platypus” as favorite pet. How can I make the modal dialog to continue running after clicking a button?

if (!radioButtonPlatypus.Checked)
{
    // avoid the modal dialog to close
}

Well, as explained on the DialogResult Enumeration documentation, we simply need to set the DialogResult property value of the Modal form to DialogResult.None.

if (!radioButtonPlatypus.Checked)
{
    // avoid the modal dialog to close
    this.DialogResult = DialogResult.None;
    MessageBox.Show("Wrong pet! Try again.");
}

This way the Modal form will not close.

I was working on an application when suddenly I stepped into a method that intrigued me.

public static string NameFormatter(string name)
{
    if (!String.IsNullOrEmpty(name))
    {
        int index = 1;
        char[] separator = new[] { ' ', '-', '_', '.', '\'' };
        name = name.Substring(0, 1).ToUpper() + name.Substring(1);
        while ((index = name.IndexOfAny(separator, index)) > 0)
        {
            index++;
            if (name.Length > index + 1)
            {
                name = name.Replace(
                                name.Substring(index, 1),
                                name.Substring(index, 1).ToUpper());
            }
        }
    }
    return name;
}

This code has no comments and it has been in production since years, at least the method’s name gives a hint of its intention, this method is meant to format a string (like a name) replacing the first character after a given separator character (' ', '-', '_', '.', '\'') by its upper case form.

Let’s a make a test:

string[] names = {
                    "john f. smith",
                    "sandra tayllor-murray",
                    "miguel d'angelo",
                    "pablo fernandez duran"
                    };

foreach (string name in names)
{
    Console.WriteLine(NameFormatter(name));
}

// output:
//     John F. Smith
//     Sandra Tayllor-Murray
//     Miguel D'Angelo
//     Pablo FernanDez Duran

It seems to work. Wait! I don’t really like how this application displays my last name (FernanDez). Leaving aside some algorithmic issues, let’s find the source of the problem. The incriminated line of code is:

name = name.Replace(
                name.Substring(index, 1),
                name.Substring(index, 1).ToUpper());

Let’s say name.Substring(index, 1) = "d".
We have: name = name.Replace("d", "d".ToUpper()). Not only the character “d” at the index position is replaced but all the occurrences of “d” in the string are replaced.

Fixing the code

Let’s fix that:

name =  name.Substring(0, index)
        + name.Substring(index, 1).ToUpper()
        + name.Substring(index + 1);

// name = name.Replace(
//                 name.Substring(index, 1),
//                 name.Substring(index, 1).ToUpper());

Now the output is:

// John F. Smith
// Sandra Tayllor-Murray
// Miguel D'Angelo
// Pablo Fernandez Duran

Using the TextInfo.ToTitleCase method

That’s better, but I’m not still happy about this code, a lot of noise, difficult to maintain, the main intention of the algorithm it’s hidden in its implementation and so on. Before trying to rewrite the method let’s see if there is something in the .NET framework that can be useful. We have the TextInfo.ToTitleCase Method.

Let’s make a test:

string[] names = {
                    "john f. smith",
                    "sandra tayllor-murray",
                    "miguel d'angelo",
                    "pablo fernandez duran"
                    };
TextInfo textInfo = new CultureInfo("en-US", false).TextInfo;
foreach (string name in names)
{
    Console.WriteLine(textInfo.ToTitleCase(name));
}

// output:
//    John F. Smith
//    Sandra Tayllor-Murray
//    Miguel D'angelo
//    Pablo Fernandez Duran

Almost there! now Miguel wouldn’t like how the application displays his name (I don’t really know any Miguel D’Angelo).

I tried with other cultures but I didn’t see any difference (and I would like to know if there is a difference between different cultures).

Using Regular Expressions

What to do now? Let’s use a regex.

public static string NameFormatter(string name)
{
    if (!String.IsNullOrEmpty(name))
    {
        return Regex.Replace(
                         name,
                         @"\b[a-zA-Z]",
                         m => m.Value.ToUpper());
    }
    return name;
}
// output:
//    John F. Smith
//    Sandra Tayllor-Murray
//    Miguel D'Angelo
//    Pablo Fernandez Duran

Great! \b[a-zA-Z] will find all characters between a to z and A to Z just after a word boundary (\b). More information about Regex.Replace here.

One case is not covered with this regex: characters following a ‘_’ (underscore). That is because the word boundary \b by definition considers as word characters the “character class” \w, and \w is the short hand for [A-Za-z0-9_] .

Let’s tune our regex to the handle the _ character as a separator: (?<=\b|_)[a-zA-Z].

Bonus

To handle names like mcfry or macdonald’s we can use:
(?<=\b(?:mc|mac)?|_)[a-zA-Z](?<!'s\b)

• john f. smith
• sandra tayllor-murray
• miguel d’angelo
• pablo fernandez duran
• mcfry
• macdonald’s

Will give:

• John F. Smith
• Sandra Tayllor-Murray
• Miguel D’Angelo
• Pablo Fernandez Duran
• McFry
• MacDonald’s

The final code is:

public static string NameFormatter(string name)
{
    if (!String.IsNullOrEmpty(name))
    {
        return Regex.Replace(
                         name,
                         @"(?<=\b(?:mc|mac)?|_)[a-zA-Z](?<!'s\b)",
                         m => m.Value.ToUpper());
    }
    return name;
}

Finally

We need to do some extra work on the regex if we want to match an extended range of characters like diacritics (accents), take a look at the Character classes in regex reference on the smdn or here. You can use this set to match also accents:
[a-zA-ZÀ-ÿ].

Warning

Formatting names is a delicate question, it may depend on cultures and languages. The name is the identity of a person and people may no like that an application tells them how to write their name. So maybe the best way to format a name is to leave it as typed by the user.