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 } ;
  48
  49 ARTICLE: "lists-manipulation" "Manipulating lists"
  50 "To get at the contents of a list:"
  51 { $subsections
  52     uncons
  53     unswons
  54     lnth
  55     cadr
  56     llength
  57 }
  58 "To get a new list from an old one:"
  59 { $subsections
  60     lreverse
  61     lappend
  62     lcut
  63 } ;
  64
  65 HELP: cons
  66 { $values { "car" "the head of the list cell" } { "cdr" "the tail of the list cell" } { "cons-state" list } }
  67 { $description "Constructs a cons cell." } ;
  68
  69 HELP: swons
  70 { $values { "cdr" "the tail of the list cell" } { "car" "the head of the list cell" } { "cons" list } }
  71 { $description "Constructs a cons cell." } ;
  72
  73 { cons swons uncons unswons } related-words
  74
  75 HELP: car
  76 { $values { "cons" list } { "car" "the first item in the list" } }
  77 { $description "Returns the first item in the list." } ;
  78
  79 HELP: cdr
  80 { $values { "cons" list } { "cdr" list } }
  81 { $description "Returns the tail of the list." } ;
  82
  83 { car cdr } related-words
  84
  85 HELP: nil
  86 { $values { "symbol" "The empty cons (+nil+)" } }
  87 { $description "Returns a symbol representing the empty list" } ;
  88
  89 HELP: nil?
  90 { $values { "object" object } { "?" boolean } }
  91 { $description "Return true if the cons object is the nil cons." } ;
  92
  93 { nil nil? } related-words
  94
  95 { 1list 2list 3list } related-words
  96
  97 HELP: 1list
  98 { $values { "obj" object } { "cons" list } }
  99 { $description "Create a list with 1 element." } ;
 100
 101 HELP: 2list
 102 { $values { "a" object } { "b" object } { "cons" list } }
 103 { $description "Create a list with 2 elements." } ;
 104
 105 HELP: 3list
 106 { $values { "a" object } { "b" object } { "c" object } { "cons" list } }
 107 { $description "Create a list with 3 elements." } ;
 108
 109 HELP: lnth
 110 { $values { "n" "an integer index" } { "list" list } { "elt" "the element at the nth index" } }
 111 { $description "Outputs the nth element of the list." }
 112 { $see-also llength cons car cdr } ;
 113
 114 HELP: llength
 115 { $values { "list" list } { "n" "a non-negative integer" } }
 116 { $description "Outputs the length of the list. This should not be called on an infinite list." }
 117 { $see-also lnth cons car cdr } ;
 118
 119 HELP: uncons
 120 { $values { "cons" list } { "car" "the head of the list" } { "cdr" "the tail of the list" } }
 121 { $description "Put the head and tail of the list on the stack." } ;
 122
 123 HELP: unswons
 124 { $values { "cons" list } { "cdr" "the tail of the list" } { "car" "the head of the list" } }
 125 { $description "Put the head and tail of the list on the stack." } ;
 126
 127 { leach foldl lmap>array } related-words
 128
 129 HELP: leach
 130 { $values { "list" list } { "quot" { $quotation ( ... elt -- ... ) } } }
 131 { $description "Call the quotation for each item in the list." } ;
 132
 133 HELP: foldl
 134 { $values { "list" list } { "identity" object } { "quot" { $quotation ( ... prev elt -- ... next ) } } { "result" "the final result" } }
 135 { $description "Combines successive elements of the list (in a left-associative order) using a binary operation and outputs the final result." } ;
 136
 137 HELP: foldr
 138 { $values { "list" list } { "identity" object } { "quot" { $quotation ( ... prev elt -- ... next ) } } { "result" "the final result" } }
 139 { $description "Combines successive elements of the list (in a right-associative order) using a binary operation, and outputs the final result." } ;
 140
 141 HELP: lmap
 142 { $values { "list" list } { "quot" { $quotation ( ... elt -- ... newelt ) } } { "result" "the final result" } }
 143 { $description "Applies the quotation to each element of the list in order, collecting the new elements into a new list." } ;
 144
 145 HELP: lreverse
 146 { $values { "list" list } { "newlist" list } }
 147 { $description "Reverses the input list, outputting a new, reversed list. The output is a strict cons list." } ;
 148
 149 HELP: list>array
 150 { $values { "list" list } { "array" array } }
 151 { $description "Convert a list into an array." } ;
 152
 153 HELP: list
 154 { $class-description "The class of lists. All lists are expected to conform to " { $link "lists-protocol" } "." } ;
 155
 156 HELP: cadr
 157 { $values { "list" list } { "elt" object } }
 158 { $description "Returns the second element of the list, ie the car of the cdr." } ;
 159
 160 HELP: lappend
 161 { $values { "list1" list } { "list2" list } { "newlist" list } }
 162 { $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 exhausted." } ;
 163
 164 HELP: lcut
 165 { $values { "list" list } { "index" integer } { "before" cons } { "after" cons } }
 166 { $description "Analogous to " { $link cut } ", this word cuts a list into two pieces at the given index." } ;
 167
 168 HELP: lmap>array
 169 { $values { "list" list } { "quot" quotation } { "array" array } }
 170 { $description "Executes the quotation on each element of the list, collecting the results in an array." } ;
 171
 172 HELP: >list
 173 { $values { "object" object } { "list" "a list" } }
 174 { $description "Converts the object into a list." } ;