Создание простейших структур данных с помощью функций в Python

[lair]

def _map(l,f):
    if null_seq(l):
        return null
    else:
        return make_pair(f(head(l)),_map(tail(l),f))

Что будет, если в списке 500 элементов? Десять тысяч? Миллион?

[Monnoroch]

Будет очень плохо.
Питон для этого не предназначен. На самом деле, список в том же хаскеле — это интерфейс навроде генератора. Не надо его использовать в качестве хранилища. А без ленивости это полный трэш.

[phantomit]

До меня уже написали, что «Все будет очень плохо». От себя еще могу добавить, что если в CPython была бы поддержка хвостовой рекурсии «из коробки», я бы написал _map (да и остальные функции) иначе.
Впрочем, в Python есть свои решения для поддержки TCO.

[lair]

Ну так может быть об этом надо написать в статье, потому как это типовая для функциональных языков проблема?

[gbezyuk]

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

[SirEdvin]

Немного LISP в Python?

[knagaev]

Не знаю, известно ли вам, что теперь этот курс (SICP) читают на Python, но на всякий случай вот ссылка на материалы
www-inst.eecs.berkeley.edu/~cs61a/fa11/61a-python/content/www/index.html
Надеюсь, поможет в освоении SICP на Python :)

[phantomit]

Спасибо за ссылку, не видел ранее этот курс. Просмотрел примеры — код какой-то совсем императивный.

def sum_naturals(n):
 """Sum the first n natural numbers.
 >>> sum_naturals(5)
 15
 """
 total, k = 0, 1
 while k <= n:
  total, k = total + k, k + 1
 return total

[knagaev]

А вы по какому признаку отличаете императивный код от декларативного? :)
В приведенном примере ведь простая итерация.
В функциональных языках итерации тоже можно использовать.
Там дальше как раз идёт описание работы с higher-order functions, и такой код совсем не мешает.

Это просто пример, скорректированный к синтаксису Python.
Вы наверняка сами уже оценили, что SICP рассказывает идеи, а имплементировать можно на любых языках, которые позволяют (например, поддерживают эти самые HOF).