Нахождение недостающего класса типов "Уменьшить" из статьи "Дерево пальца"

Вчерашний Wikibender, который начался с этого стекового потока на Comonads, закончился в статье MarkCC о Finger Trees.

В статье он широко использует Reduce тип класс. Он пишет об этом классе типов, как если бы он был очень распространенной и часто используемой библиотекой, но я не могу найти ее по взлому и не могу найти достаточно документации, чтобы действительно понять код.

Может кто-нибудь помочь мне понять, что Reduce класс типов делает, как (-<) а также (>-) операторы работают, а что должен рассказать о коде в статье (скопировано ниже)?

Листинг кода из Finger Trees выполнен правильно (надеюсь):

Листинг 1: объявление экземпляра для Node

instance Reduce Node where
  reducer (-<) (Node2 a b) z = a -< (b -< z)
  reducer (-<) (Node3 a b c) z = a -< (b -< (c -< z))
  reducer (>-) (Node2 b a) = (z >- b) >- a
  reducer (>-) (Node3 c b a) = ((z >- c) >- b) >- a

Листинг 2: объявление экземпляра для FingerTree

instance Reduce FingerTree where
  reducer (-<) Empty zero = zero
  reducer (-<) (Single x) zero = x -< zero
  reducer (-<) Deep left mid right zero = left -<' (mid -<'' (right -<' zero))
    where (-<') = reducer (-<)
          (-<'') = reducer (reducer (-<))
  reducel (>-) zero Empty = zero
  reducel (>-) zero (Single x) = zero >- x
  reducel (>-) zero (Deep left mid right) = ((zero >-' left) >-'' mid) >-' right
    where (>-') = reducel (>-)
          (>-'') = reducel (reducel (>-))

листинг 3: типы данных

data Node s = Node2 s s | Node3 s s s

data FingerTree a = Empty
  |  Single a
  | Deep (Digit a) (FingerTree (Node a)) (Digit a)

data Digit a = [ a ]
Источник

2 ответа

Решение

При условии reduce это общее альтернативное имя для функции "сгиба", я думаю, что это что-то похожее на Foldable тип класс. Определения экземпляров, похоже, тоже имеют смысл.

Foldable класс может быть определен с помощью просто foldr, который имеет тип подписи foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b тогда как reducer в этом коде, кажется, reducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b, За исключением другого порядка аргументов, он должен работать одинаково.

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

Источник

Это определено в документе, связанном в статье: Пальцы: простая структура данных общего назначения.

class Reduce f where
  reducer :: (a -> b -> b) -> (f a -> b -> b)
  reducel :: (b -> a -> b) -> (b -> f a -> b)
Источник
Другие вопросы по тегам