source: project/wiki/eggref/5/pseudolists @ 37751

Last change on this file since 37751 was 37751, checked in by juergen, 7 weeks ago

pseudolist-1.1 docu: sentinell-options added, syntax of pl-iterate and pl-for changed

File size: 10.1 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4== Pseudolists
5
6This module exports routines to handle pseudolists as a generalisation
7of ordinary lists.
8
9=== Rationale
10
11Pseudolists differ from lists insofor, as their sentinels might be
12arbitrary atoms instead of the empty lists. In other words, a
13pseudolist is either a pair or an atom. But since an atom is simply not
14a pair, everything is a pseudolist, in particular, a list is one.
15
16So the routines of this module have to be written so that they work for
17lists as well. For example, this means, that the sentinel doesn't count
18in a length routine, and have to be handled in constructors by supplying
19an additional argument, a sentinel-option.
20
21Additional sentinel-option arguments are not provided, if a sub-pseudolist is
22constructed, e.g. for filter, member, drop, take. In that case, the sentinel
23of the original pseudolist is used.
24
25Most functions in this module are written in curried and uncurried form.
26So the curried version can be used in maps and friends. The signature of
27both versions is documented below, but only the uncurried version is
28described. If the pseudolist argument is missing in the signature, it's
29the curried version.
30
31Note, that the order of arguments is consistent: Sentinel-options come first,
32procedures second and pseudolists last.
33To conform to this convention, I've changed the syntax of pl-iterate and
34pl-for.
35
36=== Module pseudolists
37
38==== pseudolists
39
40<procedure>(pseudolists)</procedure>
41<procedure>(pseudolists sym)</procedure>
42
43documentation procedure. The first call shows the list of exported
44routines, the second documentation of the routine with symbol sym.
45
46==== pl-maker
47
48<procedure>(pl-maker opt . args)</procedure>
49
50constructs a new pseudolist with (sentinel opt).
51
52==== pl?
53
54<procedure>(pl? xpr)</procedure>
55
56type predicate. Note that everything is a pseudolist!
57
58==== pl-of?
59
60<procedure>(pl-of? . preds)</procedure>
61
62returns a unary predicate, which tests, if its argument is
63passed by each predicate in preds.
64
65==== pl-null?
66
67<procedure>(pl-null? xpr)</procedure>
68
69not a pair.
70
71==== pl-length
72
73<procedure>(pl-length pl)</procedure>
74
75length of a pseudolist. The sentinel is not counted.
76
77==== pl-iterate
78
79<procedure>(pl-iterate opt fn k)</procedure>
80<procedure>(pl-iterate opt fn k init)</procedure>
81
82creates a pseudolist with (sentinel opt) applying fn to init
83recursively k times.
84
85==== pl-at
86
87<procedure>(pl-at k)</procedure>
88<procedure>(pl-at k pl)</procedure>
89
90returns the kth item of pl.
91
92==== pl-head
93
94<procedure>(pl-head pl)</procedure>
95
96returns the list of items with pl's sentinel stripped.
97
98==== pl-sentinel
99
100<procedure>(pl-sentinel pl)</procedure>
101
102returns the sentinel of pl.
103
104==== pl-drop
105
106<procedure>(pl-drop n)</procedure>
107<procedure>(pl-drop n pl)</procedure>
108
109returns the tail of pl removing all head items
110that pass the ok? test.
111
112==== pl-drop-while
113
114<procedure>(pl-drop-while ok?)</procedure>
115<procedure>(pl-drop-while ok? pl)</procedure>
116
117returns the tail of pl starting with the first item
118that does not pass the ok? test.
119
120==== pl-take
121
122<procedure>(pl-take n)</procedure>
123<procedure>(pl-take n pl)</procedure>
124
125returns the head of pl up to but excluding index n,
126where n is less than or equal to pl's pl-length.
127
128==== pl-take-while
129
130<procedure>(pl-take-while ok?)</procedure>
131<procedure>(pl-take-while ok? pl)</procedure>
132
133returns the head of pl consisting of items
134which pass the ok? test.
135
136==== pl-map
137
138<procedure>(pl-map opt fn)</procedure>
139<procedure>(pl-map opt fn pl)</procedure>
140
141maps fn over the pseudolist pl, returning a new pseudolist
142with (sentinel opt).
143
144==== pl-index
145
146<procedure>(pl-index ok?)</procedure>
147<procedure>(pl-index ok? pl)</procedure>
148
149returns the index of the first item passing
150the ok? test, -1 otherwise.
151
152==== filter
153
154<procedure>(filter ok?)</procedure>
155<procedure>(filter ok? pl)</procedure>
156
157returns the sublist of lst consisting of all items passing the ok?
158predicate.
159
160==== pl-reverse
161
162<procedure>(pl-reverse opt pl)</procedure>
163
164reverses its pseudolist argument, changing the sentinel
165to (sentinel opt).
166
167==== pl-append
168
169<procedure>(pl-append opt pl . pls)</procedure>
170
171appends all argument pseudolists to a new one with (sentinel opt).
172
173==== pl-memp
174
175<procedure>(pl-memp ok?)</procedure>
176<procedure>(pl-memp ok? pl)</procedure>
177
178returns the sub-pseudolist starting at the first
179item which passes the ok? test.
180
181==== pl-member
182
183<procedure>(pl-member x)</procedure>
184<procedure>(pl-member x pl)</procedure>
185
186same as (pl-memp (cut equal? <> x) pl).
187
188==== pl-memq
189
190<procedure>(pl-memq x)</procedure>
191<procedure>(pl-memq x pl)</procedure>
192
193same as (pl-memp (cut eq? <> x) pl).
194
195==== pl-memv
196
197<procedure>(pl-memv x)</procedure>
198<procedure>(pl-memv x pl)</procedure>
199
200same as (pl-memp (cut eqv? <> x) pl).
201
202==== pl-fold-right
203
204<procedure>(pl-fold-right op init)</procedure>
205<procedure>(pl-fold-right op init pl)</procedure>
206
207folds pl from the right with binary operation op
208and starting value init.
209
210==== pl-fold-right0
211
212<procedure>(pl-fold-right0 op)</procedure>
213<procedure>(pl-fold-right0 op pl)</procedure>
214
215folds (cdr pl) from the right with binary operation op
216and starting value (car pl).
217
218==== pl-fold-left
219
220<procedure>(pl-fold-left op init)</procedure>
221<procedure>(pl-fold-left op init pl)</procedure>
222
223folds pl from the left with binary operation op
224and starting value init.
225
226==== pl-fold-left0
227
228<procedure>(pl-fold-left0 op)</procedure>
229<procedure>(pl-fold-left0 op pl)</procedure>
230
231folds (cdr pl) from the left with binary operation op
232and starting value (car pl).
233
234==== pl-adjoin
235
236<procedure>(adjoin obj)</procedure>
237<procedure>(adjoin obj pl)</procedure>
238
239adds obj to the pseudolist pl, provided obj is not an item of lst.
240
241==== pl-remove-dups
242
243<procedure>(pl-remove-dups pl)</procedure>
244
245removes all duplicates of lst.
246
247==== pl-flatten
248
249<procedure>(pl-flatten opt pl-tree)</procedure>
250
251transforms a nested pseudolist to a flat pseudolist with (sentinel opt).
252
253==== pl-for
254
255<macro>(pl-for opt item-xpr (var pl ok-xpr ...) ....)</macro>
256
257creates a new pseudolist with (sentinel opt) by binding var to each element
258of the pseudolist pl in sequence, and if it passes the checks,
259ok-xpr ..., inserts the value of item-xpr into the resulting (pseudo-) list.
260The qualifieres, (var pl ok-xpr ...), are processed
261sequentially from left to right, so that filters of a
262qualifier have access to the variables of qualifiers
263to its left.
264
265=== Dependencies
266
267datatype
268
269=== Examples
270
271<enscript highlight=scheme>
272
273(import pseudolists)
274
275((pl-of? symbol?) '(a b . c)) ;-> #t
276(pl-maker (Some-sentinel #f) 0 1 2 3) ;-> '(0 1 2 3 . #f)
277(pl-maker (No-sentinel) 0 1 2 3) ;-> '(0 1 2 3)
278(pl-iterate (Some-sentienel #f) add1 5 0) ;-> '(0 1 2 3 4 . #f)
279
280(pl-length '(0 1 2 3 . 4)) ;-> 4
281(pl-head '(0 . 1)) ;-> '(0)
282(pl-at 2 '(0 1 2 3 . #f)) ;-> 2
283(condition-case (pl-at 0 1)
284  ((exn) #f)) ;-> #f
285
286(pl-index odd? '(0 2 4 . 1)) ;-> -1
287(pl-drop 0 1) ;-> 1
288(pl-drop 2 '(0 1 2 3 . #f)) ;-> '(2 3 . #f)
289(pl-take-while negative? '(1 3 2 4 . #f)) ;-> #f
290(pl-take 2 '(0 1 2 3 . #f)) ;-> '(0 1 . #f))
291
292(pl-filter odd? '(0 1 2 3 . 4)) ;-> '(1 3 . 4)
293(pl-map add1 (No-sentinel) '(0 1 2 3 . 4)) ;-> '(1 2 3 4)
294(pl-map (Some-sentinel 5) add1 '(0 1 2 3 . 4)) ;-> '(1 2 3 4 . 5)
295(pl-map (Some-sentinel #f) add1 '(0 1 2 3)) ;-> '(1 2 3 4 . #f)
296(pl-map (Some-sentinel #t) add1 #f) ;-> #t
297
298(pl-reverse (Some-sentinel #f) '(0 1 2 3 . 4)) ;-> '(3 2 1 0 . #f)
299(pl-reverse (No-sentinel) '(0 1 2 3 . 4)) ;-> '(3 2 1 0)
300
301(pl-append (Some-sentinel #f) '(0 1 . #t) '(2 3 . #t) '(4 5 . #t)) ;-> '(0 1 2 3 4 5 . #f)
302(pl-append (No-sentinel) '(0 1) '(2 3) #f) ;-> '(0 1 2 3)
303(pl-adjoin 2 '(0 1 2 3 . #f)) ;-> '(0 1 2 3 . #f)
304(pl-adjoin 1 '()) ;-> '(1)
305(pl-remove-dups '(0 1 2 3 2 . 2)) ;-> '(0 1 3 2 . 2)
306
307(pl-flatten (Some-sentinel #f) '(1 (2 3) . #t)) ;-> '(1 2 3 . #f)
308(pl-flatten (No-sentinel) '(1 (2 (3 . #f) . #t) . #f)) ;-> '(1 2 3)
309(pl-flatten (Some-sentinel #t) #f) ;-> #t
310(null? (pl-flatten (No-sentinel) #f) ;-> '()
311
312(pl-for (Some-sentinel #f) (add1 x) (x '(0 1 2 3 . #t))) ; map
313  ;-> '(1 2 3 4 . #f)
314(pl-for (No-sentinel) (add1 x) (x '(0 1 2 3))) ; map
315  ;-> '(1 2 3 4)
316(pl-for (No-sentinel) x (x '(0 1 2 3 4 5) (odd? x))) ; filter
317  ;-> '(1 3 5)
318(pl-for (Some-sentinel #f) (* 10 n)
319        (n '(0 1 2 3 4 5) (positive? n) (even? n)))
320  ;-> '(20 40 . #f)
321(pl-for (No-sentinel) (list c k)
322        (c '(A B C)) (k '(1 2 3 4)))
323  ;-> '((A 1) (A 2) (A 3) (A 4)
324  ;     (B 1) (B 2) (B 3) (B 4)
325  ;     (C 1) (C 2) (C 3) (C 4))
326(pl-for (No-sentinel) (list c k)
327        (c '(A B C . #f)) (k '(1 2 3 4 . #t)))
328  ;-> '((A 1) (A 2) (A 3) (A 4)
329  ;     (B 1) (B 2) (B 3) (B 4)
330  ;     (C 1) (C 2) (C 3) (C 4))
331
332</enscript>
333
334== Last update
335
336Jul 03, 2019
337
338== Author
339
340[[/users/juergen-lorenz|Juergen Lorenz]]
341
342== License
343
344 Copyright (c) 2019, Juergen Lorenz
345 All rights reserved.
346
347 Redistribution and use in source and binary forms, with or without
348 modification, are permitted provided that the following conditions are
349 met:
350 
351 Redistributions of source code must retain the above copyright
352 notice, this list of conditions and the following disclaimer.
353 
354 Redistributions in binary form must reproduce the above copyright
355 notice, this list of conditions and the following disclaimer in the
356 documentation and/or other materials provided with the distribution.
357 Neither the name of the author nor the names of its contributors may be
358 used to endorse or promote products derived from this software without
359 specific prior written permission.
360   
361 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
362 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
363 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
364 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
365 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
366 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
367 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
368 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
369 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
370 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
371 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
372
373== Version History
374
375; 1.1 : some sentinel-option arguments added; syntax-change of pl-for and pl-iterate
376; 1.0 : initial import
377
Note: See TracBrowser for help on using the repository browser.