Я думаю, у вас есть идея, что интерпретатор Prolog рассматривает списки различий как нечто особенное. Это не так: Prolog не осознает концепцию разностного списка (и почти каждого понятия, кроме синтаксического сахара ). Он видит только:
L=-(|(a, |(b, |(c, |(d, |(e, []))))), |(d, |(e, [])))
где -/2 и |/2 функторы и a, b, c, d, e и [] являются константами.
списки Разница просто метод программирования (как, например, динамического программирования представляет собой метод, а компилятор не может обнаружить ни лечить динамические программы программирования по-разному). Он используется для эффективной унификации (частично) неизолированной части в выражении.
Скажите, что вы хотите append/3 два списка. Вы можете сделать это следующим образом:
%append(A,B,C).
append([],L,L).
append([H|T],L,[H|B]) :-
append(T,L,B).
Но это работает в O (N): сначала нужно перебирать весь первый список. Если этот список содержит тысячи элементов, это займет много времени.
Теперь вы можете определить себя контракт, который вы будете кормить append_diff/3 не только список, но кортеж -(List,Tail) где List является ссылкой на начало списка, а Tail является ссылкой на конце не унифицированный список. Примерами структур, которые удовлетворяют этому требованию, являются Tail-Tail, [a|Tail]-Tail, [1,4,2,5|Tail]-Tail.
Теперь вы можете эффективно append_diff/3 в O (1) с:
append_diff(H1-T1,T1-T2,H1-T2).
Почему? Потому что вы объединяете незанятый хвост первого списка со вторым списком. Теперь необработанный хвост вторых списков становится хвостом окончательного списка.Так возьмите, например:
append_diff([a|T1]-T1,[1,4,2,5|T2]-T2,L).
При вызове предиката, как вы видите выше, T1 унифицируют с [1,4,2,5|T2], так что теперь первый список коллапсирует [a|[1,4,2,5|T2]] или короче [a,1,4,2,5|T2], так как у нас также есть ссылка на T2, мы можем «вернуться» (в Прологе ничего нет ), [a,1,4,2,5|T2]-T2: новый список различий с открытым хвостом T2. Но это только потому, что вы даете - особого смысл себя: для Пролога - это просто -, это не минус, он не вычисляет разницы, и т.д. Пролог делает не придает семантике к функторам. Если бы вы использовали + вместо -, это не имело бы ни малейшей разницы.
Итак, чтобы вернуться к вашему вопросу: вы просто заявляете Prolog, что L = -([a,b,c,d,e],[d,e]) и позже заявите, что L = [a,b,c]. Теперь ясно, что эти два выражения не могут быть унифицированы. Итак, Пролог говорит false.
Ключом к чтению этого раздела является слово * present *. Если вы посмотрите в книге, когда примеры можно использовать с интерпретатором ACA верхнего уровня, они имеют префикс '? -'. В этом разделе он читает «Итак, список [a, b, c] может быть представлен, например, [a, b, c] - [] или [a, b, c, d, e] - [d, e] или [a, b, c, d, e | T] - [d, e | T] или [a, b, c | T] -T, где T - любой список. «Таким образом, это не пример запустить с верхним уровнем, но примеры, которые * представляют * то, что вы должны думать, таким образом, ошибка при использовании его в качестве входа на верхнем уровне. –
'L' не могут быть' [a, b, c | [d, e]] - [d, e] 'и' [a, b, c] '. Это две разные структуры. – lurker
@ lurker Я вижу это сейчас, но, как поясняется в комментариях, вероятно, поэтому я не вижу практического преимущества списка различий. Вам всегда понадобится шаг * finalize *, предложенный Виллемом Ван Онем, если вы хотите использовать объединенный список. –