SICP по-русски

Иногда возникает ощущение, что авторы СИКП (Структуры и интерпретации компьютерных программ) специально упрощают нам жизнь, делая большую часть упражнения за нас. В данном случае структура процедуры, строящей множество всех подмножеств уже задана. Нам нужно лишь вписать маленькую часть. Логика процедуры следующая. Чтобы получить все подмножества множества из N элементов, выделим первый элемент, получим все подмножества […]

Обобщение совершенно естественно получается из любого варианта описания процедуры square-tree или scale-tree. Вот вариант tree-map без использования map: (define (tree-map proc tree)     (cond ((null? tree) null)           ((not (pair? tree)) (proc tree))           (else (cons (tree-map proc (car tree)) (tree-map proc (cdr tree)))))) А этот вариант реализации tree-map процедуру map использует: (define (tree-map proc tree) […]

Определения процедуры square-tree (как прямое, так и с применением map) аналогичны определениям scale-tree, рассмотренным в основном тексте книги, поэтому подробно разбирать, как они построены, не буду, а приведу только код: (define (square-tree tree)   (cond ((null? tree) null)         ((not (pair? tree)) (square tree))         (else (cons (square-tree (car tree))                     (square-tree (cdr tree)))))) (define […]

Книга СИКП абсолютно великолепна кругом затрагиваемых вопросов. В упражнении 2.29 нас знакомят с понятием мобиля, которое интересно само по себе как демонстрация физических явлений. Баланс и устойчивое равновесие неустойчивой фигуры завораживает. Недаром мобилями весьма интересуются дети в самом раннем возрасте. Почитать про мобили и кинетическую скульптуру в целом можно в английской википедии. Приступим к упражнению. […]

Процедура fringe будет производить обход дерева в глубину слева направо и собирать узлы в порядке обхода в один список. Ее структура очень похожа на структуру count-leaves. При рассмотрении каждого узла также рассматриваются три случая: пустое дерево, листовой элемент и нелистовой элемент (поддерево). Для пустого дерева на входе мы генерируем пустой список на выходе. Для листового […]

Определение процедуры reverse можно посмотреть в решении упражнения 2.18. В определении deep-reverse все остается прежним, кроме того, что при переносе очередного элемента из исходного списка в результирующий мы “реверсируем” этот элемент (процедура reverse-it). Реверсирование элемента для списка означает deep-reverse для него, а реверсирование атомарного значения (не списка) возвращает само это значение. (define (deep-reverse items)   (define […]

Вы, конечно же, знаете, что видео лекций по SICP, читавшихся Абельсоном и Сассманом для работников Hewlett Packard в 1986 году, выложены в публичный доступ и доступны для скачивания всем желающим. Эти 20 лекций охватывают материал всей книги (правда, первого издания) и отзывы о них очень хорошие. Проблема лично для меня заключается в том, что даже […]

В этом упражнении рассматриваются три доступные нам на данный момент операции для конструирования списков. Задача упражнения – твердо осознать разницу между этими операциями и применять ту или иную из них именно тогда, когда нужно. append объединяет элементы списков в один список, приписывая второй список позади первого: (1 2 3 4 5 6) cons возвращает список, […]

Это упражнение требует понимания принципов построения списков и повышенной внимательности. Очень рекомендую выполнить его даже тем, кому кажется, что оно тривиально. Это просветляет. Итак, начнем с простого. Для списка (1 3 (5 7) 9) нам нужно сначала дважды выполнить cdr, чтобы получить ((5 7) 9), затем взять от результата car, получив (5 7), затем вновь […]

Итак, нам задано выражение (list 1 (list 2 (list 3 4))). Начнем с вопроса о том, что напечатает интерпретатор. Мы знаем, что интерпретатор печатает выражения вида (list 1 2 3) как (1 2 3). В случае вложенных списков элементами главного списка будут являться другие списки. Фактически интерпретатор напечатает само выражение за исключением имен list. В нашем […]