Prolog 列表和运算符

2019 年 12 月 11 日

Prolog 列表和运算符

今天我们在这篇 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]
复制代码


这个简单的例子实际上为我们提供了很多很多的信息:


  1. 我们使用 [] 来”包裹”一些元素来表示列表.

  2. 列表可以含有各种不同类型的元素, 包括 atom, variable, complex term, number.

  3. 列表中的元素是可以重复的, 与集合不同.

  4. 列表可以是空的(empty list), 也就是 [].

  5. 列表是可以无限嵌套的.


列表的组成


Prolog 的列表与 Functional Programming 中的列表一样, 都由 headtail 组成.


  • head 就是列表的头部, 如果列表非空, 那么 head 就是列表的第一个元素.

  • tail 就是列表的尾部, 如果列表非空, 那么 tail 就是列表去掉第一个元素后剩下的元素构成的列表.


在这里有一点需要注意的就是 head 一定是元素, 而 tail 一定是列表, 这一点有很大的不同, 相信各位会在之后的科普中逐一了解.


既然我们介绍了列表的组成, 那么有一个非常重要的操作符我们不得不提, 这个操作符在操作列表中是非常关键的, 也就是 |.


这个操作符到底是怎么用呢, 我们来看一段代码就知道了:


?- [Head|Tail] = [1,2,3,4,5].
复制代码


这段代码会返回


Head = 1,Tail = [2, 3, 4, 5].
复制代码


我们可以看到 | 操作符将列表分成了两个部分, 分别是 HeadTail, | 成功地将列表分成了两个部分, 这就是它的作用, 而如果你在 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 就是其中之一.


我们怎么样才能实现它呢?


列表其实是一种递归的数据结构, 它由 headtail 组成, 而每一个非空的 tail 也都由另一个 newheadnewtail 构成, 在这里, 只需要不断提取列表的 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 的实现也应该是递归的, 先分析一下如何将一个列表反转.


  1. 如果需要 reverse 一个空列表, 那就直接返回一个空列表, 这是递归的边界条件.

  2. 如果需要 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).
复制代码


到这里我们对于这部分的介绍就到这里了.


本文转载自 Draveness 技术博客。


原文链接:https://draveness.me/prolog-lie-biao-he-yun-suan-fu-4


2019 年 12 月 11 日 15:26191

评论

发布
暂无评论
发现更多内容

week10

不在调上

week10作业1

第十周作业

刘卓

悄咪咪提高团队幸福感 & Surprise!

Kerwin

Java 开源项目

架构师训练营 week10

devfan

微服务架构

阿飞

微服务架构

week10 小结

Geek_196d0f

第十周学习总结

潜默闻雨

LeetCode题解:88. 合并两个有序数组,双指针+从前往后+使用新数组Copy,JavaScript,详细注释

Lee Chen

前端进阶训练营

centos中Anaconda的安装以及keras安装

我是程序员小贱

第十周命题作业

菲尼克斯

第十周学习总结

菲尼克斯

架构师训练营 W10 作业

telliex

SpringBoot 实战:一招实现结果的优雅响应

看山

springboot 实战

第十周学习总结

刘卓

[高冷面试]好不容易走到HR,结果被HR盘了,14题带走

我是程序员小贱

B 站收藏 10W+,GitHub 标星 6K+,肝了这门计算机速成课!

JackTian

GitHub 编程 程序员 B站 计算机基础

架构师训练营 W10 学习心得

telliex

架构师训练营 第十周 总结

CR

FastDFS不同步怎么破

心平气和

Binlog 同步 fastdfs

架构师训练营 第十周 作业

CR

架构师训练营 week10 - 学习总结

devfan

计算机网络怎么学?学会这几个工具有助你理解网络协议!

我是程序员小贱

一网打尽 Java 并发模型

cxuan

Java 后端 并发

计算机网络基础(十八)---传输层-TCP的流量控制

书旅

TCP 计算机网络 协议栈 网络层 流量控制

翻译: Effective Go (4)

申屠鹏会

golang 翻译

mini-vue之proxy代理

晓枫

vue.js

第10周作业

小胖子

微服务架构的一些思考

Acker飏

linux终端的快捷命令汇总

良知犹存

Linux

DDD

GalaxyCreater

架构

Prolog 列表和运算符-InfoQ