Списки из lambda-функций

Original author: Steve Losh
  • Translation
Примечание переводчика: Оригинал здесь. Все примеры в оригинале написаны на JavaScript, но я решил перевести их на Scheme. Уверен, менее понятно не стало, но зато видна вся красота этого языка.
UPD: добавил ко всем примерам справа еще и оригинальные примеры на JavaScript.


Если закрыть глаза на практическую сторону компьютеров — размер, вес, цену, тепло и т.п., что же на самом деле должен уметь язык программирования? Давайте исследуем этот вопрос.

Для понимания примеров в этой статье необходимы базовые понятия о функциях в LISP (Scheme). Если вы понимаете, что напечатает этот код, можно смело читать дальше:

(define x 10)

(define (f y)
    (display x) (newline)
    (display y) (newline)
)

(define g f)
(f 1)
(g 2)

var x = 10;

var f = function(y) {
    console.log(x);
    console.log(y);
}

var g = f;

f(1);
g(2);


Эта статья — просто разминка для мозгов, а не то, что можно было бы использовать в реальном коде. Но как гитарист играет гаммы, которые он никогда не использует в настоящей песне, так же и программистам стоит разминать свои мозги время от времени.

Я буду использовать Scheme для демонстрации, но подойдет и любой другой язык, поддерживающий функции как объекты первого класса (first-class functions), и лексическую область видимости (замыкания, в основном).

Если вы уже видели такие штуки (может, в SICP или The Little Schemer), вам стоит просто пробежаться по коду в поисках чего-нибудь нового для себя.

Если вы не видели ничего подобного ранее, для вас есть кое-что вкусненькое. В первый раз всё будет выглядеть чрезвычайно странно. Продвигайтесь медленно. Переходите к следующей части, только поняв предыдущую. Концепции, изложенные здесь, могут показаться не интуитивными, но они построены из очень простых частей.

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



1 Списки



Ну что ж, начнём! Один из самых часто выполняемых программистом процессов — группировка данных. В Scheme для этого есть встроенные списки (иначе бы он не был LISP’ом ;):

(define names (list "Alice" "Bob" "Candice"))

var names = ["Alice", "Bob", "Candice"];


Но что если бы в Scheme не было бы списков? Смогли бы мы сделать их, или что-то похожее на них, самостоятельно?

Чтобы ответить на этот вопрос, давайте подумаем, какой минимальный набор вещей нам нужен, чтобы создать что-то типа списка. Есть множество способов сделать это, но мы рассмотрим только один из них.

Для работы со списком нам необходимы четыре вещи:

  • Понятие «пустого списка»
  • Способ добавить элемент в начало списка
  • Способ получить первый элемент списка
  • Способ получить всё, кроме первого элемента списка


Если есть эти четыре вещи, мы можем построить на их основе всё, что пожелаем. Например, чтобы создать список из одного элемента, можно добавить этот элемент в начало пустого списка.

Существует много способов реализовать эти четыре части — я же буду использовать функции. Вот их эскиз:

(define empty_list '())
(define (prepend el lst) ...)
(define (head lst) ...)
(define (tail lst) ...)
(define (is_empty lst) ...)
var empty_list = null;

var prepend = function(el, list) {
    // ...
};

var head = function(list) {
    // ...
};

var tail = function(list) {
    // ...
};

var is_empty = function(list) {
    // ...
};

Вот описания каждого из этих определений.

empty_list это специальное значение, представляющие список из нуля элементов. Оно может чем угодно, поэтому я буду использовать стандартный ’() из Scheme. Мы ещё вернёмся к этому позже.

(prepend 1 some_list) вернёт новый список, выглядящий как старый с 1, вставленной в его начало. Так, если мы хотим создать список из чисел 1 и 2, мы можем написать (prepend 1 (prepend 2 empty_list)), или «добавить 2 к результату добавления 1 к пустому списку»

(head some_list) вернёт первый элемент в списке. Результат head от пустого списка не определён, так что надо быть аккуратными и не делать этого!

(tail some_list) вернёт новый список, выглядящий как старый без первого элемента. И снова, вызов tail от пустого списка всё испортит.

(is_empty some_list) вернёт #t, если данный список является пустым и #f в противном случае.

Как только у нас есть эти четыре функции (плюс специальное значение для пустого списка), мы можем начать строить вещи на их основе, так что давайте узнаем как их реализовать!

1.1 Списки из If


Вы наверно можете подумать, что можно использовать cons, car и cdr, но эта статья — эксперимент по поиску того, что нам действительно нужно, давайте не будем использовать встроенные возможности языка, если этого можно избежать.

Итак, если мы не хотим использовать возможности языка, что нам остаётся? Ну, пока что у нас есть только функции (и ’()), так что давайте попробуем их!

Вот первая рабочая версия реализации списков:

(define empty_list '())

(define (prepend el lst)
    (lambda (command)
        (if (equal? command "head")
            el
            (if (equal? command "tail")
                lst
            )
         )
    )
)

(define (head lst)
    (lst "head")
)

(define (tail lst)
    (lst "tail")
)

(define (is_empty lst)
    (equal? lst empty_list)
)
var empty_list = null;

var prepend = function(el, list) {
    return function(command) {
        if (command === "head") {
            return el;
        } else if (command === "tail") {
            return list;
        }
    }
};

var head = function(list) {
    return list("head");
};

var tail = function(list) {
    return list("tail");
};

var is_empty = function(list) {
    return list === null;
};

Вставьте это в ваш любимый интерпретатор Scheme и поиграйтесь:

(define e empty_list)

(display (is_empty e))
; #t

(define names (prepend "Alice"
                       (prepend "Bob"
                                (prepend "Candice"
                                         empty_list
                                )
                       )
               )
)

(display (is_empty names))
; #f

(display (head names))
; Alice

(display (tail names))
; Some function representing the list of ("Bob", "Candice")

(display (head (tail names)))
; Bob
var e = empty_list;

console.log(is_empty(e));
// true

var names = prepend("Alice",
                    prepend("Bob",
                            prepend("Candice",
                                    empty_list)));

console.log(is_empty(names));
// False

console.log(head(names));
// Alice

console.log(tail(names));
// Some function representing the list of ("Bob", "Candice")

console.log(head(tail(names)));
// Bob


1.2 Но куда делись данные?


Определения этих функций удивили вас? Списки кажутся такой важной, объектно-ориентированной концепцией, но тут только функции!

Давайте посмотрим как они на самом деле работают. Для начала, понятие «пустого списка» довольно прямолинейно:

(define empty_list '())

(define (is_empty lst)
    (equal? lst empty_list)
)
var empty_list = null;

var is_empty = function(list) {
    return list === null;
};


Можно было выбрать любое значение. ’() подходит, так что я использовал его.

Теперь к самому главному: prepend.

(define (prepend el lst)
    (lambda (command)
        (if (equal? command "head")
            el
            (if (equal? command "tail")
                lst
            )
         )
    )
)
var prepend = function(el, list) {
    return function(command) {
        if (command === "head") {
            return el;
        } else if (command === "tail") {
            return list;
        }
    }
};


Вот здесь и происходит вся магия. Давайте обдумаем это.

Прежде всего, мы знаем, что при добавление чего-либо в начало списка мы получаем (новый) список обратно. Таким образом, возвращаемое prepend значение должно быть списком.

Одного взгляда на код достаточно чтобы понять, что prepend возвращает функцию. Итак, в нашем маленьком мысленном эксперименте список это просто (лямбда-)функция Scheme!

Так, что нам нужно делать со списками (кроме проверки на пустоту, которую мы уже осветили)? Ну, нам надо получать голову и хвост. Когда мы вызываем (prepend h t), мы как раз передаём голову и хвост как аргументы! Значит, в prepend мы возвращаем функцию, которая знает, как вернуть свою голову или хвост по запросу.

Значит, «список» это функция, «которая знает как вернуть свою голову или хвост по запросу». Выходит, наши функции head и tail должны только хорошо попросить!

(define (head lst)
    (lst "head")
)

(define (tail lst)
    (lst "tail")
)
var head = function(list) {
    return list("head");
};

var tail = function(list) {
    return list("tail");
};


Вот и всё! Мы сделали список в 24 строках кода, не используя ничего, кроме функций. Прежде чем вы пойдете дальше, убедитесь, что вы понимаете, почему это работает. Можете потренироваться на бумажке.

1.3 Строительство на этом фундаменте


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

map


Одна из частых задач на списках – это создание нового проходом в цикле по старому и применением какой-то функции к каждому элементу. Это называется «map».

(define (map fn l)
    (if (is_empty l)
        empty_list
        (prepend (fn (head l)) (map fn (tail l)))
    )
)
var map = function(fn, l) {
    if (is_empty(l)) {
        return empty_list;
    } else {
        return prepend(fn(head(l)), map(fn, tail(l)));
    }
};


Если вы не привыкли к рекурсивным определениям типа такого, вам, возможно, стоит потратить несколько минут и расписать, как это работает. Например вот так:

(define (square x) (* x x))
(define numbers (prepend 1 (prepend 2 (prepend 3 empty_list))))

(define squared_numbers (map square numbers))
; (map square (1 2 3))
; (prepend (square 1) (map square (2 3))
; (prepend (square 1) (prepend (square 2) (map square (3))))
; (prepend (square 1) (prepend (square 2) (prepend (square 3) (map square '()))))
; (prepend (square 1) (prepend (square 2) (prepend (square 3) '())))
; (prepend (square 1) (prepend (square 2) (prepend 9 '())))
; (prepend (square 1) (prepend (square 2) (9)))
; (prepend (square 1) (prepend 4 (9)))
; (prepend (square 1) (4 9))
; (prepend 1 (4 9))
; (1 4 9)
var square = function(x) {
    return x * x;
}
var numbers = prepend(1, prepend(2, prepend(3, empty_list)));

var squared_numbers = map(square, numbers);
// map(square, [1, 2, 3])
// prepend(square(1), map(square, [1, 2, 3]))
// prepend(square(1), prepend(square(2), map(square, [3])))
// prepend(square(1), prepend(square(2), prepend(square(3), map(square, []))))
// prepend(square(1), prepend(square(2), prepend(square(3), [])))
// prepend(square(1), prepend(square(2), prepend(9, [])))
// prepend(square(1), prepend(square(2), [9]))
// prepend(square(1), prepend(4, [9]))
// prepend(square(1), [4, 9])
// prepend(1, [4, 9])
// [1, 4, 9]


Я пишу списки в стиле Scheme ((1 2 3)), но на самом деле там функции, возвращённые из prepend.

Если вы до сих пор не совсем разобрались в этом, проследите выполнение (map square empty_list), а затем выполнение (map square (prepend 10 empty_list)).

Рекурсивное мышление в таком стиле требует некоторой практики. У меня есть куча тетрадок, исписанных вот этим. Опытные гитаристы разучивают новый материал медленно и методично, и нет причины программистам не поступать так же. Наблюдение за разрастанием и уничтожением вызовов функций может помочь вам понять как работают эти вещи на самом деле, в то время как долгое всматривание в код не даст ничего.

filter


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

Следующая функция, которую мы построим на списках — filter. Она принимает функцию и список и возвращает новый список, содержащий те элементы исходного, для которых данная функция возвращает #t. Вот пример:

(define numbers (prepend 1 (prepend 2 (prepend 3 empty_list))))
(define (is_odd x) (equal? (modulo x 2) 1))

(filter is_odd numbers)
; (1 3)
var numbers = prepend(1, prepend(2, prepend(3, empty_list)));
var is_odd = function(x) {
    return x % 2 === 1;
}

filter(is_odd, numbers);
// [1, 3]



Теперь реализуем filter:

(define (filter fn l)
    (if (is_empty l)
        empty_list
        (if (fn (head l))
            (prepend (head l) (filter fn (tail l)))
            (filter fn (tail l))
        )
    )
)
var filter = function(fn, l) {
    if (is_empty(l)) {
        return empty_list;
    } else if (fn(head(l))) {
        return prepend(head(l), filter(fn, tail(l)));
    } else {
        return filter(fn, tail(l));
    }
};


Сделайте перерыв, проверьте на каких-нибудь примерах. Двигайтесь дальше только совершенно поняв это.

and, or, not


Отклонимся от курса и реализуем «вспомогательные» функции. Они не имеют отношения к спискам, но они нам ещё понадобятся.

(define (not x)
    (if x
        #f
        #t
    )
)

(define (and a b)
    (if a
        (if b
            #t
            #f
        )
        #f
    )
)

(define (or a b)
    (if a
        #t
        (if b
            #t
            #f
        )
    )
)
var not = function(x) {
    if (x) {
        return false;
    } else {
        return true;
    }
};

var and = function(a, b) {
    if (a) {
        if (b) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
};

var or = function(a, b) {
    if (a) {
        return true;
    } else {
        if (b) {
            return true;
        } else {
            return false;
        }
    }
};


Естественно, в Scheme всё это уже есть, но мы ведь пытаемся избежать использования всяческих возможностей языка, если мы можем обойтись без них. Как далеко мы сможем зайти только с функциями и if?

Маленькое замечение: это всего лишь обычные функции Scheme, так что (and a b) не использует сокращенного вычисления, как встроенный макрос. Нашим целям это не повредит, но не стоит забывать об этом.

1.4 Списки из lambda-функций


Теперь, немного попрактиковавшись, вернёмся снова к определениям наших функций:

(define empty_list '())

(define (prepend el lst)
    (lambda (command)
        (if (equal? command "head")
            el
            (if (equal? command "tail")
                lst
            )
         )
    )
)

(define (head lst)
    (lst "head")
)

(define (tail lst)
    (lst "tail")
)

(define (is_empty lst)
    (equal? lst empty_list)
)
var empty_list = null;

var prepend = function(el, list) {
    return function(command) {
        if (command === "head") {
            return el;
        } else if (command === "tail") {
            return list;
        }
    }
};

var head = function(list) {
    return list("head");
};

var tail = function(list) {
    return list("tail");
};

var is_empty = function(list) {
    return list === null;
};


В этой реализации меня волнует несколько вещей. Наша цель — использовать как можно меньше возможностей языка, но мы уже использовали достаточно! Я могу насчитать как минимум пять:

  • Функции
  • Условие if
  • Строки
  • Булевы значения (#f и #t, результат is_empty)
  • Проверка на равенство (equal?)
Оказывается, мы можем избавиться почти от всего этого, но только ценой читабельности (и напряжения ума).

Давайте сначала избавимся от строк, проверок на равенство и даже конструкции if:

(define (prepend el lst)
    (lambda (selector)
            (selector el lst)
    )
)

(define (head lst)
    (lst (lambda (h t) h))
)

(define (tail lst)
    (lst (lambda (h t) t))
)
var prepend = function(el, list) {
    return function(selector) {
        return selector(el, list);
    };
};

var head = function(list) {
    return list(function(h, t) {
        return h;
    });
};

var tail = function(list) {
    return list(function(h, t) {
        return t;
    });
};


Вам стоит перекусить, прежде чем пытаться понять это! Тут нет строк, нет проверок на равенство, нет if, но у вас всё еще есть списки!

Функция prepend возвращает функцию, точно так же, как в предыдущей версии «список» на самом деле был функцией, знающей как вернуть свою голову и хвост по запросу.

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

Посмотрим на функцию head:

  • head принимает список и вызывает (list ...), что значит «Эй, список, передай пожалуйста все свои данные этой маленькой функции что я даю».
  • Список вызывает (... el lst), что значит «Окей, маленькая функция, вот тебе мои голова и хвост».
  • Вспомогательная функция это на самом деле (lambda (h t) h), значит при вызове с головой и хвостом в качестве аргументов она возвращает голову.
  • head принимает результат и передаёт его прямо вызывающей функции.
tail работает абсолютно так же, только её вспомогательная функция возвращает второй аргумент (хвост), а не первый.

Вот и всё! Проверки на равенство и if исчезли. Вы можете сказать, куда они делись? Что теперь вместо них?

Прежде чем двигаться дальше, давайте подчистим реализацию пустого списка. Она всё ещё использует ’() и проверки на равенство. Уберём их и сделаем всё более-менее подобным.

Для того, чтобы сделать это, потребуется немного изменить и остальные функции, но если вы поняли всё до этого места, то и это изменение не составит труда.

(define (empty_list selector)
    (selector '() '() #t)
)

(define (prepend el lst)
    (lambda (selector)
            (selector el lst #f)
    )
)

(define (head lst)
    (lst (lambda (h t e) h))
)

(define (tail lst)
    (lst (lambda (h t e) t))
)

(define (is_empty lst)
    (lst (lambda (h t e) e))
)
var empty_list = function(selector) {
    return selector(undefined, undefined, true);
};

var prepend = function(el, list) {
    return function(selector) {
        return selector(el, list, false);
    };
};

var head = function(list) {
    return list(function(h, t, e) {
        return h;
    });
};

var tail = function(list) {
    return list(function(h, t, e) {
        return t;
    });
};

var is_empty = function(list) {
    return list(function(h, t, e) {
        return e;
    });
};


Мы сделали списки немножко умнее. Кроме возможности передать вспомогательной функции голову и хвост, они теперь могут сообщить, пусты ли они. Мы заставили функции head и tail учитывать (и игнорировать) третий аргумент, а еще сделали функцию is_empty такой же, как и остальные.

И наконец, мы переопределили empty_list в таком же духе, как и все остальные, вместо специального магического значения. Пустой список теперь такой же, как и обычный — это функция, которая принимает другую, и говорит ей: «Мои голова и хвост это ’() и я пустой список».

Я использовал ’(), так как ничего лучше в Scheme не нашел, но вы можете использовать любое другое значение на своё усмотрение. Так как мы будем осторожны и не будем вызывать head или tail от пустого списка, эти значения всё равно никогда не всплывут.

В конце концов, мы реализовали основные элементы списков с помощью только двух вещей:

  • Функции
  • #t и #f для пустых списков.
Если вам хочется, подумайте как можно избавиться от второго (и в таком случае, вы действительно избавляетесь, или просто используете неявно какую-то возможность Scheme?).

2 Числа



Определения функций prepend, head и tail выглядят довольно мозговыносящими. Однако, определения map и filter уже более прямолинейны.

Причина этого в том, что мы скрыли детали реализации списков в тех первых четырёх функциях. Мы сделали всю чёрную работу по созданию списков почти что из ничего, а затем спрятали это за простым интерфейсом prepend, head и tail.

Идея создания каких-то вещей из простых составных частей и абстрагирование их в «чёрные ящики» — одна из самых важных идей и computer science, и программирования, так что давайте зайдём немного дальше и реализуем числа.

2.1 Что такое Число?


В рамках этой статьи мы будем рассматривать только неотрицательные числа. Можете попытаться добавить поддержку отрицательных чисел самостоятельно.

Как мы можем представить число? Ну, очевидно, можно использовать числа Scheme, но это не так круто, раз уж мы стараемся минимизировать количество используемых возможностей языка.

Один из способов представления числа это список, длина которого равна этому числу. Можно сказать, что (1 1 1) значит «три», ("cats" #f) значит «два», а ’() значит «ноль».

Элементы этого списка сами по себе не имеют никакого значения, так что возьмём что-нибудь, что уже имеется: пустой список! Прочувствуйте это:

(define zero empty_list)
; '()

(define one (prepend empty_list empty_list))
; ( '() )

(define two (prepend empty_list (prepend empty_list empty_list)))
; ( '() '() )
var zero = empty_list;
// []

var one = prepend(empty_list, empty_list);
// [ [] ]

var two = prepend(empty_list, prepend(empty_list, empty_list));
// [ [], [] ]



2.2 inc, dec



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

Наш основной строительный материал — inc и dec (инкремент и декремент).

(define (inc n)
    (prepend empty_list n)
)

(define (dec n)
    (tail n)
)
var inc = function(n) {
    return prepend(empty_list, n);
};

var dec = function(n) {
    return tail(n);
};


Чтобы прибавить единицу к числу, мы просто вставляем еще один элемент в список. Так, (inc (inc zero)) значит «два».

Чтобы вычесть единицу, мы просто убираем один из элементов: (dec two) значит «один» (не забудьте, что мы игнорируем отрицательные числа).

2.3 is_zero



В начале работы со списками мы часто использовали is_empty, так что стоит сделать и функцию is_zero:

(define (is_zero n)
    (is_empty n)
)
var is_zero = function(n) {
    return is_empty(n);
};


Ноль это просто пустой список!

2.4 add


Прибавление единицы это просто, но нам, скорее всего, захочется уметь складывать произвольные числа. Теперь, имея inc и dec, сделать это довольно легко:

(define (add a b)
    (if (is_zero b)
        a
        (add (inc a) (dec b))
    )
)
var add = function(a, b) {
    if (is_zero(b)) {
        return a;
    } else {
        return add(inc(a), dec(b));
    }
};


Это ещё одно рекурсивное определение. При сложении чисел возникает две возможности:

  • Если b равно нулю, результат это просто a
  • В противном случае, сложение a и b это то же самое, что и сложение a+1 и b-1
В конце концов, b «кончится» и ответом станет a (которое увеличивалось по мере уменьшения b).

Обратите внимание, что тут нет ни слова о списках! Информация о том, что «числа это списки», оказалось скрыта за is_zero, inc и dec, так что мы можем игнорировать её и работать на уровне абстракции «числа».

2.5 sub


Вычитание похоже на сложение, но вместо увеличения a по мере уменьшения b, мы будем уменьшать их обоих вместе:

(define (sub a b)
    (if (is_zero b)
        a
        (sub (dec a) (dec b))
    )
)
var sub = function(a, b) {
    if (is_zero(b)) {
        return a;
    } else {
        return sub(dec(a), dec(b));
    }
};


Теперь мы можем написать что-нибудь типа (add two (sub three two)) и результатом будет представление числа «три» в нашей системе (которое, конечно — список из трёх элементов).

Прервитесь на минутку и вспомните, что внутри чисел на самом деле списки, а внутри списков нет ничего, кроме функций. Мы можем складывать и вычитать числа и внутри всего этого всего лишь функции, перемещающиеся туда-сюда, разрастающие в другие функции и сжимающиеся по мере вызова, и эта извивающаяся кучка лямбд как-то представляет 1+1=2. Круто!

2.6 mul, pow


Для тренировки реализуем умножение чисел:

(define (mul a b)
    (if (is_zero b)
        zero
        (add a (mul a (dec b)))
    )
)
var mul = function(a, b) {
    if (is_zero(b)) {
        return zero;
    } else {
        return add(a, mul(a, dec(b)));
    }
};


Наличие add делает задачу довольно простой. 3*4 это то же самое, что и 3+3+3+3+0. Проследите за выполнением функции на бумажке, если смысл происходящего начинает от вас ускользать, и возвращайтесь, когда почувствуете, что готовы.

pow (возведение в степень) подобна mul, но вместо сложения копий числа, мы будем перемножать их, а «основанием» рекурсии будет единица, а не ноль.

(define (pow a b)
    (if (is_zero b)
        one
        (mul a (pow a (dec b)))
    )
)
var pow = function(a, b) {
    if (is_zero(b)) {
        return one;
    } else {
        return mul(a, pow(a, dec(b)));
    }
};



2.7 is_equal


Ещё одна задачка о числах — проверка на равенство, так что напишем её:

(define (is_equal n m)
    (if (and (is_zero n) (is_zero m))
        #t
        (if (or (is_zero n) (is zero m))
            #f
            (is_equal (dec n) (dec m))
        )
    )
)
var is_equal = function(n, m) {
    if (and(is_zero(n), is_zero(m))) {
        return true;
    } else if (or(is_zero(n), is_zero(m))) {
        return false;
    } else {
        return is_equal(dec(n), dec(m));
    }
};


Имеется три случая:

  • Если оба числа равны нулю, они равны

  • Если одно и только одно из чисел равно нулю, они не равны

  • В противном случае, вычитаем из каждого единицу и пробуем снова

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

2.8 less_than, greater_than


Подобным же образом можно реализовать и less_than:

(define (less_than a b)
    (if (and (is_zero a) (is_zero b))
        #f
        (if (is_zero a)
            #t
            (if (is_zero b)
                #f
                (less_than (dec a) (dec b))
            )
        )
    )    
)
var less_than = function(a, b) {
    if (and(is_zero(a), is_zero(b))) {
        return false;
    } else if (is_zero(a)) {
        return true;
    } else if (is_zero(b)) {
        return false;
    } else {
        return less_than(dec(a), dec(b));
    }
};


В отличие от is_equal, здесь есть четыре случая:

  • Если оба числа равны нулю, то a не меньше чем b
  • Иначе, если a (и только a) равно нулю, то оно меньше чем b
  • Иначе, если b (и только b) равно нулю, то a не может быть меньше чем b (отрицательные числа не рассматриваются)
  • В противном случае следует уменьшить оба и попробовать снова
И опять, оба числа уменьшаются, пока хотя бы одно из них не «кончится», и результат сравнения определяется тем, какое из них «кончилось» первым.

Можно было бы сделать что-нибудь такое же для greater_than, но есть способ проще:

(define (greater_than a b)
    (less_than b a)
)
var greater_than = function(a, b) {
    return less_than(b, a);
};



2.9 div, mod


Теперь, когда у нас есть less_than, можно реализовать деление и остаток:

(define (div a b)
    (if (less_than a b)
        zero
        (inc (div (sub a b) b))
    )
)

(define (rem a b)
    (if (less_than a b)
        a
        (rem (sub a b) b)
    )
)
var div = function(a, b) {
    if (less_than(a, b)) {
        return zero;
    } else {
        return inc(div(sub(a, b), b));
    }
};

var rem = function(a, b) {
    if (less_than(a, b)) {
        return a;
    } else {
        return rem(sub(a, b), b);
    }
};


Эти две немного более сложные, чем первые три базовые операции, потому что мы не можем воспользоваться отрицательными числами. Обязательно поймите, как это рабоает.

3 Замыкая круг



К настоящему моменту у нас уже есть (очень базовая) рабочая система чисел, построенная на списках. Давайте вернёмся к началу и реализуем еще списковых функций, использующих числа.

3.1 nth


Чтобы получить n-ый элемент списка, мы будем просто удалять из него элементы и уменьшать число n, пока не достигнем нуля:

(define (nth l n)
    (if (is_zero n)
        (head l)
        (nth (tail l) (dec n))
    )
)
var nth = function(l, n) {
    if (is_zero(n)) {
        return head(l);
    } else {
        return nth(tail(l), dec(n));
    }
};


На самом деле у нас теперь два списка, элементы которых мы удаляем по мере перебора, так как n это число, которое есть список, а dec удаляет из него элемент. Но ведь это гораздо приятнее читать, когда реализация списков абстрагирована, не так ли?

3.2 drop, take


Сделаем две полезные функции для работы со списками — drop и take.

(drop l three) вернёт список без первых трёх элементов.

(take l three) вернёт первые три элемента списка.

(define (drop l n)
    (if (is_zero n)
        l
        (drop (tail l) (dec n))
    )
)

(define (take l n)
    (if (is_zero n)
        empty_list
        (prepend (head l) (take (tail l) (dec n)))
    )
)
var drop = function(l, n) {
    if (is_zero(n)) {
        return l;
    } else {
        return drop(tail(l), dec(n));
    }
};

var take = function(l, n) {
    if (is_zero(n)) {
        return empty_list;
    } else {
        return prepend(head(l), take(tail(l), dec(n)));
    }
};



3.3 slice


«Срез» списка становится очень простой задачей, как только реализованы drop, take и вычитание чисел:

(define (slice l start end)
    (take (drop l start) (sub end start))
)
var slice = function(l, start, end) {
    return take(drop(l, start), sub(end, start));
};


Сначала мы отбрасываем всё до start, а затем выбираем нужное количество элементов.

3.4 length


Мы можем определить length — длину списка — рекурсивно, как и всё остальное:

(define (length l)
    (if (is_empty l)
        zero
        (inc (length (tail l)))
    )
)
var length = function(l) {
    if (is_empty(l)) {
        return zero;
    } else {
        return inc(length(tail(l)));
    }
};


Длина пустого списка — 0, а длина непустого списка это единица плюс длина его хвоста.

Если ваши мысли ещё не спутались в крепкий узел, подумайте вот о чем:

  • Списки сделаны из функций
  • Числа сделаны из списков, длина которых представляет число
  • length это функция, которая принимает список и возвращает его длину как число (список, длина которого равна этому числу)
  • И вот только сейчас мы определили length, хотя мы используем числа (которые используют длину списка для представления числа) уже достаточно долго!
У вас уже закружилась голова? Если нет, посмотрите на это:

(define mylist
    (prepend empty_list
             (prepend empty_list
                      empty_list
             )
    )             
)
(define mylistlength (length mylist))
var mylist = prepend(empty_list,
                     prepend(empty_list,
                             empty_list));
var mylistlength = length(mylist);



mylist это список из двух пустых списков.

mylistlength это длина mylist

что есть «два»…

которое представлено списком из двух пустых списков…

а это и есть mylist!

4 Заключение




Если вам понравилась эта маленькая запутанная история, я очень рекоммендую вам прочитать The Little Schemer. Это одна из первых книг, которые на самом деле изменили моё представление о программировании. Не бойтесь, что там используется Scheme — язык на самом деле не имеет значения.

Я так же создал gist (оригинальные примеры на JavaScript тут) со всем кодом из статьи. Не стесняйтесь форкнуть его и использовать для экспериментов.

Так же, чтобы потренироваться в рекурсивных функциях, можете реализовать следующее:

  • append — добавление элемента в конец списка
  • concat — объединение двух списков
  • min и max — нахождение меньшего (большего) из двух чисел
  • remove — то же что и filter, только возвращает список из тех элементов, на которых тестирующая функция (предикат) возвращает #f
  • contains_number — проверка принадлежности числа списку

Или, если хотите чего-нибудь посерьезнее, реализуйте большие концепции на основе уже созданных:

  • Отрицательные числа
  • Неотрицательные рациональные числа
  • Отрицательные рациональные числа
  • Ассоциативные списки

Помните, смысл не в том, чтобы создать что-то, хорошо работающее на настоящем компьютере. Вместо того, чтобы думать о том, как заставить конкретную комбинацию транзисторов и схем принимать правильные напряжения, думайте о «вычислениях» в прекрасном, идеальном, абстрактном смысле.
  • +37
  • 8.1k
  • 9
Share post

Similar posts

Comments 9

    +2
    Все круто, но лучше, имхо, было бы на JS :)
      0
      Мой код на Scheme специально полностью аналогичен оригинальному коду на JS, например, я не использовал cond, хотя очень хотелось :)
      Тем более, никто не мешает посмотреть оригинальный код по ссылке или на гитхабе.
        +2
        Кстати, интересный вариант — показывать два листинга на разных языках рядом.
        Так те, кто не знают один из языков дополнительно «втянуться» в его синтаксис благодаря второму.
      –1
      Очень круто.
      Но на том месте, где мы отказались от if и сравнений, я сломал мозг :(
        0
        Сначала над этим ломаешь мозг, а потом не можешь без этого жить, проверено :)
        Почитайте SICP, очень толковая книга.
        0
        Выглядит действительно очень занимательно! Спасибо за перевод.
        Сразу зачесались руки немного поправить функцию sub, чтобы вычитание из меньшего числа большего не приводило к взятию tail от пустого списка. Но автор, видимо, сознательно не акцентировался на таких мелочах, потому что и дальше оставлены подобные «небезопасности»: nth, drop, take.
          0
          За javascript спасибо, а то так бы и пропустил эту замечательную статью мимо. По сабжу — это восхитительно.
          +1
          Наверное лучшее введение в комбинаторную логику и лямбда исчисление для чайников :)

          Only users with full accounts can post comments. Log in, please.