basis/lists/lists-docs.factor

   1 ! Copyright (C) 2006 Chris Double.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel help.markup help.syntax arrays sequences math quotations ;
   4 IN: lists
   5
   6 ABOUT: "lists"
   7
   8 ARTICLE: "lists" "Lists"
   9 "The " { $vocab-link "lists" } " vocabulary implements linked lists. There are simple strict linked lists, but a generic list protocol allows the implementation of lazy lists as well."
  10 { $subsections
  11     { "lists" "protocol" }
  12     { "lists" "strict" }
  13     { "lists" "manipulation" }
  14     { "lists" "combinators" }
  15 }
  16 { $vocab-subsection "Lazy lists" "lists.lazy" } ;
  17
  18 ARTICLE: { "lists" "protocol" } "The list protocol"
  19 "Lists are instances of a mixin class:"
  20 { $subsections list }
  21 "Instances of the mixin must implement the following words:"
  22 { $subsections
  23     car
  24     cdr
  25     nil?
  26 } ;
  27
  28 ARTICLE: { "lists" "strict" } "Constructing strict lists"
  29 "Strict lists are simply cons cells where the car and cdr have already been evaluated. These are the lists of Lisp. To construct a strict list, the following words are provided:"
  30 { $subsections
  31     cons
  32     swons
  33     sequence>list
  34     1list
  35     2list
  36     3list
  37 } ;
  38
  39 ARTICLE: { "lists" "combinators" } "Combinators for lists"
  40 "Several combinators exist for list traversal."
  41 { $subsections
  42     leach
  43     lmap
  44     foldl
  45     foldr
  46     lmap>array
  47     traverse
  48 } ;
  49
  50 ARTICLE: { "lists" "manipulation" } "Manipulating lists"
  51 "To get at the contents of a list:"
  52 { $subsections
  53     uncons
  54     unswons
  55     lnth
  56     cadr
  57     llength
  58 }
  59 "To get a new list from an old one:"
  60 { $subsections
  61     lreverse
  62     lappend
  63     lcut
  64 } ;
  65
  66 HELP: cons
  67 { $values { "car" "the head of the list cell" } { "cdr" "the tail of the list cell" } { "cons" list } }
  68 { $description "Constructs a cons cell." } ;
  69
  70 HELP: swons
  71 { $values { "cdr" "the tail of the list cell" } { "car" "the head of the list cell" } { "cons" list } }
  72 { $description "Constructs a cons cell." } ;
  73
  74 { cons swons uncons unswons } related-words
  75
  76 HELP: car
  77 { $values { "cons" list } { "car" "the first item in the list" } }
  78 { $description "Returns the first item in the list." } ;
  79
  80 HELP: cdr
  81 { $values { "cons" list } { "cdr" list } }
  82 { $description "Returns the tail of the list." } ;
  83
  84 { car cdr } related-words
  85
  86 HELP: nil
  87 { $values { "symbol" "The empty cons (+nil+)" } }
  88 { $description "Returns a symbol representing the empty list" } ;
  89
  90 HELP: nil?
  91 { $values { "object" object } { "?" "a boolean" } }
  92 { $description "Return true if the cons object is the nil cons." } ;
  93
  94 { nil nil? } related-words
  95
  96 { 1list 2list 3list } related-words
  97
  98 HELP: 1list
  99 { $values { "obj" "an object" } { "cons" list } }
 100 { $description "Create a list with 1 element." } ;
 101
 102 HELP: 2list
 103 { $values { "a" "an object" } { "b" "an object" } { "cons" list } }
 104 { $description "Create a list with 2 elements." } ;
 105
 106 HELP: 3list
 107 { $values { "a" "an object" } { "b" "an object" } { "c" "an object" } { "cons" list } }
 108 { $description "Create a list with 3 elements." } ;
 109
 110 HELP: lnth
 111 { $values { "n" "an integer index" } { "list" list } { "elt" "the element at the nth index" } }
 112 { $description "Outputs the nth element of the list." }
 113 { $see-also llength cons car cdr } ;
 114
 115 HELP: llength
 116 { $values { "list" list } { "n" "a non-negative integer" } }
 117 { $description "Outputs the length of the list. This should not be called on an infinite list." }
 118 { $see-also lnth cons car cdr } ;
 119
 120 HELP: uncons
 121 { $values { "cons" list } { "car" "the head of the list" } { "cdr" "the tail of the list" } }
 122 { $description "Put the head and tail of the list on the stack." } ;
 123
 124 HELP: unswons
 125 { $values { "cons" list } { "car" "the head of the list" } { "cdr" "the tail of the list" } }
 126 { $description "Put the head and tail of the list on the stack." } ;
 127
 128 { leach foldl lmap>array } related-words
 129
 130 HELP: leach
 131 { $values { "list" list } { "quot" { $quotation "( obj -- )" } } }
 132 { $description "Call the quotation for each item in the list." } ;
 133
 134 HELP: foldl
 135 { $values { "list" list } { "identity" "an object" } { "quot" { $quotation "( prev elt -- next )" } } { "result" "the final result" } }
 136 { $description "Combines successive elements of the list (in a left-assocative order) using a binary operation and outputs the final result." } ;
 137
 138 HELP: foldr
 139 { $values { "list" list } { "identity" "an object" } { "quot" { $quotation "( prev elt -- next )" } } { "result" "the final result" } }
 140 { $description "Combines successive elements of the list (in a right-assocative order) using a binary operation, and outputs the final result." } ;
 141
 142 HELP: lmap
 143 { $values { "list" list } { "quot" { $quotation "( old -- new )" } } { "result" "the final result" } }
 144 { $description "Applies the quotation to each element of the list in order, collecting the new elements into a new list." } ;
 145
 146 HELP: lreverse
 147 { $values { "list" list } { "newlist" list } }
 148 { $description "Reverses the input list, outputing a new, reversed list. The output is a strict cons list." } ;
 149
 150 HELP: list>array
 151 { $values { "list" list } { "array" array } }
 152 { $description "Convert a list into an array." } ;
 153
 154 HELP: traverse
 155 { $values { "list"  list } { "pred" { $quotation "( list/elt -- ? )" } }
 156           { "quot" { $quotation "( list/elt -- result)" } }  { "result" "a new cons object" } }
 157 { $description "Recursively traverses the list object, replacing any elements (which can themselves be sublists) that pred"
 158  " returns true for with the result of applying quot to." } ;
 159
 160 HELP: list
 161 { $class-description "The class of lists. All lists are expected to conform to " { $link { "lists" "protocol" } } "." } ;
 162
 163 HELP: cadr
 164 { $values { "list" list } { "elt" object } }
 165 { $description "Returns the second element of the list, ie the car of the cdr." } ;
 166
 167 HELP: lappend
 168 { $values { "list1" list } { "list2" list } { "newlist" list } }
 169 { $description "Appends the two lists to form a new list. The first list must be finite. The result is a strict cons cell, and the first list is exausted." } ;
 170
 171 HELP: lcut
 172 { $values { "list" list } { "index" integer } { "before" cons } { "after" cons } }
 173 { $description "Analogous to " { $link cut } ", this word cuts a list into two pieces at the given index." } ;
 174
 175 HELP: lmap>array
 176 { $values { "list" list } { "quot" quotation } { "array" array } }
 177 { $description "Executes the quotation on each element of the list, collecting the results in an array." } ;
 178