SRC Interactive Computing Facility Prolog Program LibrarySRC Interactive Computing Facility Prolog Program LibrarySRC Interactive Computing Facility Prolog Program Library SIG Artificial Intelligence BAGUTLSIG Artificial Intelligence BAGUTLSIG Artificial Intelligence BAGUTL Department of Artificial Intelligence Department of Artificial Intelligence Department of Artificial Intelligence University of Edinburgh University of Edinburgh University of Edinburgh BAG MANIPULATION UTILITY ROUTINES BAG MANIPULATION UTILITY ROUTINES BAG MANIPULATION UTILITY ROUTINES Source: R. A. O'Keefe Program Issued: 23 September 81 Documentation: 25 September 1981 1. Description1. Description1. Description Bags are a generalisation of sets, in which a given element may be present several times. Just as a set may be represented by its characteristic function (a mapping from some class to truth values), so may a bag be represented by its characteristic function, whose range is the non-negative integers. These routines manipulate Prolog data-structures encoding bags as tabular characteristic functions. X is an encoded bag if - it is the term 'bag', representing the empty bag. - it is the term bag(Element, Count, RestOfBag) where RestOfBag is a term representing a bag, Count is a (strictly) positive integer, and Element is any Prolog term. To make these representations canonical, Element must precede all the other elements of the bag, in the sense of '@<'. For example, the bag {a,b,c,d,c,a,d,c,a,e,d,c} would be represented by the Prolog term bag(a,3,bag(b,1,bag(c,4,bag(d,3,bag(e,1,bag))))). 2. How to Use the Program2. How to Use the Program2. How to Use the Program This library may already be loaded into UTIL. To see if it is, type 'listing(is_bag)' to UTIL. If it shows you any clauses, all these predicates should be available at once. Otherwise, you may either compile or consult the file 'Util:BagUtl.Pl'. The following predicates are then available. bag_inter(+Bag1, +Bag2, -Inter) takes the intersection of two bags. The count of an element in the result is the minimum of its count in Bag1 and its count in Bag2. bag_to_list(+Bag, -List) converts a Bag to a List. Each element of the Bag will appear in the List as many times as it occurs in {the abstract value of} the Bag. E.g. [% a:2, b:3, c:1 %] => [a,a, b,b,b, c]. BAGUTL - 2 - bag_to_set(+Bag, -SetList) converts a Bag to a Set, i.e. to a List in which each element of the Bag occurs exactly once. bag_union(+Bag1, +Bag2, -Union) takes the union of two bags. The count of an element in the result is the sum of its count in Bag1 and its count in Bag2. bagmax(+Bag, ?Elem) unifies Elem with that element of Bag which has the greatest not not count. NB: this is not an ordering on the elements themselves, but the ordinary arithmetic ordering on their frequencies. Predicates to select the alphabetically (@<) least and greatest elements could be supplied if anyone wanted them. bagmax returns the commonest one. bagmin(+Bag, ?Elem) unifies Elem with that element of Bag which has the least count. In other words, with the rarest object actually in the Bag. checkbag(+Pred, +Bag) is an analogue of checklist for bags. It succeeds if Pred(Elem,Count) is true for every element of the Bag and its associated Count. is_bag(+Bag) succeeds if Bag is a well-formed bag representation. Not all terms which resemble bags are bags: bag(1,a,bag) is not {'a' is not a positive integer} and bag(b,1,bag(a,1,bag)) is not {'b' is not alphabetically less than 'a}. length(+Bag, -Total, -Distinct) unifies Distinct with the number of distinct elements in the Bag and Total with the sum of their counts. Hence Total >= Distinct. This name was chosen to agree with the notation for lists (sets). list_to_bag(+List, -Bag) converts a List to a Bag. The elements of the list do not need to be in any special order. make_sub_bag(+Bag, -SubBag) A sub_bag predicate would have two uses: testing whether one already existing bag is a sub-bag of another, and generating ____ the sub-bags of a given bag. Since bags have so many sub-bags, this second use is likely to be rare, and has been split out as make_sub_bag. Given a Bag, make_sub_bag will backtrack through all its SubBags. mapbag(+Pred, +BagIn, -BagOut) is analogous to maplist. It applies Pred(Element,Transformed) to each element of the Bag, generating a transformed bag. The counts are not given to Pred, but are preserved. If several elements are mapped to the same transformed element, their counts will be added, so the result will always be a proper bag. For the same reason, the order of results in the answer - 3 - BAGUTL will be alphabetic, rather than the order of the elements in the input bag. member(?Elem, -Count, +Bag) can be used to backtrack through all the members of a bag or to test whether some specific object is in a bag. In either case Count is set to the element's count. NB if Elem is not an not not element of the bag, member will not unify Count with 0, it will fail fail fail. portray_bag(+Bag) These predicates assume that people will never want to type bags, but will always create them using bag utilities. Hence the internal representation is meant for efficiency rather than readability. If you add the clause portray(Bag) :- portray_bag(Bag). to your program you will get a prettier 'print'ed form (but not a 'write'n form, alas). A bag is printed between '[%' and '%]', with elements followed by a colon and their count, and separated by commas. For example, ?- list_to_bag([a,c,d,e,f,a,f,d,c,d,e,f,s], B). B = [% a:2, c:2, d:3, e:2, f:3, s:1 %] test_sub_bag(+SubBag, +Bag) tests whether SubBag is a sub bag of Bag. This is redundant, as test_sub_bag_2(Sb, Bg) :- bag_inter(Sb, Bg, In), In = Sb. It is cheaper and clearer to use test_sub_bag. 3. Program Requirements3. Program Requirements3. Program Requirements checkbag and mapbag require the utility apply/2. No other utilities are used, but BagUtl cannot be used with versions of Prolog prior to Version 3. The database is not affected. The compiled code occupies about 2k.