<html>
<head>
<title>Querying Trees in R - wondr</title>
<link rel="stylesheet" href="../style.css"/>
<link rel="stylesheet" href="../code_highlight.css"/>
<link rel="alternate" type="application/atom+xml" href="../atom.xml"/>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
</head>
<body class="page">
<div class="site">
<header id="header" class="header-container">
<div class="site-header">
<nav id="navmenu" aria-label="Main Menu">
<ul class="main-menu">
<li>
<a href=".." aria-current="page">Index</a>
</li>
</ul>
</nav>
<div class="site-info">
<h1 class="site-title title">Wondr</h1>
<p class="site-description">Wondering about R</p>
</div>
</div>
</header>
<main class="main">
<article lang="en" class="entry">
<header class="entry-header">
<div class="entry-info">
<h1 class="entry-title title">Querying Trees in R</h1>
</div>
<div class="meta">
<span class="posted-on">
<svg class="icon" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" aria-hidden="true">
<rect x="3" y="4" width="18" height="18" rx="2" ry="2"></rect>
<line x1="16" y1="2" x2="16" y2="6"></line>
<line x1="8" y1="2" x2="8" y2="6"></line>
<line x1="3" y1="10" x2="21" y2="10"></line>
</svg>
<span class="screen-reader">Posted on </span>
<time class="date" datetime="2018-08-06T00:00:00Z">2018-08-06</time>
</span>
<span class="reading-time">
<svg class="icon" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" aria-hidden="true">
<circle cx="12" cy="12" r="10"></circle>
<polyline points="12 6 12 12 15 15"></polyline>
</svg>
3 minute read
</span>
</div>
</header>
<div class="entry-content">
<p>R is <em>awesome</em> for working with tabular data. The language and its libraries together offer comprehensive support for querying, visualizing, and modifying data in the form of rows and columns.</p>
<p>Unfortunately, much data in the world is not tabular, and so not amenable to direct manipulation in R. JSON, one of today’s most popular interchange formats, is hierarchical or tree-like.</p>
<p>The JSONPath query language has been developed to facilitate querying JSON trees, and is accessible in R through the <a href="https://github.com/blmoore/rjsonpath">rjsonpath</a> library.</p>
<p>An alternative to using a purpose-built tree query language like JSONPath is to:</p>
<ol type="1">
<li>Parse the tree from JSON (such as with <a href="https://cran.r-project.org/web/packages/jsonlite/vignettes/json-aaquickstart.html">jsonlite</a>) into a tree of R objects.</li>
<li>Convert the tree to a table.</li>
<li>Work with it from there, in R, without hand-writing tree-walking code or resorting to a separate query language.</li>
</ol>
<h2 id="transforming">Transforming</h2>
<p>A tree can be represented as a table of paths. For example, the following structures have different affordances but are informationally equivalent:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb1-1"><a href="#cb1-1"></a><span class="co"># Tree</span></span>
<span id="cb1-2"><a href="#cb1-2"></a><span class="kw">list</span>(</span>
<span id="cb1-3"><a href="#cb1-3"></a> <span class="dt">people =</span> <span class="kw">list</span>(</span>
<span id="cb1-4"><a href="#cb1-4"></a> <span class="kw">list</span>(<span class="dt">name =</span> <span class="st">"Joe"</span>, <span class="dt">age =</span> <span class="dv">34</span>),</span>
<span id="cb1-5"><a href="#cb1-5"></a> <span class="kw">list</span>(<span class="dt">name =</span> <span class="st">"Lance"</span>, <span class="dt">age =</span> <span class="dv">46</span>),</span>
<span id="cb1-6"><a href="#cb1-6"></a> <span class="kw">list</span>(<span class="dt">name =</span> <span class="st">"Margaret"</span>)</span>
<span id="cb1-7"><a href="#cb1-7"></a> )</span>
<span id="cb1-8"><a href="#cb1-8"></a>)</span>
<span id="cb1-9"><a href="#cb1-9"></a></span>
<span id="cb1-10"><a href="#cb1-10"></a><span class="co"># Table</span></span>
<span id="cb1-11"><a href="#cb1-11"></a><span class="kw">list</span>(</span>
<span id="cb1-12"><a href="#cb1-12"></a> <span class="kw">list</span>(<span class="st">"people"</span>, <span class="dv">0</span>, <span class="st">"name"</span>, <span class="st">"Joe"</span>)</span>
<span id="cb1-13"><a href="#cb1-13"></a> <span class="kw">list</span>(<span class="st">"people"</span>, <span class="dv">0</span>, <span class="st">"age"</span>, <span class="dv">34</span>)</span>
<span id="cb1-14"><a href="#cb1-14"></a> <span class="kw">list</span>(<span class="st">"people"</span>, <span class="dv">1</span>, <span class="st">"name"</span>, <span class="st">"Lance"</span>)</span>
<span id="cb1-15"><a href="#cb1-15"></a> <span class="kw">list</span>(<span class="st">"people"</span>, <span class="dv">1</span>, <span class="st">"age"</span>, <span class="dv">46</span>)</span>
<span id="cb1-16"><a href="#cb1-16"></a> <span class="kw">list</span>(<span class="st">"people"</span>, <span class="dv">2</span>, <span class="st">"name"</span>, <span class="st">"Margaret"</span>)</span>
<span id="cb1-17"><a href="#cb1-17"></a>)</span></code></pre></div>
<p>The <code>tree_df</code> function below performs this transformation by walking the tree and recursively accumulating a list of paths, and then converting the list of paths to a dataframe with rows of uniform length:</p>
<div class="sourceCode" id="cb2"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb2-1"><a href="#cb2-1"></a><span class="co"># Returns a list of lists, each a path into the nested structure x. Each path</span></span>
<span id="cb2-2"><a href="#cb2-2"></a><span class="co"># ends with the value at the leaf.</span></span>
<span id="cb2-3"><a href="#cb2-3"></a>paths <-<span class="st"> </span><span class="cf">function</span>(parent, x) {</span>
<span id="cb2-4"><a href="#cb2-4"></a> paths_recurse <-<span class="st"> </span><span class="cf">function</span>(items) {</span>
<span id="cb2-5"><a href="#cb2-5"></a> <span class="kw">unlist</span>(</span>
<span id="cb2-6"><a href="#cb2-6"></a> <span class="kw">lapply</span>(items, <span class="cf">function</span>(item) {</span>
<span id="cb2-7"><a href="#cb2-7"></a> <span class="kw">paths</span>(<span class="kw">c</span>(parent, item), x[[item]])</span>
<span id="cb2-8"><a href="#cb2-8"></a> }),</span>
<span id="cb2-9"><a href="#cb2-9"></a> <span class="dt">recursive =</span> <span class="ot">FALSE</span></span>
<span id="cb2-10"><a href="#cb2-10"></a> )</span>
<span id="cb2-11"><a href="#cb2-11"></a> }</span>
<span id="cb2-12"><a href="#cb2-12"></a> <span class="cf">if</span> (<span class="kw">typeof</span>(x) <span class="op">==</span><span class="st"> "list"</span>) {</span>
<span id="cb2-13"><a href="#cb2-13"></a> <span class="cf">if</span> (<span class="kw">is.null</span>(<span class="kw">names</span>(x))) {</span>
<span id="cb2-14"><a href="#cb2-14"></a> <span class="co"># Unnamed list aka JSON array</span></span>
<span id="cb2-15"><a href="#cb2-15"></a> <span class="kw">paths_recurse</span>(<span class="kw">seq_along</span>(x))</span>
<span id="cb2-16"><a href="#cb2-16"></a> } <span class="cf">else</span> <span class="cf">if</span> (<span class="kw">length</span>(x) <span class="op">></span><span class="st"> </span><span class="dv">0</span>) {</span>
<span id="cb2-17"><a href="#cb2-17"></a> <span class="co"># Named list aka JSON object</span></span>
<span id="cb2-18"><a href="#cb2-18"></a> <span class="kw">paths_recurse</span>(<span class="kw">names</span>(x))</span>
<span id="cb2-19"><a href="#cb2-19"></a> }</span>
<span id="cb2-20"><a href="#cb2-20"></a> } <span class="cf">else</span> {</span>
<span id="cb2-21"><a href="#cb2-21"></a> <span class="co"># Leaf, return the path to the leaf and its value</span></span>
<span id="cb2-22"><a href="#cb2-22"></a> <span class="kw">list</span>(<span class="kw">c</span>(parent, x))</span>
<span id="cb2-23"><a href="#cb2-23"></a> }</span>
<span id="cb2-24"><a href="#cb2-24"></a>}</span>
<span id="cb2-25"><a href="#cb2-25"></a></span>
<span id="cb2-26"><a href="#cb2-26"></a><span class="co"># Returns a data frame where each row is a distinct path into a tree of lists,</span></span>
<span id="cb2-27"><a href="#cb2-27"></a><span class="co"># such as that produced by jsonlite::fromJSON. Useful for querying deeply-nested</span></span>
<span id="cb2-28"><a href="#cb2-28"></a><span class="co"># structures in a tabular fashion.</span></span>
<span id="cb2-29"><a href="#cb2-29"></a>tree_df <-<span class="st"> </span><span class="cf">function</span>(tree) {</span>
<span id="cb2-30"><a href="#cb2-30"></a> ps <-<span class="st"> </span><span class="kw">paths</span>(<span class="kw">list</span>(), tree)</span>
<span id="cb2-31"><a href="#cb2-31"></a></span>
<span id="cb2-32"><a href="#cb2-32"></a> <span class="co"># Ensure rows are all the same length, with NA for padding</span></span>
<span id="cb2-33"><a href="#cb2-33"></a> lengths <-<span class="st"> </span><span class="kw">vapply</span>(ps, length, <span class="kw">numeric</span>(<span class="dv">1</span>))</span>
<span id="cb2-34"><a href="#cb2-34"></a> longest <-<span class="st"> </span><span class="kw">max</span>(lengths)</span>
<span id="cb2-35"><a href="#cb2-35"></a> padded <-<span class="st"> </span><span class="kw">Map</span>(ps, lengths, <span class="dt">f =</span> <span class="cf">function</span>(path, len) {</span>
<span id="cb2-36"><a href="#cb2-36"></a> <span class="kw">append</span>(path, <span class="kw">rep</span>(<span class="ot">NA</span>, longest <span class="op">-</span><span class="st"> </span>len))</span>
<span id="cb2-37"><a href="#cb2-37"></a> })</span>
<span id="cb2-38"><a href="#cb2-38"></a></span>
<span id="cb2-39"><a href="#cb2-39"></a> <span class="kw">as.data.frame</span>(<span class="kw">do.call</span>(rbind, padded))</span>
<span id="cb2-40"><a href="#cb2-40"></a>}</span></code></pre></div>
<h2 id="querying">Querying</h2>
<p>With <code>tree_df</code> we can create a table from a tree:</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb3-1"><a href="#cb3-1"></a>tree <-<span class="st"> </span><span class="kw">list</span>(</span>
<span id="cb3-2"><a href="#cb3-2"></a> <span class="dt">people =</span> <span class="kw">list</span>(</span>
<span id="cb3-3"><a href="#cb3-3"></a> <span class="kw">list</span>(<span class="dt">name =</span> <span class="st">"Joe"</span>, <span class="dt">age =</span> <span class="dv">34</span>),</span>
<span id="cb3-4"><a href="#cb3-4"></a> <span class="kw">list</span>(<span class="dt">name =</span> <span class="st">"Lance"</span>, <span class="dt">age =</span> <span class="dv">46</span>),</span>
<span id="cb3-5"><a href="#cb3-5"></a> <span class="kw">list</span>(<span class="dt">name =</span> <span class="st">"Margaret"</span>)</span>
<span id="cb3-6"><a href="#cb3-6"></a> )</span>
<span id="cb3-7"><a href="#cb3-7"></a>)</span>
<span id="cb3-8"><a href="#cb3-8"></a> </span>
<span id="cb3-9"><a href="#cb3-9"></a>df <-<span class="st"> </span><span class="kw">tree_df</span>(tree)</span></code></pre></div>
<p>Now, as a dataframe, the structure can be queried path-wise using <code>subset</code>. However, because each column represents a depth, and the values at a particular depth are not necessarily the same type, it’s useful to have a helper function to suppress the warnings <code>subset</code> produces about this:</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb4-1"><a href="#cb4-1"></a>tree_subset <-<span class="st"> </span><span class="cf">function</span>(...) <span class="kw">suppressWarnings</span>(<span class="kw">subset</span>(...))</span></code></pre></div>
<p>Finally, we can write code to tell us everyone’s names:</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb5-1"><a href="#cb5-1"></a><span class="op">></span><span class="st"> </span><span class="kw">tree_subset</span>(df, V3 <span class="op">==</span><span class="st"> "name"</span>, V4)</span>
<span id="cb5-2"><a href="#cb5-2"></a> V4</span>
<span id="cb5-3"><a href="#cb5-3"></a><span class="dv">1</span> Joe</span>
<span id="cb5-4"><a href="#cb5-4"></a><span class="dv">3</span> Lance</span>
<span id="cb5-5"><a href="#cb5-5"></a><span class="dv">5</span> Margaret</span></code></pre></div>
<p>Or we could find all the ages under 40:</p>
<div class="sourceCode" id="cb6"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb6-1"><a href="#cb6-1"></a><span class="op">></span><span class="st"> </span><span class="kw">tree_subset</span>(df, V3 <span class="op">==</span><span class="st"> "age"</span> <span class="op">&</span><span class="st"> </span>V4 <span class="op"><</span><span class="st"> </span><span class="dv">40</span>, V4)</span>
<span id="cb6-2"><a href="#cb6-2"></a> V4</span>
<span id="cb6-3"><a href="#cb6-3"></a><span class="dv">2</span> <span class="dv">34</span></span></code></pre></div>
<h2 id="joining">Joining</h2>
<p>We can join query results in order to answer questions like “What are the names of people under 40?”</p>
<p>First we gather the “ids” of people in the graph as <code>people_ids</code>, and then we filter by it in a subsequent query using <code>%in%</code>.</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb7-1"><a href="#cb7-1"></a>people_ids <-<span class="st"> </span><span class="kw">tree_subset</span>(df, V3 <span class="op">==</span><span class="st"> "age"</span> <span class="op">&</span><span class="st"> </span>V4 <span class="op"><</span><span class="st"> </span><span class="dv">40</span>)</span>
<span id="cb7-2"><a href="#cb7-2"></a><span class="kw">tree_subset</span>(df, V2 <span class="op">%in%</span><span class="st"> </span>people_ids <span class="op">&</span><span class="st"> </span>V3 <span class="op">==</span><span class="st"> "name"</span>)<span class="op">$</span>V4</span></code></pre></div>
<h2 id="summary">Summary</h2>
<p>Transforming trees into tables provides a way to use R like a path query language. The conversion requires walking the tree and storing it in memory as a table, and so may not be suitable for large trees. For small trees, however, the computation time is negligible and the programmer is able to write clear R code for querying the structure without explicitly walking the tree or admitting a separate query language.</p>
<blockquote>
<p>Many thanks to <a href="http://schloerke.com/">Barret Schloerke</a> for reviewing this post and suggesting improvements.</p>
</blockquote>
</div>
</article>
<article data-sblg-article="1" class="entry-content"></article>
</main>
<footer id="footer" class="footer-container">
<div class="footer">
<div class="social">
<nav aria-label="Social Menu">
<ul class="social-menu"><li>
<a href="mailto:alan@tailrecursion.com" >
<span class="screen-reader">Send E-mail</span>
<svg class="icon" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" aria-hidden="true">
<path d="M4 4h16c1.1 0 2 .9 2 2v12c0 1.1-.9 2-2 2H4c-1.1 0-2-.9-2-2V6c0-1.1.9-2 2-2z"></path>
<polyline points="22,6 12,13 2,6"></polyline>
</svg>
</a>
</li><li>
<a href="https://github.com/alandipert/wondr-blog" >
<span class="screen-reader">Open Github account</span>
<svg class="icon" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" aria-hidden="true">
<path d="M9 19c-5 1.5-5-2.5-7-3m14 6v-3.87a3.37 3.37 0 0 0-.94-2.61c3.14-.35 6.44-1.54 6.44-7A5.44 5.44 0 0 0 20 4.77 5.07 5.07 0 0 0 19.91 1S18.73.65 16 2.48a13.38 13.38 0 0 0-7 0C6.27.65 5.09 1 5.09 1A5.07 5.07 0 0 0 5 4.77a5.44 5.44 0 0 0-1.5 3.78c0 5.42 3.3 6.61 6.44 7A3.37 3.37 0 0 0 9 18.13V22"></path>
</svg>
</a>
</li>
<li>
<a href='https://twitter.com/alandipert' target='_blank' rel='noopener'>
<span class='screen-reader'>Open Twitter account in new tab</span><svg class='icon' viewbox='0 0 24 24' stroke-linecap='round' stroke-linejoin='round' stroke-width='2' aria-hidden='true'>
<path d="M23 3a10.9 10.9 0 0 1-3.14 1.53 4.48 4.48 0 0 0-7.86 3v1A10.66 10.66 0 0 1 3 4s-4 9 5 13a11.64 11.64 0 0 1-7 2c9 5 20 0 20-11.5a4.5 4.5 0 0 0-.08-.83A7.72 7.72 0 0 0 23 3z"/>
</svg>
</a>
</li>
</ul>
</nav>
</div>
</div>
</footer>
</div>
</body>
</html>