Функции высшего порядка

Половина рекурсии из прошлого урока больше не нужна: map, filter и zipWith покрывают типовые обходы. В этом уроке: лямбды, композиция через точку, $ против скобок, list comprehensions, бесточечный стиль, первая встреча с import и экскурсия по Data.List, Data.Char и Data.Function. В ДЗ девять кат: сегодня день набивания руки.

Идея

Вернись к своим решениям из урока 03 и положи рядом stutter, elem' и воображаемую функцию “удвой каждое число”. Скелет у них один: пройди список, в базе верни базу, в шаге сделай что-то с головой и рекурсивно займись хвостом. Меняется только это “что-то”. А раз меняется одно место, его можно вынести в параметр. Параметр-функцию.

Функции в Haskell это обычные значения: их можно передавать аргументами, возвращать из функций, хранить в списках. Функция, которая принимает или возвращает другую функцию, называется функцией высшего порядка. Ты плотно работал с ними в ФП-серии раздела 02, так что сегодня не знакомство, а перенос навыка на новую почву. Вот весь map, целиком:

map' :: (a -> b) -> [a] -> [b]
map' _ []       = []
map' f (x : xs) = f x : map' f xs

Посмотри на сигнатуру. В уроке 02 ты выяснил, что стрелка правоассоциативна и скобки справа можно не писать. Здесь скобки слева, и они обязательны: (a -> b) -> [a] -> [b] означает “дай мне функцию из a в b”, а без скобок a -> b -> [a] -> [b] означало бы “дай мне a, потом b”. Скобки в левой позиции это и есть формальная примета функции высшего порядка.

И filter, с guards из прошлого урока:

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x : xs)
  | p x       = x : filter' p xs
  | otherwise = filter' p xs

Аргумент p это предикат, вопрос про элемент. Дальше всё урок будет крутиться вокруг одной мысли: map, filter и их родня это не магия стандартной библиотеки, а словарь именованных обходов. Рекурсия из урока 03 это ассемблер; сегодня поднимаемся на уровень, где у каждого паттерна обхода есть имя, и читатель твоего кода видит намерение, а не цикл, который надо расшифровывать.