VPF::Разностные списки - Форум программистов

DSan

Дата 2.5.2007, 01:21 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 10.2.2007

Репутация: нет
Всего: нет

Как можно представить разностные списки в Turbo Prolog для дальнейшей с ними работы.

Не откажусь для наглядности от какого-нибудь простенького примерчика работы со списками при помощи разностных списков (еще называют разностными парами).
Для TP так и не смог найти примеров, только для VIP, но там другая история.

Artemios

Дата 3.5.2007, 14:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 6
Всего: 50

Только не знаю, подойдет ли хоть что-то отсюда для Турбо (для swi-prolog подходит), а вообще вот:

Цитата

Один интересный трюк изобретенный Пролог-программистами для повышения эффективности программ - неполные структуры данных. Например, неполный список отличается от обычного тем, что завершается не пустым списком, а свободной переменной. Такой список возвращается предикатом member при запросах вида

    ?- member(1,L).
    L = [1|_G208]
    Yes

    ?- member(1,L), member(2,L).

    L = [1, 2|_G226]
    Yes

Неполные списки часто используются для организации небольших словарей. Доступ к словарю осуществляется процедурой lookup, которая возвращает значение соответствующее ключу или добавляет пару ключ-значение в словарь. Простейшее определение этой процедуры

    lookup(Key,Dict,Val):- member(Key-Val,Dict).

Например

    ?- lookup(a,Dict,1),lookup(b,Dict,2),lookup(a,Dict,A).

    Dict = [a-1, b-2|_G268]
    A = 1

    Yes

К неполному списку можно очень быстро присоединить другой список, присваивая его переменной, завершающей неполный список. Правда, сделать это можно только один раз.

    ?- X=[1,2,3|A],A=[4,5,6].

    X = [1, 2, 3, 4, 5, 6]
    A = [4, 5, 6]
    Yes

Но если присоединяемый список тоже неполный, можно присоединить к нему еще один список и т.д.

    ?- A=[1,2,3|B], B=[4,5,6|C], C=[7,8,9].

    A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    B = [4, 5, 6, 7, 8, 9]
    C = [7, 8, 9]
    Yes

Мы можем оформить эту идею, определив отношение

    append_incomplete(A,B,B,C,A,C).

    ?- append_incomplete([1,2,3|A],A,[4,5,6|B],B,C,[]).

    A = [4, 5, 6]
    B = []
    C = [1, 2, 3, 4, 5, 6]

    Yes

Естественно объединить список и относящуюся к нему переменную в одну структуру. Такие структуры называют разностными списками и записывают обычно в виде [1,2,3|A]-A. В этих обозначениях определение соединения примет вид.

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

Название "разностный список" объясняется тем, что структура A-B представляет список, получающийся при "вычитании" списка B из списка A. Например [1,2,3,4,5]-[4,5] и  [1,2,3]-[] представляют один и тот же список [1,2,3], а выражение  [1,2,3|A]-A -наиболее общий образец такого представления. При такой интерпретации определение append_d совершенно очевидно: A-B + B-C = A-C.

Разностные списки полезны главным образом в тех случаях, когда создается большое количество коротких списков, которые затем объединяются в один. Возьмем простой и хорошо знакомый пример. При "наивном" обращении к списку многократно присоединяется  список из одного элемента.

    reverse([], []).
    reverse([H|T],L) :- reverse(T,S), append(S,[H],L).

Попробуем заменить результат процедуры разностным списком. Процедура reverse_d создает разностный список, представляющий обращение данного списка.

    reverse_d([], X-X).
    reverse_d([H|T],L-L1) :- reverse_d(T,S-S1), append_d(S-S1,[H|X]-X,L-L1).

Используя определение append_d, можно переписать второе правило

    reverse_d([H|T],L-L1) :- reverse_d(T,S-S1), S1=[H|X],L=S,L1=X.

или, выполнив подстановки

    reverse_d([H|T],L-X) :- reverse_d(T,L-[H|X]).

Собирая все вместе, получаем

    reverse(L,R):-  reverse_d(L,R-[]).

    reverse_d([],X-X).
    reverse_d([H|T],L-X) :- reverse_d(T,L-[H|X]).

Можно заметить, что это определение практически эквивалентно процедуре с накопителем. Вообще разностные списки часто позволяют получать программы, аналогичные использующим накопители, но имеющие ясный декларативный смысл.

Еще один типичный пример - создание списка узлов двоичного дерева. Прямая реализация

    nodes(empty,[]).
    nodes(bt(X,Lt,Rt), [X|Xs]) :-
        nodes(Lt,Ls),
        nodes(Rt,Rs),
        append(Ls,Rs,Xs).

неэффективна из-за большого количества операций соединения. Используя разностные списки, можно избавится от них и значительно повысить скорость.

    nodes(T,L):-nodes_d(T,L-[]).

    nodes_d(empty,L-L).
    nodes_d(bt(X,Lt,Rt),[X|L]-Z) :-
        nodes_d(Lt,L-Y),
        nodes_d(Rt,Y-Z).

взято с:
Декларативное программирование (И.А. Дехтяренко)

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

DSan

Дата 4.5.2007, 22:52 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 10.2.2007

Репутация: нет
Всего: нет

Спасибо, конечно, но самое плохое что он такое, например:
reverse_d([],X-X).
не понимает и ругается.
Поэтому и встает вопрос, а какое ему нужно представление разностных списков?.

Artemios

Дата 5.5.2007, 03:17 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 6
Всего: 50

Турбы нет, проверить не могу... Возможно, он не хочет воспринимать знак "-" как инфиксный функтор, а воспринимает его как бинарную операцию? Если так -- можно построить собственный аналог разностных списков введением какого-либо функтора.
например вместо X-Y (что на "нормальном" прологе эквивалентно -(X,Y)) писать как-нибудь так: g(X,Y)

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Prolog \| Следующая тема »