[Lisp] [binary tree] [remove-node] как?

http://aima.cs.berkeley.edu/lisp/utilities/binary-tree.lisp

Ты думаешь я гуглом пользоваться не умею? :)

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

поищи книжицу purely functional data structures - там как раз все написано, правда не на лиспе

Довольно быстро нашёл книжку, спасибо, очень интересно, почитаю на досуге,
но при беглом просмотре не нашёл того чего искал :(

вообщем, после недолгого размышления, мой разум порадил нечто следующее :)

(defun move-it (from to)
  (if (second to)
      (list (first to)
            (move-it from (second to))
            (third to))
      (list (first to)
            from
            (third to))))

(defun remove-it (node)
  (cond ((and (second node) (third node)) (move-it (second node) (third node)))
        ((second node) (second node))
        ((third node) (third node))
        (t nil)))

(defun remove-node (tree key)
  (if (not tree) 
      nil
      (cond ((< key (first tree)) (list (first tree)
                                        (remove-node (second tree) key)
                                        (third tree)))
            ((> key (first tree)) (list (first tree)
                                        (second tree)
                                        (remove-node (third tree) key)))
            ((= key (first tree)) (remove-it tree)))))

как не крути, тут сплошная имеративщина :) прямо изо всех сторон торчит...

у меня уже закрадываются сомнения... а можно ли красивее? если кто-нить знает как, с удовольствием посмотрю :)

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

Да не, я и книгу нашёл... там как-то интересно, он-лайн просмотр гугловский сделан какой-то... но что-то я там не нашёл нужного мне.. надо будет посмотреть подробнее :)

http://lib.store.yahoo.net/lib/paulgraham/acl2.lisp

мб это подойдёт

А где нашёл? Я только диссер находил.

вот тут

http://books.google.ru/books?id=SxPzSTcTalAC&dq=purely+functional+data+st.. .

только это к сожалению он-лайн версия... но мне в принципе хватает чтобы почитать :)

Кстати очень удивился, когда не нашёл данной книги вот тут http://www.pdfchm.com/publisher/ ... жаль :(

Кстати посмотрел ссылку, в принципе там примерно то же что я написал тут, просто написано немного иначе :) там используется дополнительная "структура" для ноды, поэтому код выглядит несколько иначе... но в целом то же самое...

наверное диструктивныые действия с данными - не совсем функциональный подход :) поэтому всё это решается как и везде :)

За книгу спасибо.

Ну да, похоже. Функциональный подход работает с неизменяемыми структурами. Поэтому показалось странным, что Вы узрели императивщину в своём коде.

Да всегда пожалуйста :)

и кстати да... если посмотреть на код, то вроде всё "функционально" :) только ветвления и рекурсия :))

P.S.: нинада на ВЫ, очень прошу ;)

Об том и речь. Рекурсия и ветвления вполне функциональны, если, конечно, не считать что ФП=Unlambda :-D