![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
На правах потока сознания, преимущественно чтобы сформулировать. Но если кому из понявших, о чем речь, есть что сказать - welcome.
Читая тут на досуге "Higher Order Perl", обнаружил, что автор запутался между List::Util::reduce из стандартного модуля и тем, что в более других языках называется fold. И до меня, похоже, дошла небанальная мысль, откуда там путаница. Я буду в хаскельных терминах, с аннотацией типами.
Итак, у нас есть (для ясности будем работать с левым fold, как более близким по смыслу к тому, что нам надо)
foldl :: (acc -> elt -> acc) -> acc -> [elt] -> acc
и есть его частный случай, когда типы аккумулятора и элемента списка совпадают. Его хорошо применять для вычисления сумм, произведений, и т.п. барахла, которое является моноидом относительно подставленной операции (и следовательно, есть единица оного моноида). fold - тотальная функция относительно списка. Собственно, если посмотреть в исходники, то мы увидим, что sum и product определяются именно как частичное применение foldl:
sum, product :: (Num a) => [a] -> a
sum = foldl (+) 0
product = foldl (*) 1
И есть очень, на первый взгляд, похожий блок функций minimum, maximum, etc.:
minimum, maximum: (Ord a) => [a] -> a
которые, сюрприз, определяются совсем не так, потому что у операций сравнения единицы нет, и поэтому второй аргумент для foldl взять неоткуда. И вот они-то, вернее, лежащий под ними
foldl1 :: (a -> a -> a) -> [a] -> a
и соответствуют List::Util::reduce. А путаница оттого, что они очень похожи, но имеют совершенно разную природу. Похоже, авторы Haskell тоже попались в эту ловушку, ибо иначе непонятно, почему foldl1 называется именно так. В чем разница в природе?
Вышеуказанный тип для foldl1, так похожий на частный случай для foldl (acc = elt, и откуда-то добыт второй аргумент) дает частичную функцию, не определенную для пустого списка. И всё, что на нем построено - minimum, maximum, minimumBy, etc. - тоже частичные. А каков будет тип тотальной? Правильно,
foldl1total :: (a -> a -> a) -> [a] -> Maybe a
И сюрприз, сразу видно, что это - не частный случай foldl. Невозможно так подставить типы и частично применить foldl, чтобы получить такой тип.
В теории, можно еще свести это к частному случаю foldl1, если взять acc = Maybe a, в качестве дефолтного значения Nothing, и похимичить с функцией. Но и с точки зрения стратегии вычислений, и с точки зрения смысла операции, это будет плохая идея. Хорошая идея - это
foldl1total f (x:xs) = Just (foldl f x xs)
foldl1total _ _ = Nothing
но это не частный случай foldl, это использование foldl глубоко внутри определения (перед ним - pattern matching, для которого надо вычислить список до конструктора, а после - инкапсуляция результата). Что совсем не то же самое. И сюрприз, именно так, с точностью до типа результата (пустота вместо Just и error вместо Nothing) и определяется foldl1. То есть на самом деле по реализации видно, что foldl1 не является foldl. А по типу - нет, и народ путается. И неважно, что perl не типизированный. Существенная разница в смысле операций от этого никуда не девается, и идея объединить эти две операции в одну неизбежно приводит к проблемам.
Надо сказать, что из такого определения foldl1 есть интересные следствия. Pattern match, как уже говорилось - это такая проверка, с предварительным вычислением до конструктора. Казалось бы, можно определить minimum как
minimum = foldl1 min
Но сюрприз, реальное определение толще:
minimum [] = errorEmptyList "minimum"
minimum xs = foldl1 min xs
Почему? Да потому что функция частичная, т.е. с вероятностью 1/2 :) мы налетим на то, что она не определена, и хочется, чтобы в эпитафии написали хотя бы, какой именно функцией программист пристрелил всю свою программу (если он вызывал minimum, то хотелось бы увидеть сообщение именно про нее, а не про foldl1, которую он не вызывал). То есть разобрать список до конструктора приходится дважды - сначала в minimum при проверке, затем еще раз в foldl1 уже для работы (и заодно для проверки тоже).
Читая тут на досуге "Higher Order Perl", обнаружил, что автор запутался между List::Util::reduce из стандартного модуля и тем, что в более других языках называется fold. И до меня, похоже, дошла небанальная мысль, откуда там путаница. Я буду в хаскельных терминах, с аннотацией типами.
Итак, у нас есть (для ясности будем работать с левым fold, как более близким по смыслу к тому, что нам надо)
foldl :: (acc -> elt -> acc) -> acc -> [elt] -> acc
и есть его частный случай, когда типы аккумулятора и элемента списка совпадают. Его хорошо применять для вычисления сумм, произведений, и т.п. барахла, которое является моноидом относительно подставленной операции (и следовательно, есть единица оного моноида). fold - тотальная функция относительно списка. Собственно, если посмотреть в исходники, то мы увидим, что sum и product определяются именно как частичное применение foldl:
sum, product :: (Num a) => [a] -> a
sum = foldl (+) 0
product = foldl (*) 1
И есть очень, на первый взгляд, похожий блок функций minimum, maximum, etc.:
minimum, maximum: (Ord a) => [a] -> a
которые, сюрприз, определяются совсем не так, потому что у операций сравнения единицы нет, и поэтому второй аргумент для foldl взять неоткуда. И вот они-то, вернее, лежащий под ними
foldl1 :: (a -> a -> a) -> [a] -> a
и соответствуют List::Util::reduce. А путаница оттого, что они очень похожи, но имеют совершенно разную природу. Похоже, авторы Haskell тоже попались в эту ловушку, ибо иначе непонятно, почему foldl1 называется именно так. В чем разница в природе?
Вышеуказанный тип для foldl1, так похожий на частный случай для foldl (acc = elt, и откуда-то добыт второй аргумент) дает частичную функцию, не определенную для пустого списка. И всё, что на нем построено - minimum, maximum, minimumBy, etc. - тоже частичные. А каков будет тип тотальной? Правильно,
foldl1total :: (a -> a -> a) -> [a] -> Maybe a
И сюрприз, сразу видно, что это - не частный случай foldl. Невозможно так подставить типы и частично применить foldl, чтобы получить такой тип.
В теории, можно еще свести это к частному случаю foldl1, если взять acc = Maybe a, в качестве дефолтного значения Nothing, и похимичить с функцией. Но и с точки зрения стратегии вычислений, и с точки зрения смысла операции, это будет плохая идея. Хорошая идея - это
foldl1total f (x:xs) = Just (foldl f x xs)
foldl1total _ _ = Nothing
но это не частный случай foldl, это использование foldl глубоко внутри определения (перед ним - pattern matching, для которого надо вычислить список до конструктора, а после - инкапсуляция результата). Что совсем не то же самое. И сюрприз, именно так, с точностью до типа результата (пустота вместо Just и error вместо Nothing) и определяется foldl1. То есть на самом деле по реализации видно, что foldl1 не является foldl. А по типу - нет, и народ путается. И неважно, что perl не типизированный. Существенная разница в смысле операций от этого никуда не девается, и идея объединить эти две операции в одну неизбежно приводит к проблемам.
Надо сказать, что из такого определения foldl1 есть интересные следствия. Pattern match, как уже говорилось - это такая проверка, с предварительным вычислением до конструктора. Казалось бы, можно определить minimum как
minimum = foldl1 min
Но сюрприз, реальное определение толще:
minimum [] = errorEmptyList "minimum"
minimum xs = foldl1 min xs
Почему? Да потому что функция частичная, т.е. с вероятностью 1/2 :) мы налетим на то, что она не определена, и хочется, чтобы в эпитафии написали хотя бы, какой именно функцией программист пристрелил всю свою программу (если он вызывал minimum, то хотелось бы увидеть сообщение именно про нее, а не про foldl1, которую он не вызывал). То есть разобрать список до конструктора приходится дважды - сначала в minimum при проверке, затем еще раз в foldl1 уже для работы (и заодно для проверки тоже).
Tags: