Haskell Foldable Wats

(Перенос поста со старого сайта от 21 мая 2016 года)

По мотивам Haskell Foldable Wats в Haskell Mailing Lists.

Знаете ли вы, что произойдет, если поинтересоваться у Haskell минимальным значением кортежа из двух элементов?

Prelude> minimum (1,2)
2

Не очень интуитивно, правда? Давайте разбираться почему так происходит.

Для начала поймем, как этот самый minimum устроен. Вопрос к Hoogle дает следующий результат:

minimum :: Ord a => [a] -> a

Такая функция точно не подойдет для работы с кортежем, поскольку требует список в качестве аргумента. GHCi предлагает нам альтернативную, более общую версию, которая теперь и используется в base (у Hoogle, по всей видимости, сведения устаревшие):

Prelude> :t minimum
minimum :: (Ord a, Foldable t) => t a -> a

В исходниках Data.Foldable мы, наконец, находим виновника нашего беспокойства:

-- | The least element of a non-empty structure.
minimum :: (Foldable t, Ord a) => t a -> a
minimum = foldr1 min

Правая свертка с функцией min на каждом шаге будет брать элемент в аккумуляторе и элемент из структуры (в нашем случае — кортежа), сравнивать их и оставлять в аккумуляторе минимальный. Чтобы функция была полиморфна, начальное значение аккумулятора не задается, а берется просто первое из структуры. Эту логику обеспечивает foldr1 — вариант правой свертки над непустым Foldable типом:

-- | A variant of 'foldr' that has no base case,
-- and thus may only be applied to non-empty structures.
--
-- @'foldr1' f = 'Prelude.foldr1' f . 'toList'@
foldr1 :: (a -> a -> a) -> t a -> a
foldr1 f xs = fromMaybe (error "foldr1: empty structure")
                (foldr mf Nothing xs)
  where
    mf x m = Just (case m of
                     Nothing -> x
                     Just y  -> f x y)

Если сворачиваемая структура пуста, foldr вернет Nothing, который, не пройдя барьер fromMaybe, вызовет ошибку. В ином случае, если структура непуста, на первом шаге свертки функция mf упакует в Just первое значение в структуре, а далее свертка пойдет как обычно. Если считать, что элементы структуры кортежа — это первое и второе значение кортежа, то все должно отработать как нужно, и минимальным элементом (1,2) должна быть единица.

Осталось вспомнить вид foldr для кортежа — проблема может крыться только в нем. Так и есть:

instance Foldable ((,) a) where
    foldMap f (_, y) = f y
 
    foldr f z (_, y) = f y z

Итак, правая свертка на кортежах из двух элементов игнорирует первый элемент кортежа и выполняет переданную функцию f на втором элементе кортежа и начальном значении. То есть кортеж из двух элементов — это контейнер, который хранит только свой второй элемент. Это логичное поведение, поскольку у нас нет никаких гарантий относительно согласованности типов первого и второго элемента. Но, как итог, правая свертка без начального значения и вовсе не будет обращаться к функции, а просто вернет второй элемент кортежа!

Prelude> foldr1 min (1,2)
2
Prelude> foldr1 (*) (1,2)
2
Prelude> foldr1 (+) (1,2)
2

Благодаря ленивой семантике работать будет даже:

Prelude> foldr1 (+) (undefined,2)
2
Prelude> foldr1 undefined (undefined,2)
2

Точно так же и все библиотечные функции, использующие правую свертку, будут давать неинтуитивный результат для людей, которые только начали связывать свою жизнь с Haskell.

Prelude> sum (3,2)
2
Prelude> prod (3,2)
2
Prelude> or (True,False)
False

Проблема не была бы столь значима, если бы не повальная привычка писать что-то типа:

type MyComplex = (Double,Double)

А потом люди недоумевают, что же происходит с их программами. В приведенной в начале статьи ссылке идет жаркая дискуссия относительно того, “как мы дошли до жизни такой”, “раньше [haskell98] такой фигни не было” и прочее. Почитать весьма занимательно. В ситуацию уже вмешался SPJ (на стороне тех, кто выступает за уничтожение Foldable (,) a), так что как-нибудь оно да разрешится. Ну а мы пока можем сделать три простых вывода:

Повальная реализация всего и вся через Foldable хороша только тогда, когда все представители Foldable разумны, а не кортежи.
Кортежи стоит использовать только для временных значений, а не как один из важных типов в логике программы.
Стоит всегда предпочитать кортежу собственный тип-запись.