Module (chicken sort) (historical revision 34294)

You are looking at historical revision 34294 of this page. It may differ significantly from its current revision.

manual

Module (chicken sort)
1. merge
2. sort
3. sorted?
4. topological-sort

Module (chicken sort)

This module contains several procedures which deal with sorting of sequences (i.e., lists and vectors).

merge

[procedure] (merge LIST1 LIST2 LESS?)
[procedure] (merge! LIST1 LIST2 LESS?)

Joins two lists in sorted order. merge! is the destructive version of merge. LESS? should be a procedure of two arguments, that returns true if the first argument is to be ordered before the second argument.

sort

[procedure] (sort SEQUENCE LESS?)
[procedure] (sort! SEQUENCE LESS?)

Sort SEQUENCE, which should be a list or a vector. sort! is the destructive version of sort.

sorted?

[procedure] (sorted? SEQUENCE LESS?)

Returns true if the list or vector SEQUENCE is already sorted.

topological-sort

[procedure] (topological-sort DAG PRED)

Sorts the directed acyclic graph dag DAG so that for every edge from vertex u to v, u will come before v in the resulting list of vertices.

DAG is a list of sublists. The car of each sublist is a vertex. The cdr is the adjacency list of that vertex, i.e. a list of all vertices to which there exists an edge from the car vertex. pred is procedure of two arguments that should compare vertices for equality.

Time complexity: O (|V| + |E|)

(topological-sort
       '((shirt tie belt)
         (tie jacket)
         (belt jacket)
         (watch)
         (pants shoes belt)
         (undershorts pants shoes)
         (socks shoes))
       eq?)

=>

(socks undershorts pants shoes watch shirt belt tie jacket)

If a cycle is detected during the sorting process, an exception of the condition kinds (exn runtime cycle) is thrown.

Previous: Module (chicken repl)

Next: Module (chicken syntax)