Езици като Haskell могат да работят директно с Infinite Lists, но може ли тази възможност да бъде пренесена в света на JavaScript?
В реалния свят имаме работа с „безкрайни“ идеи през цялото време. Всички положителни числа са пример за безкрайна концепция, на която не бихме хвърлили око. Но обикновено, когато програмираме, трябва да мислим за тези безкрайни концепции по краен начин. Не можете да имате Масив от всички положителни числа (поне не и в JavaScript!).
Това, което искам да представя в тази статия, е идеята за безкраен списък структура от данни, която може да представлява някаква безкрайна последователност и нека използваме общи операции като карта и филтриранеза модифициране и създаване на нови последователности.
Когато искаме действително да използваме данните, можем просто да вземем някакво конкретно количество от тях.
Създаване на безкраен списък
За да създадем типа структура, дефинирана по-горе, първо се нуждаем от някакъв начин просто да опишем безкрайно нещо, без да е необходимо действително да го оценяваме (което би убило компютъра наистина бързо). За да направим това, първо трябва да разберем 2 неща:
- Итератор модел
- Генератор функции
Моделът на итератора
Нека първо започнем с итератора шаблона. Моделът на итератора е вид модел на проектиране, където можете да създавате много стойности, една по една. По същество това е просто обект с метод .next(). Когато този метод бъде извикан, той връща друг обект с 2 ключа: value и done. Тъй като извикваме .next(),свойството done показва дали итераторът има повече стойности, които да ни даде, и стойността, разбира се, е стойността. По-долу е даден прост итератор, който връща стойности от 0 до 3:
Този вид модел има първокласномясто в JavaScript. Масиви, обекти, карти,инабори всички могат да приложат модела на итератор чрез в съответствие с интерфейс, наречен Iterable.
Функции на генератора
Функциите за генериране са специален вид функция в JavaScript, която се декларира със синтаксиса function*. Генераторните функции се използват за създаване на iterator обекти (такива с метод .next()), но по много по-ясен и по-кратък начин. По-долу е даден краен генератор, който създава еквивалентен итератор:
Тук ключовата дума yield се използва за указване на стойността, която се връща при всяко извикване на итератора. Можете да мислите за функцията, която поставя на пауза след всеки получаване и продължава от мястото, където е спряла, когато iterator' Методът .next() се извиква отново.
Всичко, което би било необходимо, за да стане този безкраен генератор, е да се превърне цикълът while (x ‹ 4) в докато (вярно) цикъл. За по-добро усещане, ето един безкраен генератор за известната последователност на Фибоначи:
Сглобяване
Итераторите изглеждат като представяне на нещо безкрайно, защото ни позволяват да искаме елемента .next()безкрайно дълго. Освен това, генераторът изглежда като добър начин за уточняване на итератора, защото можем да пишем кратки алгоритми за безкрайни серии без шаблона за ръчно създаване на итератори.
Но това все още не е достатъчно, защото колкото и мощни да са генераторите, те всъщност не са композиционни. Ако исках да създам генератор, в който филтрирах всички числа на фибоначи, завършващи с 5, не мога лесно да използвам съществуващия си createFibSeqIterator() за да направя това — т.е. не мога да съставя идеята за оригиналния генератор+ някаква нова операция върху него.
За да коригираме това, първо трябва да капсулираме генератора в тип данни, което можем да направим с клас:
В този клас ще внедрим нашите операции като филтър, карта и вземи.
Безкрайно мързелив
Може да сте озадачени, когато мислите как бихме могли да приложим операция като филтър. Отговорът е прост: правим го мързеливо. Вместо всъщност да се опитваме да филтрираме нашия списък, ние просто правим бележка в класа Infinite. След това, когато потребителят иска конкретно .take() някои елементи от него, ние можем да извършим действителната работа на филтриране тогава.
Класът Infinite получава ново свойство transformations, а filter създава нов Infinite със същия генератор и трансформациимасив и избутва трансформация в списъка.
Сега имаме всички компоненти, от които се нуждаем, за да напишем .take(), който ще направи списъка конкретен.
Когато извикаме .take(n), можем да създадем итератор от генератора и след това да инициализираме масив с фиксирана дължина с n елементи. Това ще бъде нашият конкретен списък. Променлива index може да се използва, за да следите колко конкретни стойности сме събрали досега. Използвайки цикъл while, можем да получим стойност от итератора и след това да изпълним нашия списък с трансформации върху нея. Ако една от тези трансформации е филтър и не издържи теста, ние просто не я добавяме към нашия конкретен списък и повтаряме цикъла. Когато съберем n елемента, ние сме готови и можем да върнем конкретния списък.
Нека да видим как изглежда това с примера на Фибоначи от преди:
За да приложим карта, бихме могли да използваме почти същия подход като с филтър. Самият метод на картата просто клонира текущия Infinite и добавя нова трансформация към списъка. В take е достатъчно просто да добавите else-ifвътре в цикъла на трансформация.
Заключение
В тази статия проучихме итераторния шаблон и генераторните функции, за да изградим композиционен и лениво оценен Структура на данните Безкраен списък.
Безкрайният списък в тази статия обаче е малко ограничен, тъй като му липсват някои операции, които биха го направили наистина полезен, като внедряване на карта, зависимо филтриране или възможност за комбиниране на Безкрайноs заедно (като сдвояване на всяко число на фибоначи с просто число, например).
За тях създадох lazy-infinite,по-мощна структура на Infinite List, която съответства на спецификацията Fantasy-Land. „Бих се радвал да разгледате github“ или да опитате в следващия си проект с
Ако ви е харесало това задълбочаване в безкрайните структури от данни, „Напишете ми в twitter @fstokesman“ и обмисляте да дадете 👏 на тази статия.
