В отличие от map, filter для деревьев, в том виде, в котором он используется для коллекций, практически непригоден. Посудите сами. Предположим, мы хотим выполнить поиск по файловой системе файлов, подходящих под шаблон *.log. Задача сразу разбивается на две подзадачи. Фильтрация, оставляющая листовые узлы, и последующая фильтрация по шаблону. Очевидно, что после первого фильтра мы уже хотим работать со списком, но никак не с деревом. Более того, как будет выглядеть дерево в котором только одни файлы, и какой в нём практический смысл? Как ни крути, большинство фильтров древовидных структур, должны на выходе давать плоские списки.

Filter
Trees

Но всё же иногда filter может использоваться, к тому же, для полноты картины, стоит пройти все шаги. Для начала необходимо определиться с тем, что нужно вернуть в ситуации, если нода не удовлетворяет предикату. Логично использовать null.

//   a *
//    /|\
// B * C * d
//  /|   |\
// e  F  G j

Глядя на реализацию фильтра, видно, что если нода не удовлетворяет предикату, то её дети не рассматриваются вообще. В примере выше это нода B. Соответственно её дети e и F даже не анализируются и отфильтровываются вместе с B.

Интересно выглядит и вот эта запись children.map(c => filter(f, c)).filter(v => v). Дело в том, что наш фильтр не работает со списком, а работает с конкретным корневым узлом. Соответственно, если мы обрабатываем детей, то в результате фильтрации количество детей не уменьшается. На их месте появляется null. Поэтому обход детей совершается, используя map на массиве children с последующим filter. Тогда все null элементы отфильтруются.

Посмотрите, какой результат получился бы, если не использовать фильтрацию на значение null:

Сравните с результатом из прошлого примера.

Элементы null отфильтрованы:

=> '["a",[["d",[["j"]]]]]'

Элементы null НЕ отфильтрованы:

=> '["a",[null,null,["d",[null,["j"]]]]]'
Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Node, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →