Нахождение недостающего класса типов «Уменьшить» из статьи «Дерево пальца» - PullRequest
Новая
       22

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

9 голосов
/ 09 декабря 2011

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

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

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

Список кода из Деревья пальца выполнены правильно (я надеюсь) :

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

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 ]

6 голосов
/ 09 декабря 2011

Учитывая, что reduce - это общее альтернативное имя для функции "fold", я бы предположил, что это нечто похожее на класс 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 или другим аналогичным универсальным идентификатором. Использование оператора в качестве имени аргумента бинарной функции - это ... немного необычный выбор, но, думаю, он подчеркивает некоторые аспекты структуры сгиба.

5 голосов
/ 09 декабря 2011

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

class Reduce f where
  reducer :: (a -> b -> b) -> (f a -> b -> b)
  reducel :: (b -> a -> b) -> (b -> f a -> b)
...