Оптимизация соответствия шаблонов на Haskell - PullRequest
Новая
       20

Оптимизация соответствия шаблонов на Haskell

0 голосов
/ 17 декабря 2018

Я начал изучать Haskell для университетского курса, и я написал функцию с сопоставлением с образцом (называется Simplify).Но я немного не уверен, как мне оптимизировать мой код, так как я чувствую, что он слишком жестко запрограммирован.

В любом случае, это код, который я написал: 

data Proposition = Proposition Bool
                | Const Bool
                | Var String
                | And Proposition Proposition
                | Or Proposition Proposition
                | Not Proposition deriving (Show, Eq)


simplify :: Proposition -> Proposition

simplify (And _ (Const False)) = (Const False)
simplify (And (Const False) _) = (Const False)
simplify (And p (Const True)) = simplify p
simplify (And (Const True) p) = simplify p
simplify (Or _ (Const True)) = (Const True)
simplify (Or (Const True) _) = (Const True)
simplify (Or a b) = simplify (Or (simplify a) (simplify b))
simplify (Const b) = (Const b)
simplify (Var v) = (Var v)
simplify (Not (Const True)) = (Const False)
simplify (Not (Const False)) = (Const True)
simplify (Not p) = simplify (Not (simplify p))

1 Ответ

0 голосов
/ 17 декабря 2018

Похоже, вы обычно хотите следовать шаблону

  1. Упростить все подвыражения.
  2. Упростить выражение.

Для меня,это предполагает пакет recursion-schemes. 

{-# language TemplateHaskell, TypeFamilies, DeriveTraversable #-}
import Data.Functor.Foldable
import Data.Functor.Foldable.TH

data Proposition
  = Const Bool
  | Var String
  | And Proposition Proposition
  | Or Proposition Proposition
  | Not Proposition
  deriving (Show, Eq)

makeBaseFunctor ''Proposition

Это волшебным образом генерирует тип 

data PropositionF x
  = ConstF Bool
  | VarF String
  | AndF x x
  | OrF x x
  | NotF x
  deriving (Functor, Foldable, Traversable)

вместе с некоторыми связанными экземплярами.Обратите внимание, что PropositionF заменяет каждое вхождение Proposition копией параметра типа.Теперь вы можете написать 

simplify :: Proposition -> Proposition
simplify = cata go
  where
    go :: PropositionF Proposition -> Proposition

    go (AndF (Const True) x) = x
    go (AndF f@(Const False) _) = f
    go (AndF x (Const True)) = x
    go (AndF _ f@(Const False)) = f

    go (OrF t@(Const True) _) = t
    go (OrF (Const False) x) = x
    go (OrF _ t@(Const True)) = t
    go (OrF x (Const False)) = x

    go (NotF (Const x)) = Const (not x)

    go x = embed x -- Catch-all: no rules apply

Все рекурсивное упрощение обрабатывается «автоматически», а все случаи «ничего интересного здесь» обрабатываются в одну строку.

...