Свёртка или рекурсия

@include_brain · Регистрация: 13.09.2013

Студворк — интернет-сервис помощи студентам

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

для стандартных рекурсивных обходов списка

К примеру, имеется список телефонных номеров:

Haskell
1
2
3
4
5
6
phonebook = [   
    ("Masha", "123-456-78"),
    ("Dasha", "456-178-33"),
    ("Glasha", "247-355-45"),
    ("Vasya", "252-146-77"),
    ("Kolya", "354-136-82")]

Автор рекомендует использовать такой вариант lookup' (я в курсе, что есть библиотечный аналог, но сейчас речь не об этом):

Haskell
1
2
lookup'::String->[(String,String)]->Maybe String
lookup' key = foldl (\acc (k,v)-> if k == key then Just v else acc) Nothing

вместо следующего:

Haskell
1
2
3
4
5
lookup'::String->[(String,String)]->Maybe String
lookup' _ [] = Nothing
lookup' key ((k,v):xs)
    | key == k = Just v
    | otherwise = lookup' key xs

Свою рекомендацию Миран аргументирует тем, что по его мнению первый вариант проще читать и понимать, в то время как для понятие второго варианта

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

Насчёт интеллектуальных усилий может автор и прав для каких-то более сложных примеров, однако в приведённых выше, на мой взгляд, более читабельным является именно второй вариант (во всяком случае для меня).

Кроме того, я склоняюсь к выбору именно второго варианта, т.к. в случае первого (рекомендуемого автором) всегда будет проводиться полная итерация по списку, даже если искомый элемент был найден в первой же записи. Я против "работы в ведро" - если предстоящая работа не нужна, то её не стоит выполнять. Найдя нужный элемент, нет никакой нужды продолжать работу.

Прошу меня поправить, если я в чём-то ошибаюсь.

Спасибо.

@_Ivana · 18.12.2014, 11:56

Начнем с того, что эти функции разные - первая вернет последнее значение неуникального ключа - и поэтому она обязана пробежать по всему списку, а вторая - первое, и ей бежать до конца необязательно.

@include_brain · 18.12.2014, 11:58 **[ТС]**

Предполагается, что это словарь, соответственно все ключи должны быть уникальными.

@korvin_ · 18.12.2014, 12:01

Сообщение от include_brain

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

Сообщение от include_brain

Прошу меня поправить, если я в чём-то ошибаюсь.

1) С чего ты решил, что автор утверждает, будто свертку нужно использовать даже тогда, когда нужен другой алгоритм?
2) Рекомендую почитать про TCO в Хаскелле.

@include_brain · 18.12.2014, 12:03 **[ТС]**

Сообщение от korvin_

1) С чего ты решил, что автор утверждает, будто свертку нужно использовать даже тогда, когда нужен другой алгоритм?

Я привёл конкретную ситуацию (данные и код) на примере которых автор даёт рекомендацию.

@Catstail · 18.12.2014, 12:23

include_brain, то, что Вы написали, на мой взгляд верно. Действительно, если ключ уникален, то нет смысла просматривать весь список. Да, рекурсия здесь будет к месту. А для неуникальных ключей, наверное лучше отказаться от Maybe и сделать аккумулятор списком. Как-нибудь так:

Haskell
1
2
lookup' :: String -> [(String,String)]-> [String]
lookup' key = foldl (\acc (k,v)-> if k == key then v:acc else acc) []

Тогда функция вернет телефоны всех Маш из списка (или пустой список, если нет ни одной знакомой Маши)

@_Ivana · 18.12.2014, 12:46

Ага, называется filter. И вообще, имхо, тема об использовании или прелюдных мапов/фолдов/фильтров или самописные реализаций каждый раз.

@include_brain · 18.12.2014, 12:48 **[ТС]**

Сообщение от _Ivana

Ага, называется filter.

Я не спрашивал о функциях, мой вопрос заключался в другом.

@_Ivana · 18.12.2014, 14:18

Сообщение от include_brain

Я не спрашивал о функциях, мой вопрос заключался в другом.

А я и не вам отвечал, поскольку до сих пор не понял суть вашего "вопроса".

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	18.12.2014, 11:56
	Начнем с того, что эти функции разные - первая вернет последнее значение неуникального ключа - и поэтому она обязана пробежать по всему списку, а вторая - первое, и ей бежать до конца необязательно. 0

@include_brain 3 / 3 / 0 Регистрация: 13.09.2013 Сообщений: 38
	18.12.2014, 11:58 [ТС]
	Предполагается, что это словарь, соответственно все ключи должны быть уникальными. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	18.12.2014, 12:46
	Ага, называется filter. И вообще, имхо, тема об использовании или прелюдных мапов/фолдов/фильтров или самописные реализаций каждый раз. 0

Свёртка или рекурсия

Решение