Changeset 34294 in project


Ignore:
Timestamp:
08/20/17 11:46:44 (5 weeks ago)
Author:
sjamaan
Message:

man/5: Add Module (chicken sort) chapter

Location:
wiki/man/5
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • wiki/man/5/Module (chicken repl)

    r34288 r34294  
    5959Previous: [[Module (chicken read-syntax)]]
    6060
    61 Next: [[Module (chicken syntax)]]
     61Next: [[Module (chicken sort)]]
  • wiki/man/5/Module (chicken syntax)

    r34052 r34294  
    77
    88---
    9 Previous: [[Module (chicken repl)]]
     9Previous: [[Module (chicken sort)]]
    1010
    1111Next: [[Module (chicken tcp)]]
  • wiki/man/5/TODO/Unit data-structures

    r34052 r34294  
    122122
    123123Returns true if {{X}} is one of the tails (cdr's) of {{LIST}}.
    124 
    125 
    126 === Sorting
    127 
    128 
    129 ==== merge
    130 
    131 <procedure>(merge LIST1 LIST2 LESS?)</procedure><br>
    132 <procedure>(merge! LIST1 LIST2 LESS?)</procedure>
    133 
    134 Joins two lists in sorted order. {{merge!}} is the destructive
    135 version of merge. {{LESS?  }} should be a procedure of two arguments,
    136 that returns true if the first argument is to be ordered before the
    137 second argument.
    138 
    139 
    140 ==== sort
    141 
    142 <procedure>(sort SEQUENCE LESS?)</procedure><br>
    143 <procedure>(sort! SEQUENCE LESS?)</procedure>
    144 
    145 Sort {{SEQUENCE}}, which should be a list or a vector. {{sort!}}
    146 is the destructive version of sort.
    147 
    148 
    149 ==== sorted?
    150 
    151 <procedure>(sorted? SEQUENCE LESS?)</procedure>
    152 
    153 Returns true if the list or vector {{SEQUENCE}} is already sorted.
    154 
    155 ==== topological-sort
    156 
    157 <procedure>(topological-sort DAG PRED)</procedure>
    158 
    159 Sorts the directed acyclic graph dag {{DAG}} so that for every edge from vertex
    160 u to v, u will come before v in the resulting list of vertices.
    161 
    162 {{DAG}} is a list of sublists. The car of each sublist is a
    163 vertex. The cdr is the adjacency list of that vertex, i.e. a list of
    164 all vertices to which there exists an edge from the car vertex.
    165 {{pred}} is procedure of two arguments that should compare vertices
    166 for equality.
    167 
    168 Time complexity: O (|V| + |E|)
    169 
    170 <enscript highlight=scheme>
    171 (topological-sort
    172        '((shirt tie belt)
    173          (tie jacket)
    174          (belt jacket)
    175          (watch)
    176          (pants shoes belt)
    177          (undershorts pants shoes)
    178          (socks shoes))
    179        eq?)
    180 
    181 =>
    182 
    183 (socks undershorts pants shoes watch shirt belt tie jacket)
    184 </enscript>
    185 
    186 If a cycle is detected during the sorting process, an exception of the
    187 condition kinds {{(exn runtime cycle)}} is thrown.
    188124
    189125
  • wiki/man/5/TODO/new-manual.org

    r34271 r34294  
    4444** Module (chicken read-syntax) : Creating syntactic extensions to the reader
    4545** Module (chicken repl) : Creating a Read-Eval-Print Loop
     46** Module (chicken sort) : Sorting lists and vectors
    4647** Module (chicken syntax) : Creating syntactic extensions (macros)
    4748** Module (chicken tcp) : Connecting over the network via TCP
Note: See TracChangeset for help on using the changeset viewer.