doc/parts/extensions/conssupport.sxml

   1 <?xml version="1.0" encoding="UTF-8"?>
   2 <?xml-stylesheet type="text/xsl" href="formats/html.xsl"?>
   3
   4 <!-- This file is part of Shapes.                                           -->
   5 <!--                                                                        -->
   6 <!-- Shapes is free software: you can redistribute it and/or modify         -->
   7 <!-- it under the terms of the GNU General Public License as published by   -->
   8 <!-- the Free Software Foundation, either version 3 of the License, or      -->
   9 <!-- any later version.                                                     -->
  10 <!--                                                                        -->
  11 <!-- Shapes is distributed in the hope that it will be useful,              -->
  12 <!-- but WITHOUT ANY WARRANTY; without even the implied warranty of         -->
  13 <!-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          -->
  14 <!-- GNU General Public License for more details.                           -->
  15 <!--                                                                        -->
  16 <!-- You should have received a copy of the GNU General Public License      -->
  17 <!-- along with Shapes.  If not, see <http://www.gnu.org/licenses/>.        -->
  18 <!--                                                                        -->
  19 <!-- Copyright 2008, 2014 Henrik Tidefelt                                   -->
  20
  21
  22 <book>
  23         <title>conssupport</title>
  24         <description>
  25                 <p>Tools for working with cons-style lists (à la Scheme, for instance).</p>
  26         </description>
  27         <meta-selflink><self-href /></meta-selflink>
  28         <base href=<!--#expand-next-string-->"$(BASE)" />
  29         <examples-home href=<!--#expand-next-string-->"$(EXAMPLES)" />
  30         <shapes-version number=<!--#expand-next-string-->"$(SHAPES_VERSION)" />
  31         <up-link><parent-namespace /></up-link>
  32         <needs></needs>
  33         <public-namespace>Shapes..Data</public-namespace>
  34   <external>
  35     <!--#include virtual="^/toc.xml" -->
  36   </external>
  37         <top>
  38                 <alphabetical-index/>
  39                 <p>Currently, <str-Shapes /> provides both a dedicated type for singly linked lists, <named-type name="SingleList" />, as well as the two-value-container <named-type name="ConsPair" /> which can also be used to build singly linked lists.  The <str-Shapes /> kernel does not provide any functions that operate on <named-type name="ConsPair" /> lists, but basic operations are defined in this extension.</p>
  40                 <p>Note that <named-type name="ConsPair" /> lists are by definition terminated by the empty <named-type name="SingleList" />, recognized by <binding name="null?" /> — or else they are just arbitrary <named-type name="ConsPair" /> structures.</p>
  41                 <p>There is an example with some relevance to this package which appears under <named-type name="ConsPair" />.</p>
  42         </top>
  43
  44         <section id="extensions/conssupport/folds">
  45                 <title>Folds</title>
  46                 <body>
  47                         <p>Recall the fold operations that are accessed as fields of <named-type name="SingleList" /> values.  This extension defines these for <named-type name="ConsPair" /> lists.</p>
  48
  49                 <system-binding identifier="foldl">
  50                         <function>
  51                                 <case>
  52                                         <type-templates>
  53                                                 <template name="T">
  54                                                         <description>
  55                                                                 <p>Type of fold pile.</p>
  56                                                         </description>
  57                                                 </template>
  58                                                 <template name="E">
  59                                                         <description>
  60                                                                 <p>Type of list elements.</p>
  61                                                         </description>
  62                                                 </template>
  63                                         </type-templates>
  64                                         <arguments>
  65                                                 <arg identifier="op">
  66                                                         <type>
  67                                                                 <function-type>
  68                                                                         <arguments>
  69                                                                                 <arg><type><template-type name="T" /></type></arg>
  70                                                                                 <arg><type><template-type name="E" /></type></arg>
  71                                                                         </arguments>
  72                                                                         <result>
  73                                                                                 <type><template-type name="T" /></type>
  74                                                                         </result>
  75                                                                 </function-type>
  76                                                         </type>
  77                                                 </arg>
  78                                                 <arg identifier="nullRes"><type><template-type name="T" /></type></arg>
  79                                                 <arg identifier="lst"><type><named-type name="ConsPair" /></type></arg>
  80                                         </arguments>
  81                                         <result>
  82                                                 <type><template-type name="T" /></type>
  83                                         </result>
  84                                         <dynamic-references></dynamic-references>
  85                                         <description>
  86                                                 <p>Left fold.</p>
  87                                         </description>
  88                                 </case>
  89                         </function>
  90                 </system-binding>
  91
  92                 <system-binding identifier="foldr">
  93                         <function>
  94                                 <case>
  95                                         <type-templates>
  96                                                 <template name="T">
  97                                                         <description>
  98                                                                 <p>Type of fold pile.</p>
  99                                                         </description>
 100                                                 </template>
 101                                                 <template name="E">
 102                                                         <description>
 103                                                                 <p>Type of list elements.</p>
 104                                                         </description>
 105                                                 </template>
 106                                         </type-templates>
 107                                         <arguments>
 108                                                 <arg identifier="op">
 109                                                         <type>
 110                                                                 <function-type>
 111                                                                         <arguments>
 112                                                                                 <arg><type><template-type name="T" /></type></arg>
 113                                                                                 <arg><type><template-type name="E" /></type></arg>
 114                                                                         </arguments>
 115                                                                         <result>
 116                                                                                 <type><template-type name="T" /></type>
 117                                                                         </result>
 118                                                                 </function-type>
 119                                                         </type>
 120                                                 </arg>
 121                                                 <arg identifier="nullRes"><type><template-type name="T" /></type></arg>
 122                                                 <arg identifier="lst"><type><named-type name="ConsPair" /></type></arg>
 123                                         </arguments>
 124                                         <result>
 125                                                 <type><template-type name="T" /></type>
 126                                         </result>
 127                                         <dynamic-references></dynamic-references>
 128                                         <description>
 129                                                 <p>Right fold.</p>
 130                                         </description>
 131                                 </case>
 132                         </function>
 133                 </system-binding>
 134
 135                 <system-binding identifier="foldsl">
 136                         <function>
 137                                 <case>
 138                                         <type-templates>
 139                                                 <template name="T">
 140                                                         <description>
 141                                                                 <p>Type of fold pile.</p>
 142                                                         </description>
 143                                                 </template>
 144                                                 <template name="E">
 145                                                         <description>
 146                                                                 <p>Type of list elements.</p>
 147                                                         </description>
 148                                                 </template>
 149                                                 <template-state name="S">
 150                                                         <description>
 151                                                                 <p>Type of state.</p>
 152                                                         </description>
 153                                                 </template-state>
 154                                         </type-templates>
 155                                         <arguments>
 156                                                 <arg identifier="op">
 157                                                         <type>
 158                                                                 <function-type>
 159                                                                         <arguments>
 160                                                                                 <arg><type><template-type name="T" /></type></arg>
 161                                                                                 <arg><type><template-type name="E" /></type></arg>
 162                                                                                 <state><type><template-state-type name="S" /></type></state>
 163                                                                         </arguments>
 164                                                                         <result>
 165                                                                                 <type><template-type name="T" /></type>
 166                                                                         </result>
 167                                                                 </function-type>
 168                                                         </type>
 169                                                 </arg>
 170                                                 <arg identifier="nullRes"><type><template-type name="T" /></type></arg>
 171                                                 <state identifier="state"><type><template-state-type name="S" /></type></state>
 172                                                 <arg identifier="lst"><type><named-type name="ConsPair" /></type></arg>
 173                                         </arguments>
 174                                         <result>
 175                                                 <type><template-type name="T" /></type>
 176                                         </result>
 177                                         <dynamic-references></dynamic-references>
 178                                         <description>
 179                                                 <p>Left fold with state.</p>
 180                                         </description>
 181                                 </case>
 182                         </function>
 183                 </system-binding>
 184
 185                 <system-binding identifier="foldsr">
 186                         <function>
 187                                 <case>
 188                                         <type-templates>
 189                                                 <template name="T">
 190                                                         <description>
 191                                                                 <p>Type of fold pile.</p>
 192                                                         </description>
 193                                                 </template>
 194                                                 <template name="E">
 195                                                         <description>
 196                                                                 <p>Type of list elements.</p>
 197                                                         </description>
 198                                                 </template>
 199                                                 <template-state name="S">
 200                                                         <description>
 201                                                                 <p>Type of state.</p>
 202                                                         </description>
 203                                                 </template-state>
 204                                         </type-templates>
 205                                         <arguments>
 206                                                 <arg identifier="op">
 207                                                         <type>
 208                                                                 <function-type>
 209                                                                         <arguments>
 210                                                                                 <arg><type><template-type name="T" /></type></arg>
 211                                                                                 <arg><type><template-type name="E" /></type></arg>
 212                                                                                 <state><type><template-state-type name="S" /></type></state>
 213                                                                         </arguments>
 214                                                                         <result>
 215                                                                                 <type><template-type name="T" /></type>
 216                                                                         </result>
 217                                                                 </function-type>
 218                                                         </type>
 219                                                 </arg>
 220                                                 <arg identifier="nullRes"><type><template-type name="T" /></type></arg>
 221                                                 <state identifier="state"><type><template-state-type name="S" /></type></state>
 222                                                 <arg identifier="lst"><type><named-type name="ConsPair" /></type></arg>
 223                                         </arguments>
 224                                         <result>
 225                                                 <type><template-type name="T" /></type>
 226                                         </result>
 227                                         <dynamic-references></dynamic-references>
 228                                         <description>
 229                                                 <p>Right fold with state.</p>
 230                                         </description>
 231                                 </case>
 232                         </function>
 233                 </system-binding>
 234
 235                 </body>
 236         </section> <!-- End of  -->
 237
 238         <section id="extensions/conssupport/misc">
 239                 <title>Miscellaneous</title>
 240                 <body>
 241                         <p>Here are the functions that have no corresponding function for <named-type name="SingleList" /> in the kernel.</p>
 242
 243                 <system-binding identifier="consify">
 244                         <function>
 245                                 <case>
 246                                         <arguments>
 247                                                 <arg identifier="lst">
 248                                                         <type><named-type name="SingleList" /></type>
 249                                                 </arg>
 250                                         </arguments>
 251                                         <result>
 252                                                 <type><named-type name="ConsPair" /></type>
 253                                         </result>
 254                                         <dynamic-references></dynamic-references>
 255                                         <description>
 256                                                 <p>Convert from of type of list to the other.</p>
 257                                         </description>
 258                                 </case>
 259                         </function>
 260                 </system-binding>
 261
 262                 <system-binding identifier="map">
 263                         <function>
 264                                 <case>
 265                                         <type-templates>
 266                                                 <template name="E">
 267                                                         <description>
 268                                                                 <p>Type of original list elements.</p>
 269                                                         </description>
 270                                                 </template>
 271                                                 <template name="T">
 272                                                         <description>
 273                                                                 <p>Type of new list elements.</p>
 274                                                         </description>
 275                                                 </template>
 276                                         </type-templates>
 277                                         <arguments>
 278                                                 <arg identifier="f">
 279                                                         <type>
 280                                                                 <function-type>
 281                                                                         <arguments>
 282                                                                                 <arg><type><template-type name="E" /></type></arg>
 283                                                                         </arguments>
 284                                                                         <result>
 285                                                                                 <type><template-type name="T" /></type>
 286                                                                         </result>
 287                                                                 </function-type>
 288                                                         </type>
 289                                                 </arg>
 290                                                 <arg identifier="lst"><type><named-type name="ConsPair" /></type></arg>
 291                                         </arguments>
 292                                         <result>
 293                                                 <type><named-type name="ConsPair" /></type>
 294                                         </result>
 295                                         <dynamic-references></dynamic-references>
 296                                         <description>
 297                                                 <p>Construct new list with elements obtained by applying <arg name="f" /> to the corresponding element in <arg name="lst" />.</p>
 298                                         </description>
 299                                 </case>
 300                         </function>
 301                 </system-binding>
 302
 303                 <system-binding identifier="sublist">
 304                         <function>
 305                                 <case>
 306                                         <arguments>
 307                                                 <arg identifier="lst">
 308                                                         <type><named-type name="SingleList" /></type>
 309                                                 </arg>
 310                                                 <arg identifier="n">
 311                                                         <type><named-type name="Integer" /></type>
 312                                                 </arg>
 313                                         </arguments>
 314                                         <result>
 315                                                 <type><named-type name="ConsPair" /></type>
 316                                         </result>
 317                                         <dynamic-references></dynamic-references>
 318                                         <description>
 319                                                 <p>Construct list with just the first <arg name="n" /> elements in <arg name="lst" /> (or all of <arg name="lst" /> if <arg name="n" /> exceeds the length of the list).  Obviously, <arg name="n" /> shall be non-negative.</p>
 320                                         </description>
 321                                 </case>
 322                         </function>
 323                 </system-binding>
 324
 325
 326                 </body>
 327         </section> <!-- End of  -->
 328
 329 </book>