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