Списки и рекурсия

Список это главный носитель данных начального Haskell, а рекурсия заменяет циклы. В этом уроке: устройство списка из cons-ячеек, иммутабельность и разделение хвостов, паттерн-матчинг и guards, рекурсия по форме данных, аккумуляторы и хвостовая рекурсия, и почему String это просто [Char] со всеми последствиями.

Идея

Плохая новость: в Haskell нет цикла for. И while нет. И не будет.

Это не упрямство дизайнеров языка, а прямое следствие урока 01: цикл живёт на мутации. i++, аккумулятор-переменная, флажок выхода, всё это перезапись значений, которой в чистом языке не существует. Хорошая новость: всё, что ты делал циклом, делается рекурсией, и большую часть этой рекурсии ты даже не будешь писать руками. В уроке 04 появятся map, filter и компания, которые заберут себе девять циклов из десяти. Но они сами написаны через рекурсию, и сегодня мы спускаемся на этот нижний этаж: после него стандартная библиотека перестанет быть магией.

Опорная мысль урока такая: форма функции повторяет форму данных. Посмотри, как устроен список. Это не массив, под ним нет непрерывного куска памяти. Список в Haskell определяется рекурсивно: он либо пуст, либо это один элемент плюс ещё один список. Всё:

[1, 2, 3]  это сахар для  1 : (2 : (3 : []))

┌───┬───┐    ┌───┬───┐    ┌───┬───┐
│ 1 │ ●─┼───▶│ 2 │ ●─┼───▶│ 3 │ ●─┼───▶ []
└───┴───┘    └───┴───┘    └───┴───┘

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

И одно знакомое слово напоследок. Cons-ячейки иммутабельны, поэтому хвост можно разделять между списками: 1 : xs не копирует xs, а ссылается на него. Это тот самый structural sharing из урока про персистентные структуры, только здесь он не библиотека, а способ существования каждого списка в языке.