RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://docs.racket-lang.org/reference/sets.html below:

4.19 Sets

4.19 Sets🔗ℹ

A set represents a collection of distinct elements. The following datatypes are all sets:

hash sets;
lists using equal? to compare elements; and
structures whose types implement the gen:set generic interface.

4.19.1 Hash Sets🔗ℹ

A hash set is a set whose elements are compared via equal?, equal-always?, eqv?, or eq? and partitioned via equal-hash-code, equal-always-hash-code, eqv-hash-code, or eq-hash-code. A hash set is either immutable or mutable; mutable hash sets retain their elements either strongly or weakly.

Like operations on immutable hash tables, “constant time” hash set operations actually require O(log N) time for a set of size N.

A hash set can be used as a stream (see Streams) and thus as a single-valued sequence (see Sequences). The elements of the set serve as elements of the stream or sequence. If an element is added to or removed from the hash set during iteration, then an iteration step may fail with exn:fail:contract, or the iteration may skip or duplicate elements. See also in-set.

Two hash sets are equal? when they use the same element-comparison procedure (equal?, equal-always?, eqv?, or eq?), both hold elements strongly or weakly, have the same mutability, and have equivalent elements. Immutable hash sets support effectively constant-time access and update, just like mutable hash sets; the constant on immutable operations is usually larger, but the functional nature of immutable hash sets can pay off in certain algorithms.

All hash sets implement set->stream, set-empty?, set-member?, set-count, subset?, proper-subset?, set-map, set-for-each, set-copy, set-copy-clear, set->list, and set-first. Immutable hash sets in addition implement set-add, set-remove, set-clear, set-union, set-intersect, set-subtract, and set-symmetric-difference. Mutable hash sets in addition implement set-add!, set-remove!, set-clear!, set-union!, set-intersect!, set-subtract!, and set-symmetric-difference!.

Operations on sets that contain elements that are mutated are unpredictable in much the same way that hash table operations are unpredictable when keys are mutated.

Changed in version 8.5.0.3 of package base: Added set-equal-always?.

Returns

#t

x

is a

hash set

that is respectively immutable, mutable with strongly-held keys, or mutable with weakly-held keys; returns

#f

otherwise.

Creates a

hash set

with the given

v

s as elements. The elements are added in the order that they appear as arguments, so in the case of sets that use

equal?

equal-always?

, or

eqv?

, an earlier element may be replaced by a later element that is

equal?

equal-always?

, or

eqv?

, but not

eq?

Changed in version 8.5.0.3 of package base: Added setalw, mutable-setalw, and weak-setalw.

Changed in version 8.5.0.3 of package base: Added list->setalw, list->mutable-setalw, and list->weak-setalw.

Changed in version 8.5.0.3 of package base: Added for/setalw, for/mutable-setalw, and for/weak-setalw.

Explicitly converts a specific kind of

hash set

to a sequence for use with

for

forms.

As with in-list and some other sequence constructors, in-immutable-set performs better when it appears directly in a for clause.

These sequence constructors are compatible with Custom Hash Sets.

Added in version 6.4.0.7 of package base.

4.19.2 Set Predicates and Contracts🔗ℹ

Returns

#t

v

is a

set

; returns

#f

otherwise.

Examples:

Returns

#t

st

implements all of the methods from

gen:set

named by the

sym

s; returns

#f

otherwise. Fallback implementations do not affect the result;

st

may support the given methods via fallback implementations yet produce

#f

Examples:

Recognizes sets that support all of the methods from

gen:set

named by the

sym

(set/c elem/c [ #:cmp cmp #:kind kind #:lazy? lazy? #:equal-key/c equal-key/c]) → contract?
elem/c : chaperone-contract? cmp : (or/c 'dont-care 'equal 'equal-always 'eqv 'eq) = 'dont-care kind : (or/c 'dont-care 'immutable 'mutable 'weak 'mutable-or-weak) = 'immutable equal-key/c : contract? = any/c

Constructs a contract that recognizes sets whose elements match elem/c.

If kind is 'immutable, 'mutable, or 'weak, the resulting contract accepts only hash sets that are respectively immutable, mutable with strongly-held keys, or mutable with weakly-held keys. If kind is 'mutable-or-weak, the resulting contract accepts any mutable hash sets, regardless of key-holding strength.

If cmp is 'equal, 'equal-always, 'eqv, or 'eq, the resulting contract accepts only hash sets that compare elements using equal?, equal-always?, eqv?, or eq?, respectively.

If cmp is 'eqv or 'eq, then elem/c must be a flat contract.

If cmp and kind are both 'dont-care, then the resulting contract will accept any kind of set, not just hash sets.

If lazy? is not #f, then the elements of the set are not checked immediately by the contract and only the set itself is checked (according to the cmp and kind arguments). If lazy? is #f, then the elements are checked immediately by the contract. The lazy? argument is ignored when the set contract accepts generic sets (i.e., when cmp and kind are both 'dont-care); in that case, the value being checked in that case is a list?, then the contract is not lazy otherwise the contract is lazy.

If kind allows mutable sets (i.e., is 'dont-care, 'mutable, 'weak, or 'mutable-or-weak) and lazy? is #f, then the elements are checked both immediately and when they are accessed from the set.

The equal-key/c contract is used when values are passed to the comparison and hashing functions used internally.

The result contract will be a flat contract when elem/c and equal-key/c are both flat contracts, lazy? is #f, and kind is 'immutable. The result will be a chaperone contract when elem/c is a chaperone contract.

Changed in version 8.3.0.9 of package base: Added support for random generation.
Changed in version 8.5.0.3: Added 'equal-always support for cmp.

4.19.3 Generic Set Interface🔗ℹ

Examples:

4.19.3.1 Set Methods🔗ℹ

The methods of gen:set can be classified into three categories, as determined by their fallback implementations:

methods with no fallbacks,
methods whose fallbacks depend on other, non-fallback methods,
and methods whose fallbacks can depend on either fallback or non-fallback methods.

As an example, implementing the following methods would guarantee that all the methods in gen:set would at least have a fallback method:

There may be other such subsets of methods that would guarantee at least a fallback for every method.

Returns #t if v is in st, #f otherwise. Has no fallback.

Produces a set that includes

v

plus all elements of

st

. This operation runs in constant time for

hash sets

. Has no fallback.

Adds the element

v

st

. This operation runs in constant time for

hash sets

. Has no fallback.

For hash sets, see also the caveats concerning concurrent modification for hash tables, which applies to hash sets.

Produces a set that includes all elements of

st

except

v

. This operation runs in constant time for

hash sets

. Has no fallback.

Removes the element

v

from

st

. This operation runs in constant time for

hash sets

. Has no fallback.

For hash sets, see also the caveats concerning concurrent modification for hash tables, which applies to hash sets.

Returns #t if st has no members; returns #f otherwise.

Supported for any st that implements set->stream or set-count.

Returns the number of elements in st.

Supported for any st that supports set->stream.

Produces an unspecified element of

st

. Multiple uses of

set-first

st

produce the same result.

Supported for any st that implements set->stream.

Produces a set that includes all elements of

st

except

(set-first st)

Supported for any st that implements set-remove and either set-first or set->stream.

Produces a stream containing the elements of st.

Produces a new, mutable set of the same type and with the same elements as st.

Supported for any st that supports set->stream and implements set-copy-clear and set-add!.

Produces a new, empty set of the same type, mutability, and key strength as st.

A difference between set-copy-clear and set-clear is that the latter conceptually iterates set-remove on the given set, and so it preserves any contract on the given set. The set-copy-clear function produces a new set without any contracts.

The set-copy-clear function must call concrete set constructors and thus has no generic fallback.

Produces a set like st but with all elements removed.

Supported for any st that implements set-remove and supports set->stream.

Removes all elements from st.

Supported for any st that implements set-remove! and either supports set->stream or implements set-first and either set-count or set-empty?.

For hash sets, see also the caveats concerning concurrent modification for hash tables, which applies to hash sets.

Produces a set of the same type as st0 that includes the elements from st0 and all of the sts.

If st0 is a list, each st must also be a list. This operation runs on lists in time proportional to the total size of the sts times the size of the result.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, equal-always?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the total size of all of the sets except the largest immutable set.

At least one set must be provided to set-union to determine the type of the resulting set (list, hash set, etc.). If there is a case where set-union may be applied to zero arguments, instead pass an empty set of the intended type as the first argument.

Supported for any st that implements set-add and supports set->stream.

Examples:

Adds the elements from all of the sts to st0.

Supported for any st that implements set-add! and supports set->stream.

For hash sets, see also the caveats concerning concurrent modification for hash tables, which applies to hash sets.

Produces a set of the same type as st0 that includes the elements from st0 that are also contained by all of the sts.

If st0 is a list, each st must also be a list. This operation runs on lists in time proportional to the total size of the sts times the size of st0.

Supported for any st that implements either set-remove or both set-clear and set-add, and supports set->stream.

Removes every element from st0 that is not contained by all of the sts.

Supported for any st that implements set-remove! and supports set->stream.

For hash sets, see also the caveats concerning concurrent modification for hash tables, which applies to hash sets.

Produces a set of the same type as st0 that includes the elements from st0 that are not contained by any of the sts.

If st0 is a list, each st must also be a list. This operation runs on lists in time proportional to the total size of the sts times the size of st0.

Supported for any st that implements either set-remove or both set-clear and set-add, and supports set->stream.

Removes every element from st0 that is contained by any of the sts.

Supported for any st that implements set-remove! and supports set->stream.

For hash sets, see also the caveats concerning concurrent modification for hash tables, which applies to hash sets.

Produces a set of the same type as st0 that includes all of the elements contained an odd number of times in st0 and the sts.

If st0 is a list, each st must also be a list. This operation runs on lists in time proportional to the total size of the sts times the size of st0.

Supported for any st that implements set-remove or both set-clear and set-add, and supports set->stream.

Example:

Adds and removes elements of st0 so that it includes all of the elements contained an odd number of times in the sts and the original contents of st0.

Supported for any st that implements set-remove! and supports set->stream.

For hash sets, see also the caveats concerning concurrent modification for hash tables, which applies to hash sets.

Returns #t if st and st2 contain the same members; returns #f otherwise.

If st is a list, then st2 must also be a list. This operation runs on lists in time proportional to the size of st times the size of st2.

If st is a hash set, then st2 must also be a hash set that uses the same comparison function (equal?, equal-always?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the size of st plus the size of st2.

Supported for any st and st2 that both support subset?; also supported for any if st2 that implements set=? regardless of st.

Examples:

Returns

#t

st2

contains every member of

st

; returns

#f

otherwise.

If st is a list, then st2 must also be a list. This operation runs on lists in time proportional to the size of st times the size of st2.

Supported for any st that supports set->stream.

Examples:

Returns #t if st2 contains every member of st and at least one additional element; returns #f otherwise.

If st is a list, then st2 must also be a list. This operation runs on lists in time proportional to the size of st times the size of st2.

Supported for any st and st2 that both support subset?.

Examples:

Produces a list containing the elements of st.

Supported for any st that supports set->stream.

Applies the procedure proc to each element in st in an unspecified order, accumulating the results into a list.

Supported for any st that supports set->stream.

Applies proc to each element in st (for the side-effects of proc) in an unspecified order.

Supported for any st that supports set->stream.

Explicitly converts a set to a sequence for use with

for

and other forms.

Supported for any st that supports set->stream.

Impersonates st, redirecting various set operations via the given procedures.

The inject-proc procedure is called whenever an element is temporarily put into the set for the purposes of comparing it with other elements that may already be in the set. For example, when evaluating (set-member? s e), e will be passed to the inject-proc before comparing it with other elements of s.

The add-proc procedure is called when adding an element to a set, e.g., via set-add or set-add!. The result of the add-proc is stored in the set.

The shrink-proc procedure is called when building a new set with one fewer element. For example, when evaluating (set-remove s e) or (set-remove! s e), an element is removed from a set, e.g., via set-remove or set-remove!. The result of the shrink-proc is the element actually removed from the set.

The extract-proc procedure is called when an element is pulled out of a set, e.g., by set-first. The result of the extract-proc is the element actually produced by from the set.

The clear-proc is called by set-clear and set-clear! and if it returns (as opposed to escaping, perhaps via raising an exception), the clearing operation is permitted. Its result is ignored. If clear-proc is #f, then clearing is done element by element (via calls into the other supplied procedures).

The equal-key-proc is called when an element’s hash code is needed of when an element is supplied to the underlying equality in the set. The result of equal-key-proc is used when computing the hash or comparing for equality.

If any of the inject-proc, add-proc, shrink-proc, or extract-proc arguments are #f, then they all must be #f, the clear-proc and equal-key-proc must also be #f, and there must be at least one property supplied.

Pairs of prop and prop-val (the number of arguments to impersonate-hash-set must be odd) add impersonator properties or override impersonator property values of st.

Chaperones

st

. Like

impersonate-hash-set

but with the constraints that the results of the

inject-proc

add-proc

shrink-proc

extract-proc

, and

equal-key-proc

must be

chaperone-of?

their second arguments. Also, the input may be an

immutable?

set.

4.19.4 Custom Hash Sets🔗ℹ

optional-predicate = | #:elem? predicate-expr optional-hash-functions = | hash1-expr | hash1-expr hash2-expr

Creates a new hash set type based on the given comparison

comparison-expr

, hash functions

hash1-expr

and

hash2-expr

, and element predicate

predicate-expr

; the interfaces for these functions are the same as in

make-custom-set-types

. The new set type has three variants: immutable, mutable with strongly-held elements, and mutable with weakly-held elements.

Defines seven names:

name? recognizes instances of the new type,
immutable-name? recognizes immutable instances of the new type,
mutable-name? recognizes mutable instances of the new type with strongly-held elements,
weak-name? recognizes mutable instances of the new type with weakly-held elements,
make-immutable-name constructs immutable instances of the new type,
make-mutable-name constructs mutable instances of the new type with strongly-held elements, and
make-weak-name constructs mutable instances of the new type with weakly-held elements.

The constructors all accept a stream as an optional argument, providing initial elements.

Examples:

Creates a new set type based on the given comparison function eql?, hash functions hash1 and hash2, and predicate elem?. The new set type has variants that are immutable, mutable with strongly-held elements, and mutable with weakly-held elements. The given name is used when printing instances of the new set type, and the symbol who is used for reporting errors.

The comparison function eql? may accept 2 or 3 arguments. If it accepts 2 arguments, it given two elements to compare them. If it accepts 3 arguments and does not accept 2 arguments, it is also given a recursive comparison function that handles data cycles when comparing sub-parts of the elements.

The hash functions hash1 and hash2 may accept 1 or 2 arguments. If either hash function accepts 1 argument, it is applied to a element to compute the corresponding hash value. If either hash function accepts 2 arguments and does not accept 1 argument, it is also given a recursive hash function that handles data cycles when computing hash values of sub-parts of the elements.

The predicate elem? must accept 1 argument and is used to recognize valid elements for the new set type.

Produces seven values:

a predicate recognizing all instances of the new set type,
a predicate recognizing weak instances,
a predicate recognizing mutable instances,
a predicate recognizing immutable instances,
a constructor for weak instances,
a constructor for mutable instances, and
a constructor for immutable instances.

See define-custom-set-types for an example.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4