| blob | b28cf2f0bb8e6b560964af2bf1beace0edb883eb |
1 <!-- This file is part of Shapes. -->
2 <!-- -->
3 <!-- Shapes is free software: you can redistribute it and/or modify -->
4 <!-- it under the terms of the GNU General Public License as published by -->
5 <!-- the Free Software Foundation, either version 3 of the License, or -->
6 <!-- any later version. -->
7 <!-- -->
8 <!-- Shapes is distributed in the hope that it will be useful, -->
9 <!-- but WITHOUT ANY WARRANTY; without even the implied warranty of -->
10 <!-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -->
11 <!-- GNU General Public License for more details. -->
12 <!-- -->
13 <!-- You should have received a copy of the GNU General Public License -->
14 <!-- along with Shapes. If not, see <http://www.gnu.org/licenses/>. -->
15 <!-- -->
16 <!-- Copyright 2008, 2010, 2013, 2015 Henrik Tidefelt -->
18 <section id="types/containers">
19 <title>Container types</title>
20 <top>
21 <p>Values of types in this section hold values of other types.</p>
22 </top>
24 <coretype name="ConsPair">
25 <type-parameters>
26 <parameter name="A">
27 <description>
28 <p>Type of <field name="car"/> field.</p>
29 </description>
30 </parameter>
31 <parameter name="D">
32 <description>
33 <p>Type of <field name="cdr"/> field.</p>
34 </description>
35 </parameter>
36 </type-parameters>
37 <abstraction>
38 <p>Container for two values. Often used to form linked lists and trees.</p>
39 </abstraction>
40 <see-also>
41 <value name="nil?" />
42 </see-also>
43 <construction>
44 </construction>
45 <type-templates>
46 <template name="T">
47 <description>
48 <p>Type of fold sum.</p>
49 </description>
50 </template>
51 <template-state name="S">
52 <description>
53 <p>State type.</p>
54 </description>
55 </template-state>
56 </type-templates>
57 <fields>
58 <type-field name="car">
59 <type><parameter-type name="A"/></type>
60 <description><p>First element.</p></description>
61 </type-field>
62 <type-field name="cdr">
63 <type><parameter-type name="B"/></type>
64 <description><p>Second element.</p></description>
65 </type-field>
66 <type-method name="foldl">
67 <function>
68 <case>
69 <arguments>
70 <arg identifier="op">
71 <type>
72 <function-type>
73 <arguments>
74 <arg><type><template-type name="T" /></type></arg>
75 <arg><type><parameter-type name="A" /></type></arg>
76 </arguments>
77 <result>
78 <type><template-type name="T" /></type>
79 </result>
80 </function-type>
81 </type>
82 </arg>
83 <arg identifier="zero"><type><template-type name="T" /></type></arg>
84 </arguments>
85 <result>
86 <type><template-type name="T" /></type>
87 </result>
88 <description>
89 <p>Performs a left fold, assuming that the <field name="cdr" /> field also has the same method. The following code would be a valid <str-Shapes /> implementation of the method.
90 <pre>
91 <![CDATA[\ op zero → [cdr.foldl op [op zero car]]]]>
92 </pre></p>
93 </description>
94 </case>
95 </function>
96 </type-method>
97 <type-method name="foldr">
98 <function>
99 <case>
100 <arguments>
101 <arg identifier="op">
102 <type>
103 <function-type>
104 <arguments>
105 <arg><type><parameter-type name="A" /></type></arg>
106 <arg><type><template-type name="T" /></type></arg>
107 </arguments>
108 <result>
109 <type><template-type name="T" /></type>
110 </result>
111 </function-type>
112 </type>
113 </arg>
114 <arg identifier="zero"><type><template-type name="T" /></type></arg>
115 </arguments>
116 <result>
117 <type><template-type name="T" /></type>
118 </result>
119 <description>
120 <p>Performs a right fold, assuming that the <field name="cdr" /> field also has the same method. The following code would be a valid <str-Shapes /> implementation of the method.
121 <pre>
122 <![CDATA[\ op zero → [op car [cdr.foldr op zero]]]]>
123 </pre></p>
124 </description>
125 </case>
126 </function>
127 </type-method>
128 <type-method name="foldsl">
129 <function>
130 <case>
131 <arguments>
132 <arg identifier="op">
133 <type>
134 <function-type>
135 <arguments>
136 <arg><type><template-type name="T" /></type></arg>
137 <arg><type><parameter-type name="A" /></type></arg>
138 <state><type><template-state-type name="S" /></type></state>
139 </arguments>
140 <result>
141 <type><template-type name="T" /></type>
142 </result>
143 </function-type>
144 </type>
145 </arg>
146 <arg identifier="zero"><type><template-type name="T" /></type></arg>
147 <state identifier="state"><type><template-state-type name="S" /></type></state>
148 </arguments>
149 <result>
150 <type><template-type name="T" /></type>
151 </result>
152 <description>
153 <p>Performs a left fold with state, assuming that the <field name="cdr" /> field also has the same method. The following code would be a valid <str-Shapes /> implementation of the method.
154 <pre>
155 <![CDATA[\ op zero •st → [cdr.foldsl op [op zero car •st] •st]]]>
156 </pre></p>
157 </description>
158 </case>
159 </function>
160 </type-method>
161 <type-method name="foldsr">
162 <function>
163 <case>
164 <arguments>
165 <arg identifier="op">
166 <type>
167 <function-type>
168 <arguments>
169 <arg><type><parameter-type name="A" /></type></arg>
170 <arg><type><template-type name="T" /></type></arg>
171 <state><type><template-state-type name="S" /></type></state>
172 </arguments>
173 <result>
174 <type><template-type name="T" /></type>
175 </result>
176 </function-type>
177 </type>
178 </arg>
179 <arg identifier="zero"><type><template-type name="T" /></type></arg>
180 <state identifier="state"><type><template-state-type name="S" /></type></state>
181 </arguments>
182 <result>
183 <type><template-type name="T" /></type>
184 </result>
185 <description>
186 <p>Performs a right fold with state, assuming that the <field name="cdr" /> field also has the same method. The following code would be a valid <str-Shapes /> implementation of the method.
187 <pre>
188 <![CDATA[\ op zero •st → [op car [cdr.foldsr op zero •st] •st]]]>
189 </pre></p>
190 </description>
191 </case>
192 </function>
193 </type-method>
194 </fields>
195 <description>
196 <p>When used to build linked lists, one shall use <binding name="nil" /> to terminate the list. Recall that this value is recognized by <binding name="nil?" />.</p>
197 <p>The following example illustrates the extension <a extension="seq-support" /> and how the laziness of <binding name="cons" /> allows infinite streams to be defined.</p>
199 <example-with-output title="Folds" internal-id="example/folds">
200 <source file="features/folds.shape">
201 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)features/folds.shape" -->]]>
202 </source>
203 <stdout>
204 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)features/folds.stdout" -->]]>
205 </stdout>
206 <caption>
207 <p>Folds over lists come in two flavors — left and right. <named-type name="ConsPair" /> can hold thunks, but infinite streams cannot be folded.</p>
208 </caption>
209 </example-with-output>
211 </description>
212 </coretype>
214 <coretype name="Seq">
215 <type-parameters>
216 <parameter name="E">
217 <description>
218 <p>Type of elements in list.</p>
219 </description>
220 </parameter>
221 </type-parameters>
222 <abstraction>
223 <p>A singly linked list.</p>
224 </abstraction>
225 <see-also>
226 <binding name="nil?" />
227 </see-also>
228 <definition>
229 <union-type>
230 <parameterized-type name="SeqPair">
231 <parameter-type name="E"/>
232 </parameterized-type>
233 <named-type name="SeqNil" />
234 </union-type>
235 </definition>
236 </coretype>
238 <coretype name="SeqPair">
239 <isa>
240 <parameterized-type name="Seq"><parameter-type name="E" /></parameterized-type>
241 </isa>
242 <type-parameters>
243 <parameter name="E">
244 <description>
245 <p>Type of elements in list.</p>
246 </description>
247 </parameter>
248 </type-parameters>
249 <abstraction>
250 <p>A non-empty singly linked list.</p>
251 </abstraction>
252 <definition>
253 <union-type>
254 <parameterized-type name="ConsPair">
255 <parameter-type name="E"/>
256 <parameterized-type name="Seq">
257 <parameter-type name="E"/>
258 </parameterized-type>
259 </parameterized-type>
260 </union-type>
261 </definition>
262 </coretype>
264 <coretype name="SeqNil">
265 <isa>
266 <parameterized-type name="Seq"><parameter-type name="E" /></parameterized-type>
267 </isa>
268 <abstraction>
269 <p>An empty singly linked list.</p>
270 </abstraction>
271 <see-also>
272 <binding name="nil?" />
273 </see-also>
274 <construction>
275 <binding name="list" />
276 </construction>
277 <type-templates>
278 <template name="T">
279 <description>
280 <p>Type of fold sum.</p>
281 </description>
282 </template>
283 <template-state name="S">
284 <description>
285 <p>State type.</p>
286 </description>
287 </template-state>
288 </type-templates>
289 <fields>
290 <type-method name="foldl">
291 <function>
292 <case>
293 <arguments>
294 <arg identifier="op"></arg>
295 <arg identifier="zero"><type><template-type name="T" /></type></arg>
296 </arguments>
297 <result>
298 <type><template-type name="T" /></type>
299 </result>
300 <description>
301 <p>Just returns <arg name="zero"/>.</p>
302 </description>
303 </case>
304 </function>
305 </type-method>
306 <type-method name="foldr">
307 <function>
308 <case>
309 <arguments>
310 <arg identifier="op"></arg>
311 <arg identifier="zero"><type><template-type name="T" /></type></arg>
312 </arguments>
313 <result>
314 <type><template-type name="T" /></type>
315 </result>
316 <description>
317 <p>Just returns <arg name="zero"/>.</p>
318 </description>
319 </case>
320 </function>
321 </type-method>
322 <type-method name="foldsl">
323 <function>
324 <case>
325 <arguments>
326 <arg identifier="op"></arg>
327 <arg identifier="zero"><type><template-type name="T" /></type></arg>
328 <state identifier="state"><type><template-state-type name="S" /></type></state>
329 </arguments>
330 <result>
331 <type><template-type name="T" /></type>
332 </result>
333 <description>
334 <p>Just returns <arg name="zero"/>.</p>
335 </description>
336 </case>
337 </function>
338 </type-method>
339 <type-method name="foldsr">
340 <function>
341 <case>
342 <arguments>
343 <arg identifier="op"></arg>
344 <arg identifier="zero"><type><template-type name="T" /></type></arg>
345 <state identifier="state"><type><template-state-type name="S" /></type></state>
346 </arguments>
347 <result>
348 <type><template-type name="T" /></type>
349 </result>
350 <description>
351 <p>Just returns <arg name="zero"/>.</p>
352 </description>
353 </case>
354 </function>
355 </type-method>
356 </fields>
357 <description>
358 <p>The following example illustrates the extension <extension path="..Shapes..Data/seq-support" /> and how the laziness of <value name="cons" /> <example-with-output title="Folds" internal-id="example:folds">
359 <source file="features/folds.blank">
360 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)features/folds.blank" -->]]>
361 </source>
362 <stdout>
363 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)features/folds.stdout" -->]]>
364 </stdout>
365 <caption>
366 <p>Folds over lists come in two flavors — left and right. <named-type name="ConsPair" /> can hold thunks, but infinite streams cannot be folded.</p>
367 </caption>
368 </example-with-output>
370 </description>
371 </coretype>
373 <coretype name="Array">
374 <abstraction>
375 <p>Values of type <self /> are one-dimensional arrays. The array has a finite size, does not contain any thunks, and any element can be accessed in constant time by specifying its index. The index of the first element is <eq>0</eq>.</p>
376 </abstraction>
377 <isa>
378 <function-type>
379 <arguments>
380 <arg><type><named-type name="Integer" /></type></arg>
381 </arguments>
382 <result><named-type name="Value" /></result>
383 </function-type>
384 </isa>
385 <construction>
386 <value name="newArray" />
387 </construction>
388 <type-templates>
389 <template name="T">
390 <description>
391 <p>Type of fold sum.</p>
392 </description>
393 </template>
394 <template name="E">
395 <description>
396 <p>Type of list elements.</p>
397 </description>
398 </template>
399 <template-state name="S">
400 <description>
401 <p>State type.</p>
402 </description>
403 </template-state>
404 </type-templates>
405 <fields>
406 <type-field name="size">
407 <type><named-type name="Integer" /></type>
408 <description><p>The size of the array.</p></description>
409 </type-field>
410 <type-field name="range">
411 <type><named-type name="Seq" /></type>
412 <description>
413 <p>Range of valid indices, from low to high. Constant time and space implementation. Efficient for left folds; instead of a right fold over <field name="range" />, one should try to make a left fold over <field name="reverse_range" /> instead.</p>
414 <p>For <inline>arr</inline> of type <self />, <inline>arr.range</inline> is equivalent to
415 <pre>
416 <![CDATA[[range '0 count:arr.size]]]>
417 </pre>
418 </p>
419 </description>
420 </type-field>
421 <type-field name="reverse_range">
422 <type><named-type name="Seq" /></type>
423 <description>
424 <p>Reverse range of valid indices, from high to low. Constant time and space implementation. Efficient for left folds; instead of a right fold over <field name="reverse_range" />, one should try to make a left fold over <field name="range" /> instead.</p>
425 <p>For <inline>arr</inline> of type <self />, <inline>arr.reverse_range</inline> is equivalent to
426 <pre>
427 <![CDATA[[range arr.size-'1 step:'~1 count:arr.size]]]>
428 </pre>
429 </p>
430 </description>
431 </type-field>
432 <type-field name="list">
433 <type><named-type name="Seq" /></type>
434 <description><p>Converts the array to a list.</p></description>
435 </type-field>
436 <type-method name="foldl">
437 <function>
438 <case>
439 <arguments>
440 <arg identifier="op">
441 <type>
442 <function-type>
443 <arguments>
444 <arg><type><template-type name="T" /></type></arg>
445 <arg><type><template-type name="E" /></type></arg>
446 </arguments>
447 <result>
448 <type><template-type name="T" /></type>
449 </result>
450 </function-type>
451 </type>
452 </arg>
453 <arg identifier="zero"><type><template-type name="T" /></type></arg>
454 </arguments>
455 <result>
456 <type><template-type name="T" /></type>
457 </result>
458 <description>
459 <p>Performs a left fold over the array.</p>
460 </description>
461 </case>
462 </function>
463 </type-method>
464 <type-method name="foldr">
465 <function>
466 <case>
467 <arguments>
468 <arg identifier="op">
469 <type>
470 <function-type>
471 <arguments>
472 <arg><type><template-type name="E" /></type></arg>
473 <arg><type><template-type name="T" /></type></arg>
474 </arguments>
475 <result>
476 <type><template-type name="T" /></type>
477 </result>
478 </function-type>
479 </type>
480 </arg>
481 <arg identifier="zero"><type><template-type name="T" /></type></arg>
482 </arguments>
483 <result>
484 <type><template-type name="T" /></type>
485 </result>
486 <description>
487 <p>Performs a right fold over the array.</p>
488 </description>
489 </case>
490 </function>
491 </type-method>
492 <type-method name="foldsl">
493 <function>
494 <case>
495 <arguments>
496 <arg identifier="op">
497 <type>
498 <function-type>
499 <arguments>
500 <arg><type><template-type name="T" /></type></arg>
501 <arg><type><template-type name="E" /></type></arg>
502 <state><type><template-state-type name="S" /></type></state>
503 </arguments>
504 <result>
505 <type><template-type name="T" /></type>
506 </result>
507 </function-type>
508 </type>
509 </arg>
510 <arg identifier="zero"><type><template-type name="T" /></type></arg>
511 <state identifier="state"><type><template-state-type name="S" /></type></state>
512 </arguments>
513 <result>
514 <type><template-type name="T" /></type>
515 </result>
516 <description>
517 <p>Performs a left fold with state over the array.</p>
518 </description>
519 </case>
520 </function>
521 </type-method>
522 <type-method name="foldsr">
523 <function>
524 <case>
525 <arguments>
526 <arg identifier="op">
527 <type>
528 <function-type>
529 <arguments>
530 <arg><type><template-type name="T" /></type></arg>
531 <arg><type><template-type name="E" /></type></arg>
532 <state><type><template-state-type name="S" /></type></state>
533 </arguments>
534 <result>
535 <type><template-type name="T" /></type>
536 </result>
537 </function-type>
538 </type>
539 </arg>
540 <arg identifier="zero"><type><template-type name="T" /></type></arg>
541 <state identifier="state"><type><template-state-type name="S" /></type></state>
542 </arguments>
543 <result>
544 <type><template-type name="T" /></type>
545 </result>
546 <description>
547 <p>Performs a right fold with state over the array.</p>
548 </description>
549 </case>
550 </function>
551 </type-method>
552 </fields>
553 </coretype>
555 <coretype name="Structure">
556 <abstraction>
557 <p>Container mirroring the information being passed to the callee in a function application. That is, it may contain both named and ordered fields.</p>
558 </abstraction>
559 <construction>
560 <syntax name="structure" />
561 </construction>
562 <fields>
563 <!-- Having an empty <fields> tag will generate an empty list of fields, rather than the text "A value of type ... has no fields."-->
564 </fields>
565 <description>
566 <p>The contents of a <named-type name="Structure" /> value can be passed to a function using the <syntax name="split-call" />. The named fields of a structure may also be accessed just like the named fields of any other compound value. Ordered values may be accessed using trivial helper functions (simply returning the appropriate ordered argument).</p>
567 <p>For an example showing the various ways to work with <named-type name="Structure" /> values, see the <syntax name="structure" /> syntax.</p>
568 </description>
569 </coretype>
571 </section>