Наверное многие заметили, что в последние эдак пару лет интерес к штуке под названием "функциональное программирование" растет прямо на глазах. Там и тут все чаще люди с придыханием говорят слова "Хаскел" и "Эрланг", а также периодически вспоминают, что вот был еще такой "Лисп" — это да, это был настоящий язык!

Наслушавшись все этого, я решил, что это интересно и полезно, и купил книжку "Структура и интерпретация компьютерных программ". Книжка хорошая! Несколько занудная в последних главах, но в начале очень четко расставляет по местам, что такое функциональный подход, что такое императивный, и когда какой нужен.

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

Итак, задачка — вывести на веб-страницу древовидный список комментариев. Комментарии хранятся в одной таблице примерно такой структуры:

class Comment(Model):
    text = TextField()
    parent = ForeignKey('self', null=True)

То есть вся иерархия обеспечивается ссылкой на другой комментарий, которая может быть пустой — вполне стандартное решение.

Код для вывода я вытянул из одного своего старого проекта, и выглядит он примерно так:

def comments():
  comment_list = get_from_db()

  def render_comment(comment):

    result = '<li>' + render_with_template(comment)

    replies = [c for c in comment_list if c.reply_to == comment]
    if replies:
      replies_strs = [render_comment(r) for r in replies]
      result += '<ol>' + ''.join(replies_strs) + '</ol>'

    result += '</li>'
    comment_list.remove(comment)
    return result

  output = ''
  while comment_list:
    output += render_comment(comment_list[0])
  return '<ol>' + output + '</ol>'

Чтобы было понятней, что для чего:

  1. Сначала из базы вытягиваются все нужные комментарии (к одной статье, например).
  2. Дальше определяется рекурсивная функция вывода одного комментария, которая:
    1. Сначала как-то там через шаблон выводит тело комментария.
    2. Получает список комментариев — ответов на переданный
    3. Вызывает себя же для каждого такого ответа
    4. Удаляет переданный комментарий из первоначального списка
  3. Для вывода комментариев, не являющихся ответами на другие (корневых, то есть), используется нехитрый цикл, в котором выводится первый комментарий из общего списка, пока тот не опустеет.

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

replies = [render_comment(c) for c in comment_list if c.reply_to == comment]
if replies:
  result += '<ol>' + ''.join(replies) + '</ol>'

Видите ошибку?

Если видите — завидую. Я ее увидел только тогда, когда при попытке вывести некое тестовое дерево комментариев увидел, что его структура полностью сломана. То есть все выводится, но не в тех местах и не в той вложенности, которая нужна. Потом мне потребовалась куча отладочного вывода, чтобы таки докопаться, что происходит.

Корень зла в том, что render_comment помимо своего основного назначения — выдачи отрендереннной строчки — обладает еще и тем самым побочным эффектом: она изменяет список comment_list. Раньше, когда я составлял новый список replies, и бежал по нему, все работало хорошо. А тут я бегу по comment_list, попутно удаляя из него значения. Соответственно итератор перешагивал часть комментариев, и они не учитывались как ответы, а выводились потом в корне.

В итоге я устранил всю, как у нас говорят, "галимую императивщину" и вместо того, чтобы выводить корневые комментарии в отдельном цикле, просто обобщил рекурсивную render_comment, чтобы она умела выводить и их тоже. Все стало выглядеть слегка проще:

def comments():
  comment_list = get_from_db()

  def render_comment(comment):

    result = '<li>' + render_with_template(comment)

    replies = [render_comment(c) for c in comment_list if c.reply_to == comment]
    if replies:
      result += '<ol>' + ''.join(replies) + '</ol>'

    result += '</li>'
    return result

  return '<ol>' + render_comment(None) + '</ol>'

Комментарии: 8 (особо ценных: 1)

  1. Сергей Ткачук

    Особо ценный комментарий

    Если кому-то интересно, то оригинал этой книжки можно почитать: http://mitpress.mit.edu/sicp/full-text/book/book.html

    Кстати, если пойти до конца и извести вот это "result +=", то получится еще проще и наглядней:

    def comments():
      comment_list = get_from_db()
    
      def render_replies(comment):
        replies = [render_comment(c) for c in comment_list if c.reply_to == comment]
        return replies and '<ol>' + ''.join(replies) + '</ol>' or ''
    
      def render_comment(comment):
        return '<li>' + render_with_template(comment) + render_replies(comment) + '</li>'
    
      return '<ol>' + render_comment(None) + '</ol>'
    

    P.S. Ошибку я увидел :-)

  2. buriy

    В итоге я устранил всю, как у нас говорят, “галимую императивщину” ....

    А вообще, я правильно понял, что это на самом деле пост о вреде книжек по функциональному программированию на неокрепшие программистские умы?)))

  3. Майк

    Я в подобной задаче решил пожертвовать красотой хранения в базе, и приписал всем комментариям "порядок расположения":
    001
    001001
    001002
    002

    Легко определяется порядок вывода на страницу и требуемый отсутп.

  4. koder

    Когда я начинал писать на питоне, я как-то написал прим. такой код

    def MkNewList(node = []):
        node.append(len(node))
        return node
    

    Как, наверно, догадались все кто знает питон - ф-ция работала очень неважно. О сюда я сделал вывод что в интерпретатор питона - глючная гадость. А ведь проблема то была в неровных
    верхних конечностях.

    Чистый функциональный стиль (а именно ф-ции без
    побочных эффектов) предъявляет слишком жесткие требования к оперативной памяти(потому как Вы не
    можете изменить объект - можно только создать измененную копию) + постоянные затраты на копирование. И, как результат, сложно что-то толковое на нем сделать , иначе не придумывали бы монады и прочую императивщину.

    P.S. А еще многие очень не любят указатели в С,
    и говорят что это БОЛЬШАЯ ПРОБЛЕМА. Я тоже думаю
    что это проблема.... с руками.

    P.P.S. Замените все list на tuple и наслаждайтесь функциональным стилем ))).

  5. Владимир Спаков

    Лисп - это действительно вещь.

    Мы ещё изучали целевые языки типа Пролога. Действительно искуственный интеллект ))

  6. Oleg Andreev

    Деревья траверсить без побочных эффектов сам бог велел (на почти те же грабли я наступал пару лет назад). Гораздо смешнее делать сервер с веб-приложением многопоточным (чтобы сэкономить пару гигов памяти). Каждая явная синхронизация доступа к общим ресурсам - признак недостаточной "функциональности". В этом случае наиболее интересно слизывать дизайн с Эрланга.

  7. VictorS

    Мне тут тоже нужно было сделать нечто подобное, только на C#. Мне просто нужно было удалить из дерева хранящегося в таблице (DataTable) пустые папки (в дереве 2 типа элементов: folder и entry), и я вначале сделал это используя цикл foreach по строкам таблицы, т.е. даже без ручного использования индексов строк. Удалял строки прямо в цикле, а потом сильно удивился когда прога выдала что индекс выходит за пределы размерности таблицы. Но удивился не на долго, т.к. коллега пол года назад сталкивался с подобной задачей и я сразу понял в чем ошибка. Пришлось создавать отдельный список, куда я ложил строки которые нужно удалить, а потом вторым циклом удалял их из таблицы.

  8. zahardzhan

    Чистый функциональный стиль (а именно ф-ции без побочных эффектов) предъявляет слишком жесткие требования к оперативной памяти(потому как Вы не можете изменить объект - можно только создать измененную копию) + постоянные затраты на копирование. И, как результат, сложно что-то толковое на нем сделать , иначе не придумывали бы монады и прочую императивщину.

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

Добавить комментарий