'Default Behavior' для рекурсивных типов данных Haskell

Я пытаюсь написать решатель пропозициональной логики на Haskell. Я представляю логические выражения с рекурсивным типом данных под названием «Sentence», который имеет несколько подтипов для различных операций - «AndSentence», «OrSentence» и т. Д. Итак, я предполагаю, что это дерево с несколькими типами узлов, каждый из которых имеет 0, 1, или 2 детей.

Кажется, что это работает, но часть кода в некотором роде повторяется, и я думаю, что должен быть лучший способ выразить это. В основном у меня есть несколько функций, где «поведение по умолчанию» - просто заставить функцию рекурсивно воздействовать на дочерние элементы узла, достигая дна на определенных типах узлов (обычно это «AtomicSentences», которые являются листьями). Поэтому я пишу такую ​​функцию:

imply_remove :: Sentence Symbol -> Sentence Symbol
imply_remove (ImplySentence s1 s2) = OrSentence (NotSentence (imply_remove s1)) (imply_remove s2)
imply_remove (AndSentence s1 s2) = AndSentence (imply_remove s1) (imply_remove s2)
imply_remove (OrSentence s1 s2) = OrSentence (imply_remove s1) (imply_remove s2)
imply_remove (NotSentence s1) = NotSentence (imply_remove s1)
imply_remove (AtomicSentence s1) = AtomicSentence s1

и мне нужен более лаконичный способ написания строк для «AndSentence», «OrSentence» и «NotSentence».

Похоже, что функторы похожи на то, что я хочу, но это не сработало ... Я хочу воздействовать на поддеревья, а не на некоторые значения, содержащиеся в каждом узле поддеревьев.

Есть ли правильный способ сделать это? Или более естественный способ структурировать мои данные?


haskell recursive-datastructures functor
person rwturner    schedule 22.03.2015    source источник
comment
Я бы посоветовал использовать синтаксическую библиотеку.   -  person crockeea    schedule 23.03.2015

Ответы (3)


arrow_upward
3
arrow_downward

Вы можете написать функцию по умолчанию, которая определяет, как следует обращаться с символом, если к нему не применяется преобразование:

default_transformation :: (Sentence Symbol -> Sentence Symbol) -> Sentence Symbol -> Sentence Symbol
default_transformation f (ImplySentence s1 s2) = ImplySentence (f s1) (f s2)
default_transformation f (AndSentence s1 s2) = AndSentence (f s1) (f s2)
default_transformation f (OrSentence s1 s2) = OrSentence (f s1) (f s2)
default_transformation f (NotSentence s1) = NotSentence (f s1)
default_transformation f (AtomicSentence s1) = AtomicSentence s1

Функция принимает в качестве параметра конкретное преобразование.

Если вы пишете свое конкретное преобразование, вам нужно только записать случаи, которые отличаются от значений по умолчанию, и добавить значение по умолчанию в качестве последнего случая:

imply_remove :: Sentence Symbol -> Sentence Symbol
imply_remove (ImplySentence s1 s2) = OrSentence (NotSentence (imply_remove s1)) (imply_remove s2)
imply_remove s = default_transformation imply_remove s

Преимущество этого подхода в том, что его, возможно, проще реализовать, поскольку он не требует никаких зависимостей.

person bmaderbacher    schedule 22.03.2015

arrow_upward
5
arrow_downward

Это выглядит как хороший случай для схем рекурсии.

Во-первых, мы описываем ваш Sentence sym тип как фиксированную точку на уровне типа подходящего функтора.

{-# LANGUAGE DeriveFunctor, LambdaCase #-}

import Data.Functor.Foldable  -- from the recursion-schemes package

-- The functor describing the recursive data type
data SentenceF sym r
   = AtomicSentence sym
   | ImplySentence r r
   | AndSentence r r
   | OrSentence r r
   | NotSentence r
   deriving (Functor, Show)

-- The original type recovered via a fixed point
type Sentence sym = Fix (SentenceF sym)

Вышеупомянутый тип Sentence sym почти идентичен исходному, за исключением того, что все должно быть заключено в Fix. Адаптация исходного кода для использования этого типа полностью механическая: там, где мы использовали (Constructor ...), теперь мы используем Fix (Constructor ...). Например

type Symbol = String

-- A simple formula: not (p -> (p || q))
testSentence :: Sentence Symbol
testSentence = 
   Fix $ NotSentence $
      Fix $ ImplySentence
         (Fix $ AtomicSentence "p")
         (Fix $ OrSentence
            (Fix $ AtomicSentence "p")
            (Fix $ AtomicSentence "q"))

Вот ваш исходный код с его дублированием (усугубляемым дополнительными Fixes).

-- The original code, adapted
imply_remove :: Sentence Symbol -> Sentence Symbol
imply_remove (Fix (ImplySentence s1 s2)) =
  Fix $ OrSentence (Fix $ NotSentence (imply_remove s1)) (imply_remove s2)
imply_remove (Fix (AndSentence s1 s2)) =
  Fix $ AndSentence (imply_remove s1) (imply_remove s2)
imply_remove (Fix (OrSentence s1 s2)) =
  Fix $ OrSentence (imply_remove s1) (imply_remove s2)
imply_remove (Fix (NotSentence s1)) =
  Fix $ NotSentence (imply_remove s1)
imply_remove (Fix (AtomicSentence s1)) =
  Fix $ AtomicSentence s1

Давайте проведем тест, оценив imply_remove testSentence: результат соответствует нашим ожиданиям:

 -- Output: not ((not p) || (p || q))
 Fix (NotSentence
   (Fix (OrSentence
      (Fix (NotSentence (Fix (AtomicSentence "p"))))
      (Fix (OrSentence
         (Fix (AtomicSentence "p"))
         (Fix (AtomicSentence "q")))))))

А теперь воспользуемся ядерным оружием, заимствованным из рекурсивных схем:

imply_remove2 :: Sentence Symbol -> Sentence Symbol
imply_remove2 = cata $ \case
   -- Rewrite ImplySentence as follows
   ImplySentence s1 s2 -> Fix $ OrSentence (Fix $ NotSentence s1) s2
   -- Keep everything else as it is (after it had been recursively processed)
   s -> Fix s

Если мы запустим тест imply_remove2 testSentence, мы получим тот же результат, что и исходный код.

Что делает cata? Грубо говоря, когда он применяется к функции, такой как cata f, он создает катаморфизм, то есть функцию, которая

  1. разделяет формулу на подкомпоненты
  2. рекурсивно применить cata f к найденным подкомпонентам
  3. собирает преобразованные компоненты в формулу
  4. передает эту последнюю формулу (с обработанными подформулами) в f, чтобы можно было затронуть самую верхнюю связку

Последний шаг - это тот, который выполняет фактическую работу. \case выше выполняет только желаемое преобразование. Все остальное обрабатывается cata (и экземпляром Functor, который был создан автоматически).

С учетом всего вышесказанного, я бы никому не рекомендовал легко переходить на recursion-schemes. Использование cata может привести к очень элегантному коду, но требует понимания задействованного механизма, что, возможно, не сразу понять (это, конечно, не для меня).

person chi    schedule 22.03.2015

arrow_upward
3
arrow_downward

То, что вы ищете, в Haskell называется «общим программированием»: https://wiki.haskell.org/Generics < / а>; ранняя форма называлась «Scrap Your Boilerplate», которую вы, возможно, захотите отправить в Google. Я не тестировал это, но думаю, если вы используете Uniplate модули Data.Generics.Uniplate и Data.Generics.Uniplate.Data вы можете определить imply_remove как

imply_remove = transform w where
    w (ImplySentence s1 s2) = OrSentence (NotSentence s1) s2
    w s = s

transform выполняет рекурсию за вас.

person Jonathan Cast    schedule 22.03.2015