Самоссылочные структуры данных в Лиспе / Схеме - PullRequest
Новая
       80

Самоссылочные структуры данных в Лиспе / Схеме

18 голосов
/ 03 марта 2009

Есть ли способ построить само-ссылочную структуру данных (скажем, граф с циклами) в lisp или схеме? Я никогда не думал об этом раньше, но, играя вокруг, я не могу найти простой способ сделать его из-за отсутствия способа сделать разрушительную модификацию. Является ли это просто существенным недостатком функциональных языков, и если да, то как насчет ленивых функциональных языков, таких как haskell?

Ответы [ 11 ]

0 голосов
/ 18 июня 2009

Хм, самоссылочные структуры данных в Lisp / Scheme и потоки SICP не упоминаются? Ну и подведем итог, == лениво оцененный список. Это может быть именно тот тип ссылки на себя, который вы намеревались, но это своего рода ссылка на себя.

Итак, cons-stream в SICP - это синтаксис, который задерживает оценку его аргументов. (cons-stream a b) немедленно вернется без оценки a или b и оценивает a или b только при вызове car-stream или cdr-stream

Из SICP, http://mitpress.mit.edu/sicp/full-text/sicp/book/node71.html: > 

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

Это определение говорит, что выдумка поток начинается с 0 и 1, такой что остальная часть потока может быть генерируется путем добавления выдумок к себе сдвинуто на одно место:

В этом случае 'fibs' присваивается объект, значение которого определяется лениво в терминах 'fibs'

Почти забыл упомянуть, что ленивые потоки живут в общедоступных библиотеках SRFI-40 или SRFI-41. Я думаю, что одна из этих двух должна быть доступна в самых популярных схемах

Страница:
...