Javascript функциональное ленивый пример оценки требуется объяснение - PullRequest
10 голосов
/ 12 сентября 2011

Просмотр Хакерские новости и я сталкиваюсь с http://streamjs.org/, который является реализацией отложенной оцененной коллекции в Javascript.

Один из примеров:

function ones() {  
    return new Stream( 1, ones );  
}  
function naturalNumbers() {  
    return new Stream(  
        // the natural numbers are the stream whose first element is 1...  
        1,  
        function () {  
            // and the rest are the natural numbers all incremented by one  
            // which is obtained by adding the stream of natural numbers...  
            // 1, 2, 3, 4, 5, ...  
            // to the infinite stream of ones...  
            // 1, 1, 1, 1, 1, ...  
            // yielding...  
            // 2, 3, 4, 5, 6, ...  
            // which indeed are the REST of the natural numbers after one  
            return ones().add( naturalNumbers() );  
        }   
    );  
}  
naturalNumbers().take( 5 ).print(); // prints 1, 2, 3, 4, 5

Возможно, уже слишком поздно ночью, и я упускаю суть, но я не понимаю, как это печатает 1,2,3,4,5. Я ожидаю, что он напечатает 1,2,2,2,2 и умрет от бесконечно глубокой рекурсии. Я понимаю, как ones будет печатать бесконечное число 1. Я не понимаю, как работает naturalNumbers.

По моей (очевидно некорректной) логике, head из Stream, возвращенного первым вызовом naturalNumbers, будет равен 1, а следующий элемент в потоке будет оцениваться как ones().add( naturalNumbers() );, что равно ones().add(1) сопровождаемый ones().add( naturalNumbers() ), который будет повторяться до 1 и так далее ...

Был бы очень признателен, если бы кто-нибудь пролил свет на это.

Ответы [ 3 ]

11 голосов
/ 12 сентября 2011
naturalNumbers[0] = 1 // by definition
naturalNumbers[1] = ones[0] + naturalNumbers[0] = 1 + 1 = 2
naturalNumbers[2] = ones[1] + naturalNumbers[1] = 1 + 2 = 3
naturalNumbers[3] = ones[2] + naturalNumbers[2] = 1 + 3 = 4
...

Важным моментом является то, что function() { return ones().add(naturalNumbers()) } не возвращает элемент, он возвращает stream .Последующие элементы генерируются этим потоком, в данном случае «суммирующим» потоком.Таким образом, в отличие от ones(), naturalNumbers() не вызывает себя напрямую.Скорее, он вызывает себя косвенно - опосредованный потоком суммирования.

4 голосов
/ 12 сентября 2011

Хорошо, я возьму это на себя:)

ones - это легкая отправная точка.Эта функция возвращает Stream, чье первое значение равно 1, а остальные значения можно вычислить, вызвав саму функцию ones.Таким образом, любой запрос на «остаток» значений one всегда будет начинаться с 1, до бесконечности.

Следующее, на что нужно обратить внимание, это функция take:

function (howmany) {
    if (this.empty()) {
        return this;
    }
    if (howmany == 0) {
        return new Stream;
    }
    var self = this;
    return new Stream(this.head(), function () {
        return self.tail().take(howmany - 1);
    });
}

Так что сверху вниз, если Stream пуст, то не имеет значения, сколько элементов было запрошено, так как этот запрос не может быть выполнен, поэтому Stream возвращает свое (пустое) значение "я"..

Если мы не запрашивали никаких элементов, например, howmany == 0, то возвращается пустое значение Stream, которое само по себе не даст никаких элементов, если его спросить.

Наконец, самое интересное.Ссылка на текущий Stream заблокирована в области действия функции и возвращается новый Stream.Этот новый Stream создается с той же головой, что и текущий Stream, и хвост которого создается функцией, которая будет take на один элемент меньше из исходного хвоста Stream, чем запрашивающий абонент.Так как голова - это один предмет, а хвост может генерировать howmany-1 предметов, вызывающий получит новый Stream с возможностью доставки запрошенного количества предметов.

naturalNumbers немногоmore tricky.

Функция naturalNumbers возвращает Stream, у которого 1 в качестве головы, и внутреннюю функцию для генерации хвоста.

Внутренняя функция возвращает результатвызов метода add в потоке ones с результатом вызова функции naturalNumbers.Таким образом, мы можем догадаться, что это предполагает «соединение» двух Stream вместе каким-то образом.

Как выглядит add?Это функция, которой передается Stream:

function (s) {
    return this.zip(function (x, y) {
        return x + y;
    }, s);
}

Мы можем распознать часть 'add' как внутреннюю функцию - она ​​добавляет два значения вместе, так что это имеет смысл.Но что делает zip?zip - это функция, которая принимает функцию и Stream в качестве параметров.

function (f, s) {
    if (this.empty()) {
        return s;
    }
    if (s.empty()) {
        return this;
    }
    var self = this;
    return new Stream(f(s.head(), this.head()), function () {
        return self.tail().zip(f, s.tail());
    });
}

Так что в случае добавления переданная функция была функцией 'add' (x + y),и Stream был naturalNumbers Stream.

Что zip делает с этими значениями?Если Stream сам по себе пуст, возвращается «other» Stream.Я думаю, это потому, что добавление [] к [2,4,6,8, ...] имеет больше смысла быть [2,3,6,8, ...], чем что-либо еще.т. е. первый поток обрабатывается как бесконечно много 0 или "".

Если переданный Stream пуст, то применяется то же правило, что и выше, только в обратном порядке.т.е. добавление [2,4,6,8, ...] к [].

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

Так что в случае ones().add(naturalNumbers()) это приведет к Stream, чья голова равна 2, так как функция 'add' вызывается с 1 и 1 (элемент headоба ones и naturalNumbers оба 1).Таким образом, если этот новый Stream будет добавлен к ones, то будет добавлен элемент ones head (всегда 1) к элементу head нового Stream (теперь 2),предоставление 3.

Хвост этого нового Stream - это механизм для предоставления дополнительных «добавлений», если требуется.

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

Так что, если вы позвоните ones().take(9999999999999999999999999999999).print(), то для функции print потребуется много ресурсов. необходимо , чтобы иметь значение, прежде чем оно сможет его распечатать - это обязательно заставит этот механизм выдавать столько 1 с.Но ones().take(9999999999999999999999999999999) сам по себе является просто описанием элемента головы 1 и процессом доставки остальных предметов, но только по запросу.

Но ... Я мог бы ошибиться, потому что мне уже поздно, и я только что прочитал статью;)

3 голосов
/ 12 сентября 2011

Просто выполняйте оценки по одному члену за раз:

ones
= { 1, ones }
= { 1, { 1, ones } }
= ...
= { 1, { 1, { 1, ... to infinity!

nat
= { 1, ones+nat }
= { 1, { 1, ones } + { 1, ones+nat } } = { 1, { 1+1, ones+ones+nat } }
= { 1, { 2, { 1, ones } + { 1, ones } + { 1, nat } } }
= ...
= { 1, { 2, { 3, ... and so on.

Пример "сита" на дне http://streamjs.org еще более запутанный, попробуйте!

...