> On 22 Jan 2019, at 20:19, Peter Ludemann <peter.l...@gmail.com
> The cost of accessing the end of a list is O(N) where N is the length of the list.
> Similarly, the cost of append(L1, L2, L) is also O(N) where N is the length of L1.
> you can define: last(List, Last) :- append(_, [Last], List).
> Difference lists reduce the cost of append to O(1). [This is only if the occurs check is turned off, of course.]
> Maybe there's a way of using difference lists for accessing the end of a list?
We can always derive a representation from difference lists that makes the last element explicit. For example:
last(List-Back+Last, Last) :- List \== Back.
append(List1-Back1+_, Back1-Back2+Last, List1-Back2+Last).
?- append(E-E+_, [1,2,3|T]-T+3, DL).
E = [1, 2, 3|T],
DL = [1, 2, 3|T]-T+3.
?- append(E-E+_, [1,2,3|T]-T+3, DL), append(DL, [4,5|T2]-T2+5, DL2), last(DL2, Last).
E = [1, 2, 3, 4, 5|T2],
T = [4, 5|T2],
DL = [1, 2, 3, 4, 5|T2]-[4, 5|T2]+3,
DL2 = [1, 2, 3, 4, 5|T2]-T2+5,
Last = 5.
The complexity that matters then becomes the complexity of constructing the List-Back+Last lists in the first place and likely how much conversion between these lists and normal lists would be required.
But I think you had something different in mind?
> reverse/2 is O(N) if the non-naive implementation is used, so that's an option if you need to access the end of the list a lot.
> There's no intrinsic reason why Prolog implementations couldn't do something more clever to make random list element access faster, but I don't know of any implementation that has done that (nor for Lisp, AFAIK, although Haskell has a special "++" operator, possibly because append can't be tail-recursive in functional languages). Similarly, association-lists could be O(1) [using hash tables] but O(log N) seems to be "good enough" most of the time.
> [FWIW, Python implementers have put a lot of effort into making both list/array and hash table access fast, but maybe there's less need for this in Prolog programs, especially as Python also uses hash tables for run-time resolving of non-local names.]
> On Monday, January 21, 2019 at 11:24:24 PM UTC-8, Dan wrote:
> I am curious, for very large lists, what is the cost of access the last element in a list?
> Does it require moving through the whole list, or is there an internal optimization here to get to the last one immediately?
> thank you,