Какие есть экземпляры Foldable, которые не являются «общими складными структурами» в смысле Data.Foldable? - PullRequest
Новая
       57

Какие есть экземпляры Foldable, которые не являются «общими складными структурами» в смысле Data.Foldable?

0 голосов
/ 24 ноября 2018

В документации для Foldable перечислены несколько свойств, которые требуются для "общих складных конструкций":

  • Для foldr:

    Для общей складной конструкции это должно быть семантически идентично 

    foldr f z = foldr f z . toList

  • Для foldl:

    Дляобщая Складная конструкция, которая должна быть семантически идентична, 

    foldl f z = foldl f z . toList

  • Для foldl' (с тем, что для меня выглядит опечаткой):

    Для общей складной структуры это должно быть семантически идентично 

    foldl f z = foldl' f z . toList

В каких случаях Foldable эти свойства не нужны или не могут храниться?

1 Ответ

0 голосов
/ 24 ноября 2018

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

Однако классы типов часто дают вам возможность определить больше поведения класса типов.Это может быть полезно, если автоматическое определение, скажем, toList по умолчанию неэффективно, и вы хотите предоставить более эффективную реализацию.Это может быть легче понять для класса типов Monoid, который определяет mconcat как необязательную функцию ", так что оптимизированная версия может быть предоставлена ​​для определенных типов".

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

import Data.Foldable

data Invalid a = Invalid a deriving (Show, Eq)

instance Foldable Invalid where
  foldMap f (Invalid x) = f x
  foldr _ x _ = x -- Unlawful!!
  toList (Invalid x) = [x]

Хотя ему нужно только определить foldMap как экземпляр Foldable, этот такжеопределяет foldr и toList.Хотя определение toList в порядке, определение foldr нарушает правила: 

*Q53460772 Data.Monoid Data.Foldable> toList $ Invalid 42
[42]
*Q53460772 Data.Monoid Data.Foldable> foldMap Sum $ Invalid 42
Sum {getSum = 42}
*Q53460772 Data.Monoid Data.Foldable> f = \x acc -> x + acc
*Q53460772 Data.Monoid Data.Foldable> z = 0
*Q53460772 Data.Monoid Data.Foldable> (foldr f z . toList) $ Invalid 42
42
*Q53460772 Data.Monoid Data.Foldable> foldr f z $ Invalid 42
0

Функции toList и foldMap ведут себя так, как вы ожидаете, что они будут себя вести, но обратите внимание, что foldr f z не выдает тот же вывод, что и foldr f z . toList.

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

...