今天我们在这篇 post 中介绍一下列表和运算符, 相信熟悉或者玩过函数式编程语言的朋友可能已经在函数式编程中掌握了列表, 而今天我带来的是逻辑式编程语言 Prolog 中的列表, 以及它的使用.
当然我还会在今天简单介绍一下 Prolog 中的运算符(Arithmetic). 不过这一部分的内容还是很简单的, 我们主要关注的部分就是 List.
列表
列表, 这个在函数式编程中非常常见的数据结构, 今天在逻辑式编程中也逐渐崭露头角.
什么是列表?
A list is just a plain old list of items.
列表其实就是一些项目的序列.
在 Prolog 中的列表也与其他语言中有所不同, 我们下面来举一个例子.
[hello, hi, bye, 1, [[[[1]]]], [], buy(book), [X, 2], 1]
这个简单的例子实际上为我们提供了很多很多的信息:
- 我们使用
[]来"包裹"一些元素来表示列表. - 列表可以含有各种不同类型的元素, 包括 atom, variable, complex term, number.
- 列表中的元素是可以重复的, 与集合不同.
- 列表可以是空的(empty list), 也就是
[]. - 列表是可以无限嵌套的.
列表的组成
Prolog 的列表与 Functional Programming 中的列表一样, 都由 head 和 tail 组成.
head就是列表的头部, 如果列表非空, 那么head就是列表的第一个元素.tail就是列表的尾部, 如果列表非空, 那么tail就是列表去掉第一个元素后剩下的元素构成的列表.
在这里有一点需要注意的就是 head 一定是元素, 而 tail 一定是列表, 这一点有很大的不同, 相信各位会在之后的科普中逐一了解.
既然我们介绍了列表的组成, 那么有一个非常重要的操作符我们不得不提, 这个操作符在操作列表中是非常关键的, 也就是 |.
这个操作符到底是怎么用呢, 我们来看一段代码就知道了:
?- [Head|Tail] = [1,2,3,4,5].
这段代码会返回
Head = 1,
Tail = [2, 3, 4, 5].
我们可以看到 | 操作符将列表分成了两个部分, 分别是 Head 和 Tail, | 成功地将列表分成了两个部分, 这就是它的作用, 而如果你在 Prolog 中输入如下查询:
?- [X,Y|Z] = [1,2,3,4,5].
X = 1,
Y = 2,
Z = [3, 4, 5].
这就是 | 更加高级的使用, 当然我们也可以匿名变量, 来代替一些我们不需要使用的变量:
?- [A,B,_,C,D|E] = [1,2,3,4,5].
A = 1,
B = 2,
C = 4,
D = 5,
E = [].
我们对于 | 的演示就先到这里, 接下来我们使用它来完成一些更加高级的操作.
列表的操作
我们经常需要各种各样的操作来处理列表, 而这样的操作往往都是递归的, 接下来将实现一些重要的列表中的递归操作.
- member
- append
- reverse
member
在列表的使用中, 需要来查看一个元素是否属于一个列表, 也就是 member(E,List). 在软件或者程序的构建中, 我们需要一些底层的抽象, 为实现更复杂的抽象制作出一些中间材料, 而 member/2 就是其中之一.
我们怎么样才能实现它呢?
列表其实是一种递归的数据结构, 它由 head 和 tail 组成, 而每一个非空的 tail 也都由另一个 newhead 和 newtail 构成, 在这里, 只需要不断提取列表的 head 然后与 X 对比, 直到列表为空或者找到匹配元素为止就完成了这个操作.
member(X,[X|T]).
member(X,[H|T]):-member(X,T).
这就是 member 的实现, 然后我们就可以再 Prolog 中测试一下了:
?- member(3,[1,2,3,4,5]).
true .
当然我们也可以使用匿名变量重写 member.
member(X,[X|_]).
member(X,[_|T]):-member(X,T).
append
append/3 在 Prolog 中是一个经典的操作, 它的三个参数都是列表, 我们先来演示一下 append 是怎样使用的.
append([1,2,3],[4,5,6],X).
X = [1, 2, 3, 4, 5, 6].
append 就是将第二个列表拼接到第一个列表的后面, 第三个参数就是返回的列表.
下面我们来定义一下 append(L1,L2,L3):
append([],L,L).
append([H|T],L2,[H|L3]):-append(T,L2,L3).
这是一个递归地定义, 它递归地将 L1 中的元素依次放到 L3 中直到 L1 为空时, 返回 L2. 这样整个 append 操作就完成了.
append([a,b,c],[1,2,3],_G510)
append([b,c], [1,2,3],_G523)
append([c], [1,2,3],_G554)
append([], [1,2,3],_G519)
append([], [1,2,3],[1,2,3])
append([c], [1,2,3],[c,1,2,3])
append([b,c], [1,2,3],[b,c,1,2,3])
append([]a,b,c,[1,2,3],[a,b,c,1,2,3])
X = [a, b, c, 1, 2, 3].
我们一步一步的追踪 append 操作的过程, 这样相信这个操作的过程就很容易理解了.
reverse
接下来我们介绍另一个断言(predicate) reverse . 它的作用就是将一个列表反转, 我们为什么要实现一个操作呢, 当操作列表的时候, 经常使用 [H|_] = L 来获取列表的头部, 但是列表的最后一个元素确实非常难以获得的, 这样就有了 reverse 操作诞生的原因.
reverse([1,2,3,4],Result).
Result = [4, 3, 2, 1].
在这里我们使用两种方法来实现 reverse
递归实现 (使用append)
reverse 的实现也应该是递归的, 先分析一下如何将一个列表反转.
- 如果需要
reverse一个空列表, 那就直接返回一个空列表, 这是递归的边界条件. - 如果需要
reverse一个列表[H|T], 只需要将反转[T]的结果接到H的后面.
reverse([],[]).
reverse([H|T],R) :-
reverse(T,RT),
append(RT,[H],R).
这个 reverse 的实现很简单, 但是它的效率很低, 因为 append 的运行效率就是极低的, 需要一种更加高效的 reverse 实现.
迭代实现 (使用 Acc)
更加优秀的方法就是使用一个累计器, 这里使用 Acc, 当你发现一个递归的断言或者说函数的效率十分的低效时, 使用迭代的方式, 添加一个累计器往往能成倍的提高程序或者代码的运行效率.
这里直接实现 reverse:
reverse([H|T],A,R) :-
reverse(T,[H|A],R).
reverse([],A,A).
reverse(L,R) :-
reverse(L,[],R).
我们先实现一个具有累计器版本的 reverse/3, 然后再实现正常版本的 reverse/2.
运算符
相信到目前为止, 已经对 Prolog 中的列表有了充分的了解, 而 Prolog 中的运算与其他的语言中有很大的不同, 如果你在 Prolog 中输入:
?- 6 = 2 + 4.
false.
Prolog 会返回 false 这是为什么呢, 因为 Prolog 在比较的时候不会对 + 两边的公式进行运算, 所以可以说是"字符串"之间的比较. 那在 Prolog 中如何比较两个公式呢, 我们使用 is.
?- 6 is 2 + 4.
true.
同样我们如果输入:
?- X = 3+2.
X = 3+2.
X 也不会被初始化为 5 而是 3+2.
当我们把 = 替换为 is 时, 才会得到想要的结果.
?- X is 3+2.
X = 5.
当然我们也可以使用 is 来定义一些更加复杂的断言,
add_3_and_double(X,Y) :-
Y is (X+3)*2.
然后我们问 Prolog:
?- add_3_and_double(1,X).
X = 8.
Prolog 与其他语言不同的地方就在于 is 的使用, 其他部分并没有什么显著的不同. 接下来将展示几个使用运算符和列表的断言.
len
len 是一个计算列表长度的断言, 它的实现很简单.
len([],0).
len([_|T],N) :-
len(T,X),
N is N+1.
当列表为空时就会返回 1, 是递归的边界条件, 而当列表不为空的时候, X 就会 +1.
max
max 会返回列表中最大的元素, 同样地, 使用两个操作符来实现这个断言.
accMax([H|T],A,Max):-
H > A,
accMax(T,H,Max).
accMax([H|T],A,Max):-
H=<A,
accMax(T,A,Max).
accMax([],A,A).
max(List,Max):-
[H|_] = List,
accMax(List,H,Max).
到这里我们对于这部分的介绍就到这里了.
转载申请
本作品采用知识共享署名 4.0 国际许可协议进行许可，转载时请注明原文链接，图片在使用时请保留全部内容，可适当缩放并在引用处附上图片所在的文章链接。
Go 语言设计与实现
各位读者朋友，很高兴大家通过本博客学习 Go 语言，感谢一路相伴！ 《Go语言设计与实现》 的纸质版图书已经上架京东，本书目前已经四印，印数超过 10,000 册，有需要的朋友请点击 链接 或者下面的图片购买。
