Если карта может быть определена с помощью Foldable, почему Functor не упоминается в определении Foldable?

Я читал, что map можно определить с помощью foldr, т.е. это примитивная рекурсивная функция. По крайней мере для списков.

Теперь мой вопрос: почему Functor не является подклассом Foldable? И если fmap можно определить только в терминах foldr для списков, что делает их особенными?

Глядя на определение map с foldr:

myMap f xs = foldr step [] xs
    where step x ys = f x : ys

Я мог бы использовать моноиды, чтобы добраться до:

myMap f xs = foldr step mempty xs
    where step x ys = f x : ys

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


haskell functor foldable
person hgiesel    schedule 16.03.2017    source источник
comment
Почему вы хотите это сделать? Это просто глупая идея. С другой стороны, Functor и Foldable не являются типами, и в Haskell нет подтипов.   -  person Ingo    schedule 17.03.2017
comment
IO является функтором. Допустим, есть x = readLn :: IO Int. foldr (+) 0 x должно быть Int. Что это?   -  person Ry-♦    schedule 17.03.2017
comment
@Ingo Тогда как вы называете отношения между Applicative и Functor. Просто каждый Applicative должен быть экземпляром Functor   -  person hgiesel    schedule 17.03.2017
comment
Это классы типов, а не типы, и, следовательно, супер/подклассы.   -  person Ingo    schedule 17.03.2017
comment
Foldable слишком ориентирован на список, он в основном позволяет эффективно запускать foldr f x . toList. Он не будет различать деревья с одинаковым посещением по порядку. Вместо этого fmap f сохранит всю древовидную структуру.   -  person chi    schedule 17.03.2017

Ответы (1)


arrow_upward
8
arrow_downward

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

Вы обнаружили фундаментальную проблему, которая не позволяет сделать каждый Foldable функтором; foldr отбрасывает свернутую структуру, оставляя только (что составляет) список ее элементов. Вы не можете «сойти с рук минусами», потому что вы не можете знать, какая структура данных дается только Foldable экземпляром.

Учитывая это (типичное) определение дерева:

data Tree a = Bin a (Tree a) (Tree a) | Tip

instance Functor Tree where
  fmap f (Bin a l r) = Bin (f a) (fmap f l) (fmap f r)
  fmap _ Tip = Tip

instance Foldable Tree where
  foldMap f (Bin a l r) = foldMap f l <> f a <> foldMap f r
  foldMap _ Tip = mempty

Сравните эти два дерева:

let x = Bin 'b' (Bin 'a' Tip Tip) Tip
let y = Bin 'a' Tip (Bin 'b' Tip Tip)

Оба дерева имеют toList "ab", но они явно разные. Это означает, что при свертывании дерева теряется некоторая информация (а именно, граница между левым поддеревом, правым поддеревом и элементом), которую вы не можете восстановить. Поскольку вы не можете различить x и y, используя результаты экземпляра Foldable, вы не можете написать fmap так, чтобы fmap id == id использовала только эти методы. Нам пришлось прибегнуть к сопоставлению с образцом и использовать конструкторы для записи экземпляра Functor.

person Lazersmoke    schedule 16.03.2017