-
Notifications
You must be signed in to change notification settings - Fork 0
/
associative-data.html
203 lines (203 loc) · 15.1 KB
/
associative-data.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>associative-data</title>
<style type="text/css">
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
</style>
<style type="text/css">
a.sourceLine { display: inline-block; line-height: 1.25; }
a.sourceLine { pointer-events: none; color: inherit; text-decoration: inherit; }
a.sourceLine:empty { height: 1.2em; }
.sourceCode { overflow: visible; }
code.sourceCode { white-space: pre; position: relative; }
div.sourceCode { margin: 1em 0; }
pre.sourceCode { margin: 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
code.sourceCode { white-space: pre-wrap; }
a.sourceLine { text-indent: -1em; padding-left: 1em; }
}
pre.numberSource a.sourceLine
{ position: relative; left: -4em; }
pre.numberSource a.sourceLine::before
{ content: attr(title);
position: relative; left: -1em; text-align: right; vertical-align: baseline;
border: none; pointer-events: all; display: inline-block;
-webkit-touch-callout: none; -webkit-user-select: none;
-khtml-user-select: none; -moz-user-select: none;
-ms-user-select: none; user-select: none;
padding: 0 4px; width: 4em;
background-color: #2a211c;
color: #bdae9d;
}
pre.numberSource { margin-left: 3em; border-left: 1px solid #bdae9d; padding-left: 4px; }
div.sourceCode
{ color: #bdae9d; background-color: #2a211c; }
@media screen {
a.sourceLine::before { text-decoration: underline; }
}
code span.al { color: #ffff00; } /* Alert */
code span.an { color: #0066ff; font-weight: bold; font-style: italic; } /* Annotation */
code span.at { } /* Attribute */
code span.bn { color: #44aa43; } /* BaseN */
code span.bu { } /* BuiltIn */
code span.cf { color: #43a8ed; font-weight: bold; } /* ControlFlow */
code span.ch { color: #049b0a; } /* Char */
code span.cn { } /* Constant */
code span.co { color: #0066ff; font-weight: bold; font-style: italic; } /* Comment */
code span.do { color: #0066ff; font-style: italic; } /* Documentation */
code span.dt { text-decoration: underline; } /* DataType */
code span.dv { color: #44aa43; } /* DecVal */
code span.er { color: #ffff00; font-weight: bold; } /* Error */
code span.ex { } /* Extension */
code span.fl { color: #44aa43; } /* Float */
code span.fu { color: #ff9358; font-weight: bold; } /* Function */
code span.im { } /* Import */
code span.in { color: #0066ff; font-weight: bold; font-style: italic; } /* Information */
code span.kw { color: #43a8ed; font-weight: bold; } /* Keyword */
code span.op { } /* Operator */
code span.pp { font-weight: bold; } /* Preprocessor */
code span.sc { color: #049b0a; } /* SpecialChar */
code span.ss { color: #049b0a; } /* SpecialString */
code span.st { color: #049b0a; } /* String */
code span.va { } /* Variable */
code span.vs { color: #049b0a; } /* VerbatimString */
code span.wa { color: #ffff00; font-weight: bold; } /* Warning */
</style>
<link rel="stylesheet" href="tufte.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="associative-data">Associative Data</h1>
<h3 id="property-lists">Property Lists</h3>
<div class="sourceCode" id="cb1"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb1-1" title="1">(<span class="kw">list</span> :chris <span class="dv">34</span> :dave <span class="dv">38</span> :nicky <span class="dv">34</span> :alex <span class="dv">43</span>)</a>
<a class="sourceLine" id="cb1-2" title="2"><span class="co">;; => (:CHRIS 34 :DAVE 38 :NICKY 34 :ALEX 43)</span></a>
<a class="sourceLine" id="cb1-3" title="3"></a>
<a class="sourceLine" id="cb1-4" title="4">(<span class="kw">getf</span> (<span class="kw">list</span> :a <span class="dv">1</span> :b <span class="dv">2</span>) :a)</a>
<a class="sourceLine" id="cb1-5" title="5"><span class="co">;; => 1</span></a></code></pre></div>
<ul>
<li>Property lists are also known as ‘plists’.</li>
<li>Keys are usually written with <em>keywords</em>, which begin with a <code>:</code>.</li>
</ul>
<div class="sourceCode" id="cb2"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb2-1" title="1"></a>
<a class="sourceLine" id="cb2-2" title="2">(<span class="kw">append</span> (<span class="kw">list</span> :x <span class="dv">1</span> :y <span class="dv">2</span>) (<span class="kw">list</span> :bob <span class="dv">3</span> :alice <span class="dv">4</span>))</a>
<a class="sourceLine" id="cb2-3" title="3"><span class="co">;; => (:X 1 :Y 2 :BOB 3 :ALICE 4)</span></a>
<a class="sourceLine" id="cb2-4" title="4"></a>
<a class="sourceLine" id="cb2-5" title="5">(<span class="kw">append</span> (<span class="kw">list</span> :a <span class="dv">6</span> :b <span class="dv">5</span>) (<span class="kw">list</span> :b <span class="dv">4</span>))</a>
<a class="sourceLine" id="cb2-6" title="6"><span class="co">;; => (:A 6 :B 5 :B 4)</span></a>
<a class="sourceLine" id="cb2-7" title="7"></a>
<a class="sourceLine" id="cb2-8" title="8">(<span class="kw">getf</span> (<span class="kw">append</span> (<span class="kw">list</span> :a <span class="dv">6</span> :b <span class="dv">5</span>) (<span class="kw">list</span> :b <span class="dv">4</span>)) :b)</a>
<a class="sourceLine" id="cb2-9" title="9"><span class="co">;; => 5</span></a></code></pre></div>
<ul>
<li>You can add items to a plist with <code>append</code> <em>because it’s just a list</em>.</li>
<li>When retrieving a value by key, it will always get the most recent entry.</li>
</ul>
<h3 id="association-lists">Association Lists</h3>
<p>Association Lists - or alists - are similar but built out of lists of where each item is a <code>cons</code> cell.</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb3-1" title="1">(<span class="kw">list</span> (<span class="kw">cons</span> :a <span class="dv">1</span>) (<span class="kw">cons</span> :b <span class="dv">2</span>))</a>
<a class="sourceLine" id="cb3-2" title="2"><span class="co">;; => ((:A . 1) (:B . 2))</span></a>
<a class="sourceLine" id="cb3-3" title="3"></a>
<a class="sourceLine" id="cb3-4" title="4">(<span class="kw">assoc</span> :sally (<span class="kw">list</span> (<span class="kw">cons</span> :bob <span class="dv">5</span>) (<span class="kw">cons</span> :sally <span class="dv">7</span>)))</a>
<a class="sourceLine" id="cb3-5" title="5"><span class="co">;; => (:SALLY . 7)</span></a>
<a class="sourceLine" id="cb3-6" title="6"></a>
<a class="sourceLine" id="cb3-7" title="7">(<span class="kw">cdr</span> (<span class="kw">assoc</span> :sally (<span class="kw">list</span> (<span class="kw">cons</span> :bob <span class="dv">5</span>) (<span class="kw">cons</span> :sally <span class="dv">7</span>))))</a>
<a class="sourceLine" id="cb3-8" title="8"><span class="co">;; => 7</span></a>
<a class="sourceLine" id="cb3-9" title="9"></a>
<a class="sourceLine" id="cb3-10" title="10">(<span class="kw">assoc</span> :dave (<span class="kw">list</span> (<span class="kw">cons</span> :bob <span class="dv">5</span>) (<span class="kw">cons</span> :sally <span class="dv">7</span>)))</a>
<a class="sourceLine" id="cb3-11" title="11"><span class="co">;; => NIL</span></a></code></pre></div>
<ul>
<li><code>assoc</code> returns the <code>cons</code> cell where the <code>car</code> is equal to the value you give it.</li>
</ul>
<div class="sourceCode" id="cb4"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb4-1" title="1">(<span class="kw">assoc</span> :dave (<span class="kw">list</span> (<span class="kw">cons</span> :dave <span class="dv">1</span>) (<span class="kw">cons</span> :dave <span class="dv">2</span>) (<span class="kw">cons</span> :dave <span class="dv">3</span>)))</a>
<a class="sourceLine" id="cb4-2" title="2"><span class="co">;; => (:DAVE . 1)</span></a></code></pre></div>
<ul>
<li>The first <code>cons</code> cell is always returned, just as with plist.</li>
</ul>
<div class="sourceCode" id="cb5"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb5-1" title="1">(<span class="kw">acons</span> :dave <span class="dv">1</span> ())</a>
<a class="sourceLine" id="cb5-2" title="2"><span class="co">;; => ((:DAVE . 1))</span></a></code></pre></div>
<ul>
<li><code>acons</code> is a convenience function for appending to an alist.</li>
</ul>
<div class="sourceCode" id="cb6"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb6-1" title="1">(<span class="kw">append</span> (<span class="kw">list</span> (<span class="kw">cons</span> :butts <span class="st">"nice"</span>)) ())</a>
<a class="sourceLine" id="cb6-2" title="2"><span class="co">;; => ((:BUTTS . "nice"))</span></a></code></pre></div>
<ul>
<li>We can also use <code>append</code> to build alists if we like</li>
</ul>
<div class="sourceCode" id="cb7"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb7-1" title="1">(<span class="kw">cons</span> (<span class="kw">cons</span> :butts <span class="st">"nice"</span>) <span class="kw">nil</span>)</a>
<a class="sourceLine" id="cb7-2" title="2"><span class="co">;; => ((:BUTTS . "nice"))</span></a></code></pre></div>
<ul>
<li>Or <code>cons</code></li>
<li>Because <em>they’re just lists</em></li>
</ul>
<div class="sourceCode" id="cb8"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb8-1" title="1">(<span class="kw">rassoc</span> <span class="dv">2</span> (<span class="kw">list</span> (<span class="kw">cons</span> :butts <span class="dv">2</span>)))</a>
<a class="sourceLine" id="cb8-2" title="2"><span class="co">;; => (:BUTTS . 2)</span></a></code></pre></div>
<ul>
<li><code>rassoc</code> lets us find cons cells by value (or <code>cdr</code>)</li>
</ul>
<div class="sourceCode" id="cb9"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb9-1" title="1">(<span class="kw">rassoc</span> <span class="st">"nice"</span> (<span class="kw">list</span> (<span class="kw">cons</span> :butts <span class="st">"nice"</span>)))</a>
<a class="sourceLine" id="cb9-2" title="2"><span class="co">;; => NIL</span></a></code></pre></div>
<ul>
<li>Why doesn’t this work?</li>
<li><code>rassoc</code> (and <code>assoc</code>) use <code>eq</code> to compare values</li>
<li><code>eq</code> compares values by <em>object</em> equality - whether they are the same object</li>
<li>Strings are not guaranteed to be the same object</li>
</ul>
<div class="sourceCode" id="cb10"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb10-1" title="1">(<span class="kw">rassoc</span> <span class="st">"nice"</span> (<span class="kw">list</span> (<span class="kw">cons</span> :butts <span class="st">"nice"</span>)) <span class="bu">:test</span> #'equal)</a>
<a class="sourceLine" id="cb10-2" title="2"><span class="co">;; => (:BUTTS . "nice")</span></a></code></pre></div>
<ul>
<li>We can fix this by using the <code>equal</code> function to check for equality</li>
<li>The function is passed to <code>rassoc</code> prefixed by the <code>:test</code> keyword</li>
<li>This is called a <em>keyword argument</em></li>
</ul>
<h3 id="hashtable">Hashtable</h3>
<div class="sourceCode" id="cb11"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb11-1" title="1">(<span class="kw">defparameter</span><span class="fu"> *a-table* </span>(<span class="kw">make-hash-table</span>))</a>
<a class="sourceLine" id="cb11-2" title="2"><span class="co">;; => *A-TABLE*</span></a>
<a class="sourceLine" id="cb11-3" title="3"></a>
<a class="sourceLine" id="cb11-4" title="4">(<span class="kw">gethash</span> :dave *a-table*)</a>
<a class="sourceLine" id="cb11-5" title="5"><span class="co">;; => NIL</span></a>
<a class="sourceLine" id="cb11-6" title="6"><span class="co">;; NIL</span></a></code></pre></div>
<ul>
<li><code>make-hash-table</code> makes a hashtable</li>
<li><code>gethash</code> gets values from a hashtable</li>
</ul>
<div class="sourceCode" id="cb12"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb12-1" title="1">(<span class="kw">setf</span> (<span class="kw">gethash</span> :dave *a-table*) <span class="dv">45</span>)</a>
<a class="sourceLine" id="cb12-2" title="2"><span class="co">;; => 45</span></a></code></pre></div>
<ul>
<li><code>setf</code> to adds an entry to a hash table.</li>
<li><code>setf</code> is a macro</li>
<li>The first argument is a <em>place</em> (in this case, a place in the hash table).</li>
<li>The form <code>gethash</code> isn’t evaluated by <code>setf</code>. It is being used as a place by the <code>setf</code> macro.</li>
</ul>
<div class="sourceCode" id="cb13"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb13-1" title="1">(<span class="kw">gethash</span> :dave *a-table*)</a>
<a class="sourceLine" id="cb13-2" title="2"><span class="co">;; => 45</span></a>
<a class="sourceLine" id="cb13-3" title="3"><span class="co">;; T</span></a></code></pre></div>
<ul>
<li><code>gethash</code> returns two values: the first is the value associated with the key</li>
<li>The second is a boolean indicating whether the key was in the hash table</li>
</ul>
<div class="sourceCode" id="cb14"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb14-1" title="1">(<span class="kw">remhash</span> :dave *a-table*)</a>
<a class="sourceLine" id="cb14-2" title="2"><span class="co">;; => T</span></a></code></pre></div>
<ul>
<li><code>remhash</code> removes an entry from the hashtable.</li>
<li>It returns <code>t</code> if the key was present.</li>
<li>Otherwise it returns <code>nil</code></li>
</ul>
<div class="sourceCode" id="cb15"><pre class="sourceCode commonlisp"><code class="sourceCode commonlisp"><a class="sourceLine" id="cb15-1" title="1">(<span class="kw">gethash</span> :bobine *a-table* <span class="dv">4</span>)</a>
<a class="sourceLine" id="cb15-2" title="2"><span class="co">;; => 4</span></a>
<a class="sourceLine" id="cb15-3" title="3"><span class="co">;; NIL</span></a></code></pre></div>
<p>You can provide <code>gethash</code> with a default value. This value is returned if the key is not present in the hashtable.</p>
<h3 id="see-also">See also</h3>
<p><a href="http://www.lispworks.com/documentation/lw50/CLHS/Body/f_mk_has.htm">Common Lisp Hyperspec: MAKE-HASH-TABLE</a> <a href="http://www.lispworks.com/documentation/lw50/CLHS/Body/m_setf_.htm">Common Lisp Hyperspec: SETF, PSETF</a> <a href="http://gigamonkeys.com/book/collections.html">Practical Common Lisp: Collections</a></p>
</body>
</html>