标签: difference-lists

我正在学习haskell,我看到的函数定义是:

quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
                 where less = filter (< x) xs
                       equal = filter (== x) xs
                       more = filter (> x) xs

是否可以只用一次遍历列表而不是3来编写它？

考虑以下程序,一个使用差异列表,另一个不是:

reverse1(List1,R) :- rev1(List1, R-[]).
rev1([], A-A).
rev1([H|T], C-A) :-rev1(T, C - [H|A]).

reverse2(List1,R) :- rev2(List1, R, []).
rev2([], A, A).
rev2([H|T], C, A) :- rev2(T, C, [H|A]).

由于两者都做同样的事情,使用差异列表有什么好处？

我想将不完整的列表转换为差异列表,反之亦然.

这是将常规列表转换为差异的代码:

reg2diff(L,X-Y):-append(L,Y,X).

我该怎么走另一个方向？

我无法理解差异列表,特别是在这个谓词中:

palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
   palindrome(A, B),
   B=[C|D].

谁能帮我跟踪发生的事情？

这个问题涉及书中第3章的内容:Prolog,Clocksin和Mellish编程,Ed 5

在本书的第72页中,显示了使用差异列表的程序:

partsOf(X,P):- partsacc(X,P,Hole) , Hole=[].

partsacc(X,[X|Hole],Hole):-basicpart(X).
partsacc(X,P,Hole):- assembly(X,Subparts), partsacclist(Subparts, P, Hole).

partsacclist([],Hole,Hole).
partsacclist([P|T], Total, Hole):- partsacc(P,Total,Hole1), partsacclist(T,Hole1,Hole).

在许多在线教程中,使用了以下使用" - "的格式,例如::

append([ A , B , C | R1 ] – R1 , [ D , E | R2 ] – R2 , R3)

我的问题是:

1. 这两个表示之间有什么区别(使用 - 而不是使用它)

2. 在哪些情况下最好使用它们中的每一种？

谢谢

在Haskell，差异表中的感

[a]使用有效的串联操作表示列表

似乎是在功能组成上实现的。

但是，功能和（动态）功能组合也必须使用数据结构以某种方式在计算机的内存中表示，这提出了一个问题，即在不使用功能组合的情况下如何在Haskell中实现dlist，而是通过一些基本的纯功能实现基于节点的数据结构。如何实现与功能组合相同的性能保证？

我正在为Prolog(SWI)做作业,但无法弄清楚如何完成这项工作:

我有仿函数:

palindrome([]).
palindrome([_]).
palindrome([A|T]) :-
      append(Middle,[A],T),
      palindrome(Middle).

它告诉给定的列表是否是回文.

对于我的作业,我必须编写一个palindrome/2没有append/3和有差异列表的仿函数.

我知道差异列表是一种形式[Y|X]-X,但我不明白如何使用它以及如何替换append仿函数.

有人可以向我解释一下吗？

我有一个新类型来表示Hughes的列表(即列表构造):

newtype Hughes a = Hughes {unHughes :: [a] -> [a]}

有一些功能可以解决它:

mkHughes :: [a] -> Hughes a
mkHughes = Hughes . (++)

runHughes :: Hughes a -> [a]
runHughes h = unHughes h []

的Monoid实例是一样容易与上述功能是:

instance Monoid (Hughes a) where
    mempty = Hughes id
    mappend (Hughes f) (Hughes g) = Hughes (f . g)

......但是当我到达Functor和Applicative实例时出现了麻烦.这是我到目前为止所提出的:

instance Functor Hughes where
    fmap f (Hughes h) = Hughes $ unsafeCoerce $ fmap f . h

instance …

差异列表是否可以“解决”变量在序言中不可变的事实？

即如果我实现使用差异列表追加：

diff_append(OpenList, Hole, L2) :-
    Hole = L2.

然后运行：

X=[a,b,c|Hole], diff_append(X, Hole, [d,e,f]).

在某种程度上，X已用作可变变量。就我们的意图和目的而言，它已经改变了吗？

换句话说，我们能够修改X（可变），而不必构造新列表（例如Z（不可变）），这使得差异列表具有吸引力。那么为什么不仅仅拥有可变变量呢？

更新：

diff_append2(OpenList-Hole,L2):-
    Hole=L2.

X=[a,b,c|Ho]-Ho,diff_append2(X,[d,e,f]).

当我阅读第 13 章时，Real World Haskell我想到了Difference Lists.
作者说，在命令式语言中，如果我们想将一个元素附加到列表中，成本将是O(1)因为我们将保留一个指向最后一个元素的指针。但是在 Haskell 中，我们有immutable对象，所以我们每次都需要遍历列表并将元素追加到末尾，因此0(n).

而不是[1,2,3]++[4]++[5]
我们可以使用部分应用程序：(++4).(++5) [1,2,3]。

我不明白这是怎么更有效，因为：
-当我这样做(++[5]) [1,2,3]它仍然是O(n)接着又0(n)为(++4)

引用

There are two very interesting things about this approach. The first is that the cost of a partial application is constant, so the cost of many partial applications is linear. The second is that when we finally provide a [] value to
unlock the …