Collection library（集合库）

From wiki.visual-prolog.com

（以下内容译自Category:Tutorials中的Collection_library。）

集合（collection）是一种值，它含有若干（从0个直至无数个）其它数值。

表、集、字典、数组、杂凑表、（非确定性的）事实数据库，等等，都是集合。

集合可以只含有一个值，但是本来就仅只有一个值这样类型的数据则不是集合。所以，只有一个元素的表是集合，但总含有一个元素的变量则不是集合。

PFC 含有一个面向对象的集合库，其中既有不变集合又有可变集合。集合库主要内容包括一组定义各种概念集合类型的通用接口及实现这些接口的一些类。


不变与可变

集合可以是不变的，也可以是可变的。

不变 不变集合其成员不会发生变化。这就是说，在一个不变集合中插入或删去一个成员时，会得到一个新的集合，而原来的那个集合保持不变。Prolog 的表就是不变数据类型的典型例子：当按照一个模式取表头和表尾时，原表仍是保持完好的；如果用一个新的头及原来的一个表创建表，会得到一个新表，而原来的表也仍保持不变。 可变 一个可变集合，其成员可以从集合中删去，也可以添加新的成员。这意味着，在一个可变集合中插入或删去一个成员，这个集合原来的值就没有了，只剩下改过的这个集合。即，可变集合被破坏性地更新了。Visual Prolog 的事实数据库是可变数据类型的典型例子：插入或撤消事实，数据库就被更新了，而原来的事实数据库也就没有了。

集合接口与类

从不变集合或可变集合中取数据并没有本质差别，而在更新时，这两种集合就有差别了。

因此，取数据的接口是这两种集合所共享的，而更新用的接口则是各自的。

collection 是对集合取数或查看的最基本的接口，所有集合都支持这个接口。它含有的方法有：

  • isEmpty 确认集合是否为空
  • contains 查看某个元素是否在集合中
  • tryGetFirst 取集合中的第一个元素
  • getAll_nd 逐一清点集合中的所有元素
  • asList 以表的形式取集合

要注意，first 在不同类型的集合中代表不同的东西，比如说，在哈希表（杂凑表）中它表示的是带有第一个哈希键的元素。

同样地，getAll_nd 清点其元素的顺序也与集合的类型有关系。

还需要注意，对某个类型的集合某种操作的性能可能效率很差，例如， contains 对优先级队列来说操作效率就很差，因为优先队列不是设计用来确定成员关系的。

所有不变集合还支持接口 persistent ，所有可变集合还支持接口 modifiable。 persistent 和 modifiable 具有的谓词名称相同但类型是不同的，因为不变版的会返回一个新集合而可变版的则不会有返回。这两种接口具有的方法有：

  • insert、insertList 和 insertCollection 用于插入元素
  • remove、removeList 和 removeCollection 用于删除元素
  • tryRemoveFirst 用于删除第一个元素
  • clear 用于删除集合中的所有元素

set（集）

set 是不含重复元素的集合。它的基本操作是对成员的检测，因而它只支持接口 collection 及接口 persistent 和 modifiable 之一。

  • setP_redBlack 实现基于红黑树表示法的不变集。
  • setM_redBlack 实现基于红黑树表示法的可变集。

queue（队列）

queue 是有序元素的集合。它的基本操作是取队列的第一个元素，它之中的成员关系检测效率是很低的。队列的接口与集的相仿，支持 collection 及接口 persistent 与 modifiable 之一。 不同的名称用以强调内涵及功效上的差别，以后它们的发展也会有不同。PFC 中有两类队列：

  • queue 是“常规”的 FIFO （先进先出）队列。
    • queueP_fact 实现不变 FIFO 队列，这个队列是基于含代数队列的事实数据库的。
    • queueM_fact 实现可变 FIFO 队列，这个队列是基于非确定性事实数据库的。
  • priority queue（优先级队列） 是第一个元素永远有最高优先级（比如“最小”、“最大”或用户指定的某种比较形式）的队列。
    • priorityQueueP_leftist 实现不变的优先级队列。
    • priorityQueueM_leftist 实现可变的优先级队列。

它们都是左树结构的（参见 wikipedia:Leftist tree）。

map（映射）

map 是 keys（键） 与 values 的对应关系。并非所有的键都得有值。其基本操作是设、取及试取某个键对应的值。对键设置值的时候，先前设置的键值就“丢失”了。

映射是（key,value）组元的集合，所以 collection 谓词处理的也都是这样的组元。

map 接口是检测（不变与可变）映射的基本接口。它还支持(key,value)组元的 collection 接口并有以下谓词/属性扩展：

  • get 和 tryGet 用于取一个键相关的值
  • getKey_nd 和 getValue_nd 用于逐个取键和值
  • keyList 和 valueList 用于以表的形式取全部的键和值

mapP （不变映射）和 mapM （可变映射）支持 map 及 persistent 或 modifiable 接口，还有扩展：

  • set 用于设置键的值（先前设置的值就“丢失”了）
  • removeKey 用于删除键及相应的值
  • removeKeyList 和 removeKeyCollection 用于删除若干键及相应的值

PFC 中含有基于红黑树的不变与可变映射的类：

  • mapP_redBlack
  • mapM_redBlack

应用举例

这里的例题创意源自Niels Kokholm 和 Peter Sestoft的 The C5 Generic Collection Library for C# and CLI，IT 大学技术报告序列号 TR-2006-76, 2006.

关键字识别

确定一个单词是否为某个固定单词集合中的成员是经常遇到的需求。比如，在一种程序语言中索引文本时判别是关键字还是非关键字。

首先，我们来实现一个类，它只有一个确定性的谓词，可以判别一个单词是否是关键字： 

class vipKeyword
predicates
    isKeyword : (string Word) determ.
end class vipKeyword

以关键字的集来实现是当然的选择，因为集的基本操作正是对成员关系的检测。实现可以像这样： 

implement vipKeyword
clauses
    isKeyword(Word) :-
        keywordSet:contains(Word).
 
class facts
    keywordSet : setM{string Keyword} := initKeywordSet().
 
class predicates
    initKeywordSet : () -> setM{string Keyword}.
clauses
    initKeywordSet() = S :-
        S = setM_redBlack::new(),
        S:insertList(keywords).
 
constants
    keywords : string* = ["as", "class", "clauses", ...].
end implement vipKeyword

isKeyword 只是确定 keywordSet 是否contains 询问的 Word 。

keywordSet 是串的（可变）集，初始化为含有为 keywords 常数的实际的关键字。

像上面那样初始化类事实时要特别小心，在进入程序的目标之前这样的初始化执行顺序是无法预测的。所以，首先遇到的困难是不知道程序哪些其它的部分已经初始化了；其次是异常系统还没有适当地初始化，故将报告相当低级别的异常。

文本词汇索引

文本词汇索引是文本中的单词及单词在文本中出现行号的一个表，也就是文本索引。

我们用映射来表示文本词汇索引，映射的关系是 Word 对一组 Linenumber，这里的单词是串而行号是整数。为方便起见，定义一个域： 

domains
    concordance = mapM{string Word, setM{integer Linenumber}}.

为建立一个系统（典型情况是对一个文件）的文本词汇索引，可以逐行读文件及每行中的单词。把每个单词插入到相应行号的集里，如果这个集还不存在，就需要创建它： 

class predicates
    build : (inputStream Input) -> concordance Concordance.
clauses
    build(Input) = Concordance :-
        Concordance = mapM_redBlack::new(),
        foreach
            tuple(Line, Linenumber) = getLine_nd(Input, 1),
            Word = getWord_nd(Line)
        do
            if LinenumberSet = Concordance:tryGet(Word) then
            else
                LinenumberSet = setM_redBlack::new(),
                Concordance:set(Word, LinenumberSet)
            end if,
            LinenumberSet:insert(Linenumber)
        end foreach.

反复取数据的谓词如下： 

class predicates
    getLine_nd : (inputStream Input, integer NextLine) -> tuple{string Line, integer Linenumber} nondeterm.
clauses
    getLine_nd(Input, _NextLine) = _ :-
        Input:endOfStream(),
        !,
        fail.
 
    getLine_nd(Input, NextLine) = tuple(Line, NextLine) :-
        Line = Input:readLine().
 
    getLine_nd(Input, NextLine) = getLine_nd(Input, NextLine+1).
 
class predicates
    getWord_nd : (string Line) -> string Word nondeterm.
clauses
    getWord_nd(Line) = getWord2_nd(First, Rest) :-
        string::frontToken(Line, First, Rest).
 
class predicates
    getWord2_nd : (string First, string Rest) -> string Word nondeterm.
clauses
    getWord2_nd(First, _Rest) = string::toLowerCase(First) :-
        string::length(First) > 2, % 只取至少多于两个字母的单词
        not(regexp::search("[^a-zA-Z]", First, _, _)). % 如果含有非字母则不是一个单词
 
    getWord2_nd(_First, Rest) = getWord_nd(Rest).

逐个取 Concordance中的 (Word,LinenumberSet) 组元及 LinenumberSet 中的 Linenumber， 就可以由文本词汇索引打印出一个索引，因为映射与集都是基于红黑树的，所有内容都自动排序好了： 

class predicates
    print : (outputStream Output, concordance Concordance).
clauses
    print(Output, Concordance) :-
        foreach tuple(Word, LinenumberSet) = Concordance:getAll_nd() do
            Output:writef("%:\n", Word),
            foreach Linenumber = LinenumberSet:getAll_nd() do
                Output:writef("   %\n", Linenumber)
            end foreach,
            Output:write("\n")
        end foreach.

参考

Retrieved from "https://wiki.visual-prolog.com/index.php?title=Collection_library（集合库）&oldid=4096"