前往顾页
以后地位: 主页 > 收集编程 > Ajax实例教程 >

Prolog 列表和运算符知识详解

时候:2017-12-04 22:10来源:知行网www.zhixing123.cn 编辑:麦田守望者

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).

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

顶一下
(0)
0%
踩一下
(0)
0%
------分开线----------------------------
标签(Tag):Prolog Prolog列表 Prolog运算符
------分开线----------------------------
颁发评论
请自发遵循互联网相关的政策法规,严禁公布色情、暴力、革命的谈吐。
评价:
神色:
考证码:点击我更换图片
猜你感兴趣