contrib/lazy-lists/lists.facts

   1 ! Copyright (C) 2006 Chris Double.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3
   4 USING: help lazy-lists sequences ;
   5
   6 HELP: <promise>
   7 { $values { "quot" "a quotation with stack effect ( -- X )" } { "promise" "a promise object" } }
   8 { $description "Creates a promise to return a value. When forced this quotation is called and the value returned. The value is memorised so that calling " { $link force } " again does not call the quotation again, instead the previous value is returned directly." }
   9 { $see-also force } ;
  10
  11 HELP: force
  12 { $values { "promise" "a promise object" } { "value" "a factor object" } }
  13 { $description "Calls the quotation associated with the promise if it has not been called before, and returns the value. If the promise has been forced previously, returns the value from the previous call." }
  14 { $see-also <promise> } ;
  15
  16 HELP: <cons>
  17 { $values { "car" "the head of the lazy list" } { "cdr" "the tail of the lazy list" } { "cons" "a cons object" } }
  18 { $description "Constructs a cons cell." }
  19 { $see-also cons car cdr nil nil? list? } ;
  20
  21 HELP: car
  22 { $values { "cons" "a cons object" } { "car" "the first item in the list" } }
  23 { $description "Returns the first item in the list." }
  24 { $see-also cons cdr nil nil? list? } ;
  25
  26 HELP: cdr
  27 { $values { "cons" "a cons object" } { "cdr" "a cons object" } }
  28 { $description "Returns the tail of the list." }
  29 { $see-also cons car nil nil? list? } ;
  30
  31 HELP: nil
  32 { $values { "cons" "An empty cons" } }
  33 { $description "Returns a representation of an empty list" }
  34 { $see-also cons car cdr nil? list? } ;
  35
  36 HELP: nil?
  37 { $values { "cons" "a cons object" } }
  38 { $description "Return true if the cons object is the nil cons." }
  39 { $see-also cons car cdr nil list? } ;
  40
  41 HELP: list?
  42 { $values { "object" "an object" } }
  43 { $description "Returns true if the object conforms to the list protocol." }
  44 { $see-also cons car cdr nil } ;
  45
  46 HELP: cons
  47 { $values { "car" "the head of the lazy list" } { "cdr" "the tail of the lazy list" } { "cons" "a cons object" } }
  48 { $description "Constructs a cons cell." }
  49 { $see-also car cdr nil nil? } ;
  50
  51 HELP: 1list
  52 { $values { "obj" "an object" } { "cons" "a cons object" } }
  53 { $description "Create a list with 1 element." }
  54 { $see-also 2list 3list } ;
  55
  56 HELP: 2list
  57 { $values { "a" "an object" } { "b" "an object" } { "cons" "a cons object" } }
  58 { $description "Create a list with 2 elements." }
  59 { $see-also 1list 3list } ;
  60
  61 HELP: 3list
  62 { $values { "a" "an object" } { "b" "an object" } { "c" "an object" } { "cons" "a cons object" } }
  63 { $description "Create a list with 3 elements." }
  64 { $see-also 1list 2list } ;
  65
  66 HELP: lazy-cons
  67 { $values { "car" "a quotation with stack effect ( -- X )" } { "cdr" "a quotation with stack effect ( -- cons )" } { "cons" "the resulting cons object" } }
  68 { $description "Constructs a cons object for a lazy list from two quotations. The 'car' quotation should return the head of the list, and the 'cons' quotation the tail when called. When " { $link cons } " or " { $link cdr } " are called on the lazy-cons object then the appropriate quotation is called." }
  69 { $see-also cons car cdr nil nil? } ;
  70
  71 HELP: 1lazy-list
  72 { $values { "a" "a quotation with stack effect ( -- X )" } { "lazy-cons" "a lazy-cons object" } }
  73 { $description "Create a lazy list with 1 element. The element is the result of calling the quotation. The quotation is only called when the list element is requested." }
  74 { $see-also 2lazy-list 3lazy-list } ;
  75
  76 HELP: 2lazy-list
  77 { $values { "a" "a quotation with stack effect ( -- X )" } { "b" "a quotation with stack effect ( -- X )" } { "lazy-cons" "a lazy-cons object" } }
  78 { $description "Create a lazy list with 2 elements. The elements are the result of calling the quotations. The quotations are only called when the list elements are requested." }
  79 { $see-also 1lazy-list 3lazy-list } ;
  80
  81 HELP: 3lazy-list
  82 { $values { "a" "a quotation with stack effect ( -- X )" } { "b" "a quotation with stack effect ( -- X )" } { "c" "a quotation with stack effect ( -- X )" } { "lazy-cons" "a lazy-cons object" } }
  83 { $description "Create a lazy list with 3 elements. The elements are the result of calling the quotations. The quotations are only called when the list elements are requested." }
  84 { $see-also 1lazy-list 2lazy-list } ;
  85
  86 HELP: <memoized-cons>
  87 { $values { "cons" "a cons object" } { "cons" "the resulting memoized-cons object" } }
  88 { $description "Constructs a cons object that wraps an existing cons object. Requests for the car, cdr and nil? will be remembered after the first call, and the previous result returned on subsequent calls." }
  89 { $see-also cons car cdr nil nil? } ;
  90
  91 HELP: lnth
  92 { $values { "n" "an integer index" } { "list" "a cons object" } { "elt" "the element at the nth index" } }
  93 { $description "Outputs the nth element of the list." }
  94 { $see-also cons car cdr } ;
  95
  96 HELP: uncons
  97 { $values { "cons" "a cons object" } { "car" "the head of the list" } { "cdr" "the tail of the list" } }
  98 { $description "Put the head and tail of the list on the stack." }
  99 { $see-also cons car cdr } ;
 100
 101 HELP: leach
 102 { $values { "list" "a cons object" } { "quot" "a quotation with stack effect ( obj -- )" } }
 103 { $description "Call the quotation for each item in the list." }
 104 { $see-also lmap lmap-with ltake lsubset lappend lfrom lfrom-by lconcat lcartesian-product lcartesian-product* lcomp lcomp* } ;
 105
 106 HELP: lmap
 107 { $values { "list" "a cons object" } { "quot" "a quotation with stack effect ( obj -- X )" } { "result" "resulting cons object" } }
 108 { $description "Perform a similar functionality to that of the " { $link map } " word, but in a lazy manner. No evaluation of the list elements occurs initially but a " { $link <lazy-map> } " object is returned which conforms to the list protocol. Calling " { $link car } ", " { $link cdr } " or " { $link nil? } " on this will evaluate elements as required." }
 109 { $see-also leach ltake lsubset lappend lmap-with  lfrom lfrom-by lconcat lcartesian-product lcartesian-product* lcomp lcomp* } ;
 110
 111 HELP: lmap-with
 112 { $values { "value" "an object" } { "list" "a cons object" } { "quot" "a quotation with stack effect ( obj elt -- X )" } { "result" "resulting cons object" } }
 113 { $description "Variant of " { $link lmap } " which pushes a retained object on each invocation of the quotation." }
 114 { $see-also leach ltake lsubset lappend lmap lfrom lfrom-by lconcat lcartesian-product lcartesian-product* lcomp lcomp* } ;
 115
 116 HELP: ltake
 117 { $values { "n" "a non negative integer" } { "list" "a cons object" } { "result" "resulting cons object" } }
 118 { $description "Outputs a lazy list containing the first n items in the list. This is done a lazy manner. No evaluation of the list elements occurs initially but a " { $link <lazy-take> } " object is returned which conforms to the list protocol. Calling " { $link car } ", " { $link cdr } " or " { $link nil? } " on this will evaluate elements as required." }
 119 { $see-also leach lmap lmap-with lsubset lappend lfrom lfrom-by lconcat lcartesian-product lcartesian-product* lcomp lcomp* } ;
 120
 121 HELP: lsubset
 122 { $values { "list" "a cons object" } { "quot" "a quotation with stack effect ( -- X )" } { "result" "resulting cons object" } }
 123 { $description "Perform a similar functionality to that of the " { $link subset } " word, but in a lazy manner. No evaluation of the list elements occurs initially but a " { $link <lazy-subset> } " object is returned which conforms to the list protocol. Calling " { $link car } ", " { $link cdr } " or " { $link nil? } " on this will evaluate elements as required." }
 124 { $see-also leach lmap lmap-with ltake lappend lfrom lfrom-by lconcat lcartesian-product lcartesian-product* lcomp lcomp* } ;
 125
 126 HELP: list>vector
 127 { $values { "list" "a cons object" } { "vector" "the list converted to a vector" } }
 128 { $description "Convert a list to a vector. If the list is a lazy infinite list then this will enter an infinite loop." }
 129 { $see-also list>array } ;
 130
 131 HELP: list>array
 132 { $values { "list" "a cons object" } { "array" "the list converted to an array" } }
 133 { $description "Convert a list to an array. If the list is a lazy infinite list then this will enter an infinite loop." }
 134 { $see-also list>vector } ;
 135
 136 HELP: lappend
 137 { $values { "list1" "a cons object" } { "list2" "a cons object" } { "result" "a lazy list of list2 appended to list1" } }
 138 { $description "Perform a similar functionality to that of the " { $link append } " word, but in a lazy manner. No evaluation of the list elements occurs initially but a " { $link <lazy-append> } " object is returned which conforms to the list protocol. Calling " { $link car } ", " { $link cdr } " or " { $link nil? } " on this will evaluate elements as required. Successive calls to " { $link cdr } " will iterate through list1, followed by list2." }
 139 { $see-also leach lmap lmap-with ltake lsubset lfrom lfrom-by lconcat lcartesian-product lcartesian-product* lcomp lcomp* } ;
 140
 141 HELP: lfrom-by
 142 { $values { "n" "an integer" } { "quot" "a quotation with stack effect ( -- int )" } { "result" "a lazy list of integers" } }
 143 { $description "Return an infinite lazy list of values starting from n, with each successive value being the result of applying quot to n." }
 144 { $see-also leach lmap lmap-with ltake lsubset lfrom lconcat lcartesian-product lcartesian-product* lcomp lcomp* } ;
 145
 146 HELP: lfrom
 147 { $values { "n" "an integer" } { "result" "a lazy list of integers" } }
 148 { $description "Return an infinite lazy list of incrementing integers starting from n." }
 149 { $see-also leach lmap lmap-with ltake lsubset lfrom-by lconcat lcartesian-product lcartesian-product* lcomp lcomp* } ;
 150
 151 HELP: seq>list
 152 { $values { "index" "an integer 0 or greater" } { "seq" "a sequence" } { "list" "a list" } }
 153 { $description "Convert the sequence into a list, starting from the 'index' offset into the sequence." }
 154 { $see-also >list } ;
 155
 156 HELP: >list
 157 { $values { "object" "an object" } { "list" "a list" } }
 158 { $description "Convert the object into a list. Existing lists are passed through intact, sequences are converted using " { $link seq>list } " and other objects cause an error to be thrown." }
 159 { $see-also seq>list } ;
 160
 161 HELP: lconcat
 162 { $values { "list" "a list of lists" } { "result" "a list" } }
 163 { $description "Concatenates a list of lists together into one list." }
 164 { $see-also leach lmap lmap-with ltake lsubset lcartesian-product lcartesian-product* lfrom-by lcomp lcomp* } ;
 165
 166 HELP: lcartesian-product
 167 { $values { "list1" "a list" } { "list2" "a list" } { "result" "list of cartesian products" } }
 168 { $description "Given two lists, return a list containing the cartesian product of those lists." }
 169 { $see-also leach lmap lmap-with lconcat ltake lsubset lfrom-by lcartesian-product* lcomp lcomp* } ;
 170
 171 HELP: lcartesian-product*
 172 { $values { "list" "a list of lists" } { "result" "list of cartesian products" } }
 173 { $description "Given a list of lists, return a list containing the cartesian product of those lists." }
 174 { $see-also leach lmap lmap-with lconcat ltake lsubset lfrom-by lcartesian-product lcomp lcomp* } ;
 175
 176 HELP: lcomp
 177 { $values { "list" "a list of lists" } { "quot" "a quotation with stack effect ( seq -- X )" } { "list" "the resulting list" } }
 178 { $description "Get the cartesian product of the lists in 'list' and call 'quot' call with each element from the cartesian product on the stack, the result of which is returned in the final 'list'." }
 179 { $see-also leach lmap lmap-with lconcat ltake lsubset lfrom-by lcartesian-product lcomp* } ;
 180
 181 HELP: lcomp*
 182 { $values { "list" "a list of lists" } { "guards" "a sequence of quotations with stack effect ( seq -- bool )" } { "quot" "a quotation with stack effect ( seq -- X )" } { "list" "the resulting list" } }
 183 { $description "Get the cartesian product of the lists in 'list', filter it by applying each guard quotation to it and call 'quot' call with each element from the remaining cartesian product items on the stack, the result of which is returned in the final 'list'." }
 184 { $examples
 185   { $example "{ 1 2 3 } >list { 4 5 6 } >list 2list { [ first odd? ] } [ first2 + ] lcomp*" }
 186 }
 187 { $see-also leach lmap lmap-with lconcat ltake lsubset lfrom-by lcartesian-product lcomp } ;
 188