Copyright 2008 - 2009 Tony Morris, Runar Bjarnason, Tom Adams, Brad Clow, Ricky Clarkson, Nick Partridge, Jason Zaugg

This software is released under an open source BSD licence.

fj.data
Class Set<A>

java.lang.Object
  extended by fj.data.Set<A>
All Implemented Interfaces:
Iterable<A>

public abstract class Set<A>
extends Object
implements Iterable<A>

Provides an in-memory, immutable set, implemented as a red/black tree.


Method Summary
<B> Set<B>
bind(Ord<B> o, F<A,Set<B>> f)
          Binds the given function across this set.
protected abstract  fj.data.Set.Color color()
           
 F<A,F<Set<A>,Set<A>>> delete()
          First-class deletion function.
 Set<A> delete(A a)
          Deletes the given element from this set.
static
<A> Set<A>
empty(Ord<A> ord)
          The empty set.
 Set<A> filter(F<A,Boolean> f)
          Filters elements from this set by returning only elements which produce true when the given function is applied to them.
<B> B
foldMap(F<A,B> f, Monoid<B> m)
          Folds this Set using the given monoid.
static
<A> F<A,F<Set<A>,Set<A>>>
insert()
          First-class insertion function.
 Set<A> insert(A x)
          Inserts the given element into this set.
 Set<A> intersect(Set<A> s)
          Remove all elements from this set that do not occur in the given set.
 boolean isEmpty()
           
static
<A> Set<A>
iterableSet(Ord<A> o, Iterable<A> as)
          Return the elements of the given iterable as a set.
 Iterator<A> iterator()
          Returns an iterator over this set.
static
<A> Set<A>
join(Ord<A> o, Set<Set<A>> s)
          Join a set of sets into a single set.
<B> Set<B>
map(Ord<B> o, F<A,B> f)
          Maps the given function across this set.
static
<A> F<Set<A>,F<A,Boolean>>
member()
          First-class membership check.
 boolean member(A x)
          Checks if the given element is a member of this set.
 Set<A> minus(Set<A> s)
          Remove all elements from this set that occur in the given set.
 Ord<A> ord()
          Returns the order of this Set.
static
<A> Set<A>
single(Ord<A> o, A a)
          Returns a set with a single element.
 int size()
          Returns the size of this set.
 P3<Set<A>,Option<A>,Set<A>> split(A a)
          Splits this set at the given element.
 boolean subsetOf(Set<A> s)
          Returns true if this set is a subset of the given set.
 List<A> toList()
          Returns a list representation of this set.
 Stream<A> toStream()
          Returns a stream representation of this set.
 Set<A> union(Set<A> s)
          Add all the elements of the given set to this set.
 P2<Boolean,Set<A>> update(A a, F<A,A> f)
          Updates, with the given function, the first element in the set that is equal to the given element, according to the order.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

isEmpty

public boolean isEmpty()

color

protected abstract fj.data.Set.Color color()

ord

public Ord<A> ord()
Returns the order of this Set.

Returns:
the order of this Set.

update

public P2<Boolean,Set<A>> update(A a,
                                 F<A,A> f)
Updates, with the given function, the first element in the set that is equal to the given element, according to the order.

Parameters:
a - An element to replace.
f - A function to transforms the found element.
Returns:
A pair of: (1) True if an element was found that matches the given element, otherwise false. (2) A new set with the given function applied to the first set element that was equal to the given element.

empty

public static <A> Set<A> empty(Ord<A> ord)
The empty set.

Parameters:
ord - An order for the type of elements.
Returns:
the empty set.

member

public boolean member(A x)
Checks if the given element is a member of this set.

Parameters:
x - An element to check for membership in this set.
Returns:
true if the given element is a member of this set.

member

public static <A> F<Set<A>,F<A,Boolean>> member()
First-class membership check.

Returns:
A function that returns true if the given element if a member of the given set.

insert

public Set<A> insert(A x)
Inserts the given element into this set.

Parameters:
x - An element to insert into this set.
Returns:
A new set with the given element inserted.

insert

public static <A> F<A,F<Set<A>,Set<A>>> insert()
First-class insertion function.

Returns:
A function that inserts a given element into a given set.

iterator

public Iterator<A> iterator()
Returns an iterator over this set.

Specified by:
iterator in interface Iterable<A>
Returns:
an iterator over this set.

single

public static <A> Set<A> single(Ord<A> o,
                                A a)
Returns a set with a single element.

Parameters:
o - An order for the type of element.
a - An element to put in a set.
Returns:
A new set with the given element in it.

map

public <B> Set<B> map(Ord<B> o,
                      F<A,B> f)
Maps the given function across this set.

Parameters:
o - An order for the elements of the new set.
f - A function to map across this set.
Returns:
The set of the results of applying the given function to the elements of this set.

foldMap

public <B> B foldMap(F<A,B> f,
                     Monoid<B> m)
Folds this Set using the given monoid.

Parameters:
f - A transformation from this Set's elements, to the monoid.
m - The monoid to fold this Set with.
Returns:
The result of folding the Set with the given monoid.

toList

public List<A> toList()
Returns a list representation of this set.

Returns:
a list representation of this set.

toStream

public Stream<A> toStream()
Returns a stream representation of this set.

Returns:
a stream representation of this set.

bind

public <B> Set<B> bind(Ord<B> o,
                       F<A,Set<B>> f)
Binds the given function across this set.

Parameters:
o - An order for the elements of the target set.
f - A function to bind across this set.
Returns:
A new set after applying the given function and joining the resulting sets.

union

public Set<A> union(Set<A> s)
Add all the elements of the given set to this set.

Parameters:
s - A set to add to this set.
Returns:
A new set containing all elements of both sets.

filter

public Set<A> filter(F<A,Boolean> f)
Filters elements from this set by returning only elements which produce true when the given function is applied to them.

Parameters:
f - The predicate function to filter on.
Returns:
A new set whose elements all match the given predicate.

delete

public Set<A> delete(A a)
Deletes the given element from this set.

Parameters:
a - an element to remove.
Returns:
A new set containing all the elements of this set, except the given element.

delete

public F<A,F<Set<A>,Set<A>>> delete()
First-class deletion function.

Returns:
A function that deletes a given element from a given set.

intersect

public Set<A> intersect(Set<A> s)
Remove all elements from this set that do not occur in the given set.

Parameters:
s - A set of elements to retain.
Returns:
A new set which is the intersection of this set and the given set.

minus

public Set<A> minus(Set<A> s)
Remove all elements from this set that occur in the given set.

Parameters:
s - A set of elements to delete.
Returns:
A new set which contains only the elements of this set that do not occur in the given set.

size

public int size()
Returns the size of this set.

Returns:
The number of elements in this set.

split

public P3<Set<A>,Option<A>,Set<A>> split(A a)
Splits this set at the given element. Returns a product-3 of:

Parameters:
a - A value at which to split this set.
Returns:
Two sets and an optional value, where all elements in the first set are less than the given value and all the elements in the second set are greater than the given value, and the optional value is the given value if found, otherwise None.

subsetOf

public boolean subsetOf(Set<A> s)
Returns true if this set is a subset of the given set.

Parameters:
s - A set which is a superset of this set if this method returns true.
Returns:
true if this set is a subset of the given set.

join

public static <A> Set<A> join(Ord<A> o,
                              Set<Set<A>> s)
Join a set of sets into a single set.

Parameters:
s - A set of sets.
o - An order for the elements of the new set.
Returns:
A new set which is the join of the given set of sets.

iterableSet

public static <A> Set<A> iterableSet(Ord<A> o,
                                     Iterable<A> as)
Return the elements of the given iterable as a set.

Parameters:
o - An order for the elements of the new set.
as - An iterable of elements to add to a set.
Returns:
A new set containing the elements of the given iterable.

Copyright 2008 - 2009 Tony Morris, Runar Bjarnason, Tom Adams, Brad Clow, Ricky Clarkson, Nick Partridge, Jason Zaugg

This software is released under an open source BSD licence.