Как использовать функцию сгиба в Haskell с другими типами данных - PullRequest
Новая
       38

Как использовать функцию сгиба в Haskell с другими типами данных

3 голосов
/ 20 июня 2019

Есть ли универсальный способ мышления о том, как создать функцию сгиба для нового типа данных?

Например, функция сгиба для Дерева данных: 

data Tree t = Leaf | Node t (Tree t) (Tree t)
              deriving (Eq,Ord,Show)

treeFold:: (a -> b -> b -> b) -> b -> Tree a -> b
treeFold f e Leaf = e
treeFold f e (Node x l r) = f x (treeFold f e l) (treeFold f e r)

Например, как мне создать функцию сгиба для следующих данных? 

data Json a = Val a | Obj [(String, Json a)]

Я знаю, что тип должен содержать 2 функции, по одной для каждого из случаев Val и Obj.Что я должен учитывать при создании сгиба?Я надеюсь, что мой вопрос имеет смысл.Я только что натолкнулся на множество различных типов данных, где его попросили написать функцию свертывания для типа данных, и я, похоже, не нашел шаблон.

Ответы [ 2 ]

3 голосов
/ 20 июня 2019

Как отметил Вилем Ван Онсем в (теперь удаленном) комментарии, то, что вы пытаетесь реализовать, также называется катаморфизмом .Я написал кое-что о том, что, как я полагаю, вы можете назвать катаморфизмом для начинающих, на Имеет ли каждый тип уникальный катаморфизм? .Вы можете вывести катаморфизм для типа (или показать, что ни один не может существовать) достаточно механически.Если ваш тип имеет N конструкторов, функция сгиба должна принимать N + 1 аргументов: одно значение вашего типа и одну функцию для каждого конструктора.Каждая такая функция принимает один аргумент на поле, которое имеет соответствующий конструктор (или, если конструктор не имеет полей, она принимает обычное значение, которое вы можете представить как 0-разрядную функцию), и возвращает значение любого типа катаморфизмавозвращает.

Это сложно на словах, поэтому я скопирую соответствующий код из ответа, который я связал выше, в качестве примера: 

data X a b f = A Int b
             | B
             | C (f a) (X a b f)
             | D a

xCata :: (Int -> b -> r)
      -> r
      -> (f a -> r -> r)
      -> (a -> r)
      -> X a b f
      -> r
xCata a b c d v = case v of
  A i x -> a i x
  B -> b
  C f x -> c f (xCata a b c d x)
  D x -> d x

Обратите внимание, что каждая из функций (a,b, c, d) имеет один аргумент на поле в связанном конструкторе.В большинстве случаев вы просто вызываете функцию с каждым из полей конструктора ... но что происходит в случае C?Почему бы нам не написать c f x вместо c f (xCata a b c d x)?Вот где происходит рекурсия: задача cata состоит в том, чтобы рекурсивно пройти (сложить) все дерево, представленное вашим ADT, превратив каждое значение X a b f в результат типа r.К счастью, есть только один возможный способ сделать это преобразование: вызвать xCata с тем же набором функций, которые вы передали для начала.

0 голосов
/ 20 июня 2019

Общее руководство (для всех функций, которые работают не только с помощью ADT, но и сгибанием), будет "одно уравнение на конструктор": 

data MyType = Constructor1 Int | Constructor2 Float | Constructor3

myFunc :: MyType -> Int
myFunc (Constructor1 x) = ...
myFunc (Constructor2 y) = ...
myFunc Constructor3     = ...

Кроме того, наиболее правильным способом реализации функции сгиба будет объявление экземпляра Foldable для вашего типа.

...