1 2:- module(arrays). % SEPIA header 3:- export 4 array_length/2, 5 array_to_list/2, 6 fetch/3, 7 list_to_array/2, 8 store/4. 9 10 11% File : ARRAYS.PL 12% Author : R.A.O'Keefe 13% Updated: 8 November 1983 14% Purpose: Updatable arrays in Prolog. 15 16% In this package an array is represented in the following notation 17% {1,2,3} is shown initially as 18% array([1|_1],[2|_2],[3|_3])+0 19% where the [1|_1] etc. are lists in which the most recent value for 20% the element comes last, and the +0 is a zero updates count. 21% Updating the 2nd element to a 5 for example would make the array into 22% array([1|_1],[2,5|_2],[3|_3])+1 23% Function "list_to_array" converts list e.g. [1,2,3,4] to array in 24% this format, "array_to_list" converts back. 25% fetch(+N,+A,-Elem) Fetches Nth element 26% store(+N,+A,+Elem,+NewA) Stores Elem at Nth element of A giving NewA 27 28/* These operations are fully described in 29 "Updatable Arrays in Prolog", R.A.O'Keefe, DAI Working Paper 150. 30 Note that store(Index, Old, Elem, New) sometimes side-effects Old and 31 sometimes doesn't; you cannot rely on Old remaining unchanged. 32 (i.e. uninstantiated arguments in Old may become instantiated.) 33 This is NOT an example of logic programming. For a logic programming 34 solution (with cost O(lgN) rather O(1)) see Trees.Pl. 35*/ 36 37array_length(Array+_, Length) :- 38 functor(Array, array, Length). 39 40 41array_to_list(Array+_, List) :- 42 Array =.. [array|Wrapped], 43 un_wrap(Wrapped, List). 44 45un_wrap([History|Histories], [Element|Elements]) :- 46 get_last(History, Element), 47 !, 48 un_wrap(Histories, Elements). 49 50un_wrap([], []). 51 52 53fetch(Index, Array+_, Element) :- 54 arg(Index, Array, History), 55 get_last(History, Element). 56 57get_last([Head|Tail], Element) :- 58 var(Tail), 59 !, 60 Element = Head. 61 62get_last([_|Tail], Element) :- 63 get_last(Tail, Element). 64 65 66list_to_array(List, Array+0) :- 67 wrap_up(List, Wrapped), 68 Array =.. [array|Wrapped]. 69 70wrap_up([Element|Elements], [[Element|_]|Wrapped]) :- !, 71 wrap_up(Elements, Wrapped). 72 73wrap_up([], []). 74 75 76store(Index, Array+Updates, Element, NewArray+NewUpdates) :- 77 functor(Array, array, Length), 78 arg(Index, Array, History), 79 put_last(History, Element), 80 K is Updates+1, 81 !, 82 store(Length, K, NewUpdates, Array, NewArray). 83 84store(N, N, 0, Old, New) :- !, 85 Old =.. [array|OldList], 86 un_wrap(OldList, MidList), 87 !, 88 wrap_up(MidList, NewList), 89 New =.. [array|NewList]. 90 91store(_, U, U, Array, Array). 92 93put_last(History, Element) :- 94 var(History), 95 !, 96 History = [Element|_]. 97put_last([_|History], Element) :- 98 put_last(History, Element). 99 100