Expression Bodied Collection Property Initialization Gotcha in C#

Broken Post? → Let me know

I was implementing a trie, which is a tree data structure, usually for storing strings for searching. Since it's a tree, it has a "Children" for holding child nodes.

But then I ran into a problem where simply calls to adding children to a collection (Line# 9) didn't work.

      
        private void Insert(TrieNode current, string word) 
      
        { 
      
        	foreach (char c in word) 
      
        	{ 
      
        		current.Children.TryGetValue(c, out TrieNode node); 
      
        		if (node == null) 
      
        		{ 
      
        			node = new TrieNode(); 
      
        			current.Children.Add(c, node); 
      
        		} 
      
        		current = node; 
      
        	} 
      
        	current.IsCompleteWord = true; 
      
        }

view raw insert.cs hosted with ❤ by GitHub

After 30 minutes of debugging, I was like...

Just what the hl happened?

TL;DR

Auto Property initialization creates a backing field while Expression Bodied property one does not

▬ Introduction ▬

According to Wikpedia, you can declare a trie like this (in Haskell).

      
        import Data.Map
      
        data Trie a = Trie { value    :: Maybe a,
      
                             children :: Map Char (Trie a) }

view raw Trie.hs hosted with ❤ by GitHub

So I created a TrieNode class as shown below.

      
        public class TrieNode 
      
        { 
      
        	public bool IsCompleteWord { get; set; } = false; 
      
        	public Dictionary<char, TrieNode> Children => new Dictionary<char, TrieNode>(); 
      
        }

view raw TrieNode.cs hosted with ❤ by GitHub

If you are an astute reader, you might have already spotted the problem. Congratulations!

▬ Problem ▬

The complete source for building a trie, TrieBuilder is declared as below.

      
        public class TrieBuilder 
      
        { 
      
        	public TrieNode BuildTrie(IEnumerable<string> words) 
      
        	{ 
      
        		TrieNode root = new TrieNode(); 
      
        		foreach (var word in words) 
      
        		{ 
      
        			Insert(root, word); 
      
        		} 
      
        		return root; 
      
        	} 
      
        	private void Insert(TrieNode current, string word) 
      
        	{ 
      
        		foreach (char c in word) 
      
        		{ 
      
        			current.Children.TryGetValue(c, out TrieNode node); 
      
        			if (node == null) 
      
        			{ 
      
        				node = new TrieNode(); 
      
        				current.Children.Add(c, node); 
      
        			} 
      
        			current = node; 
      
        		} 
      
        		current.IsCompleteWord = true; 
      
        	} 
      
        }

view raw TrieBuilder.cs hosted with ❤ by GitHub

Given a list of words passed to BuildTrie method, it populates a trie and returns an object instance.

Insert method simply checks for an existence of a character and maps current character to a node to the trie object instance , current.

This is where the problem occurred. current.Children.Add(...) wasn't adding node object instance.

▬ Investigation ▬

Later on, I found out a StackOverflow answer explanating that declaring a property with => syntax (introduced in C# 6) does NOT create a backing field.

So my declaration below,

public Dictionary<char, TrieNode> Children => new Dictionary<char, TrieNode>();

view raw Children1.cs hosted with ❤ by GitHub

is equivalent to

      
        public Dictionary<char, TrieNode> Children
      
        {
      
        	get { return new Dictionary<char, TrieNode>(); }
      
        }

view raw Children2.cs hosted with ❤ by GitHub

returning a new array whenever Children property was accessed, thus not adding a new node to it.

▬ Solution ▬

The fix is simple. Declare Children with a backing field or use an auto property initialization syntax.

      
        public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>();

view raw Children3.cs hosted with ❤ by GitHub

Above declaration is equivalent to

      
        private readonly Dictionary<char, TrieNode> _children = new Dictionary<char, TrieNode>(); 
      
        public Dictionary<char, TrieNode> Children 
      
        { 
      
        	get { return _children; } 
      
        }

view raw Children4.cs hosted with ❤ by GitHub

That was all it took to make me a happy camper ?.

▬ Takeaway ▬

Auto Property initialization creates a backing field while Expression Bodied property one does not.

	import Data.Map

	data Trie a = Trie { value :: Maybe a,
	children :: Map Char (Trie a) }

	public class TrieNode
	{
	public bool IsCompleteWord { get; set; } = false;

	public Dictionary<char, TrieNode> Children => new Dictionary<char, TrieNode>();
	}

	public class TrieBuilder
	{
	public TrieNode BuildTrie(IEnumerable<string> words)
	{
	TrieNode root = new TrieNode();
	foreach (var word in words)
	{
	Insert(root, word);
	}

	return root;
	}

	private void Insert(TrieNode current, string word)
	{
	foreach (char c in word)
	{
	current.Children.TryGetValue(c, out TrieNode node);
	if (node == null)
	{
	node = new TrieNode();
	current.Children.Add(c, node);
	}
	current = node;
	}

	current.IsCompleteWord = true;
	}
	}

	public Dictionary<char, TrieNode> Children
	{
	get { return new Dictionary<char, TrieNode>(); }
	}

	private readonly Dictionary<char, TrieNode> _children = new Dictionary<char, TrieNode>();
	public Dictionary<char, TrieNode> Children
	{
	get { return _children; }
	}