标签: difference-lists

我目前正在通过在线学习你的Haskell书籍的方式,并且已经到了一个章节,作者正在解释一些列表连接可能效率低下:例如

((((a ++ b) ++ c) ++ d) ++ e) ++ f

据说效率低下.作者提出的解决方案是使用定义为的"差异列表"

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

我很难理解为什么DiffList在某些情况下比简单串联更具计算效率.有人可以用简单的语言向我解释为什么上面的例子是如此低效,以及DiffList以什么方式解决了这个问题？

我只与Prolog合作了几天.我理解一些事情,但这真让我感到困惑.

我想要编写一个带有列表并将其展平的函数.

?- flatten([a,[b,c],[[d],[],[e]]],Xs).  
Xs = [a,b,c,d,e].                           % expected result

该函数取出列表的内部结构.

这是我到目前为止:

flatten2([],[]).
flatten2([Atom|ListTail],[Atom|RetList]) :-
      atom(Atom), flatten2(ListTail,RetList).
flatten2([List|ListTail],RetList) :-
      flatten2(List,RetList).

现在,这在我打电话时起作用:

?- flatten2([a,[b,c],[[d],[],[e]]], R).
R = [a,b,c,d,e].                         % works as expected!

但是当我打电话来查看我输入的列表是否已经展平时,将返回false而不是true:

?- flatten2([a,[b,c],[[d],[],[e]]], [a,b,c,d,e]).
false.                                   % BAD result!

为什么一方面工作,另一方面又不工作？我觉得我错过了很简单的事情.

如果我在Prolog中有一个列表,例如X = [1,2,3,4],如何将元素5添加到列表的末尾以使X = [1,2,3,4,5]？

append函数需要两个列表,即追加(A,B,C)以获得A和B连接到列表C.

我可以用临时列表Y = [1,2,3,4]和Z = [5]来做这个,然后做一个追加(Y,Z,X),但我不喜欢有一个临时列表.

通常的免责声明适用于此 - 这不是家庭作业,我只是在学习Prolog.

我正在尝试理解Prolog中的差异列表,但我正在努力实际实现一个,每次我尝试这样做,我得到一个列表列表,但这不是我想要的.我正在尝试实现一个追加谓词,但到目前为止运气不佳.很少有尝试,所有这些都无效.

app(X, Y, Z) :- Z = [X|Y].

?- app([a,b,c], [z], Z).
Z = [[a,b,c],z].

要么

app(X, Y, Z) :- Z = [X|Hole], Hole = Y.

与第一个结果相同(它们看起来基本相同).我在一本有效的书中有一个例子(尽管它不是谓词),我不明白其中的区别.X实例化到正确答案[a,b,c,z],与第二个例子有什么不同？

X = [a,b,c|Y], Y = [z].

我错过了什么？谢谢.

我正在考虑将二进制树展平为列表,以便进行后续处理.

我首先考虑使用(++)加入左右分支,但后来想到了更糟糕的情况需要O(n^2)时间.

然后我考虑向后构建列表,使用(:)在线性时间附加到前面.然而,我想如果我将这个列表发送到类似折叠的函数,它必须等到整个树遍历才能开始折叠,因此不能使用列表融合.

然后我想出了以下内容:

data Tree a = Node a (Tree a) (Tree a) | Tip

flatten :: Tree a -> [a]
flatten x = (flatten' x) []

flatten' :: Tree a -> [a] -> [a]
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l)))
flatten' Tip l = l

main = 
  putStrLn $ show $ flatten $ 
    (Node 2 (Node 1 Tip Tip) (Node 4 (Node …

我正在读这个问题的答案,

p(X) :- read(A), q(A,X-[]).

q(end,X-X) :- !.    
q(A,[A|X]-Y) :- read(B), q(B,X-Y).

上面的代码使用语法List-List.我有点理解发生了什么,但我想知道" - "符号/谓词到底是做什么的.此外,这个SWI是否具体？

该DLIST包包含DList数据类型,它有大量的实例,但不是Foldable或Traversable.在我看来,这是两个最"类似列表"的类型.是否存在DList不是这些类的实例的性能原因？

而且,封装确实实现foldr和unfoldr,但是没有其他的折叠功能.

"开放式列表"和"差异列表"之间有什么区别？

我一直在阅读有多大的差异列表,我希望从书中测试一些例子.但似乎你不能以与插入([1,2,3],[4,5],X)相同的方式传递列表作为输入,其中X = [1,2,3, 4,5].奇怪的是,我咨询过的任何一本书都没有提到这一点.

我在swipl上运行代码,我有兴趣测试差异追加谓词:

dapp(A-B,B-C,A-C).

和"旋转列表的第一个元素"谓词:

drotate([H|T]-T1,R-S) :- dapp(T-T1,[H|L]-L,R-S).

任何想法,我如何在swipl中测试这些谓词？

我正在阅读Prolog中关于上下文无关语法的本教程,他们在页面底部提到使用差异列表在Prolog中实现上下文无关语法,包括以下代码块:

s(X,Z):-  np(X,Y),  vp(Y,Z). 

np(X,Z):-  det(X,Y),  n(Y,Z). 

vp(X,Z):-    v(X,Y),  np(Y,Z). 
vp(X,Z):-    v(X,Z). 

det([the|W],W). 
det([a|W],W). 

n([woman|W],W). 
n([man|W],W). 

v([shoots|W],W).

它提到:

仔细考虑这些规则.例如,s规则说:我知道一对列表X和Z表示一个句子,如果(1)我可以消耗X并留下Y,而X和Y对代表一个名词短语,(2)然后我可以继续消耗Y而将Z留在后面,而YZ代表一个动词短语.np规则和第二个vp规则的工作方式类似.

和

将第一个列表视为需要消耗的内容(或者如果您愿意:输入列表),将第二个列表视为我们应该留下的内容(或:输出列表).从这个(相当程序上)的角度来看差异列表

[a,woman,shoots,a,man]  [].

Run Code Online (Sandbox Code Playgroud)

代表一个女人射杀一个男人的句子,因为它说:如果我消耗左边的所有符号,并留下右边的符号,那么我就有我感兴趣的句子.也就是说,我们感兴趣的句子是这两个列表的内容之间的差异.

这就是我们需要知道的差异列表来重写我们的识别器.如果我们只是牢记消费某些东西的想法,并留下一些东西,我们会获得以下认知:

作为解释,但这只是没有做任何事情来澄清这段代码给我.我知道它比使用更有效append/3,但至于消费和留下其他人的概念,它似乎比以前的append/3实现更令人困惑,我只是无法做出正面或反面.此外,当我将该代码复制并粘贴到Prolog可视化工具中以试图理解它时,可视化工具表示存在错误.谁能对此有所了解？