Предложения по сокращению ассигнований (и работы) в этой функции Haskell

Question

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

import qualified Data.Set as S 
import qualified Data.IntMap.Strict as M 
import Data.Ord 
import Data.Monoid 

data Atom = Neg { index :: Int } 
      | Pos { index :: Int } 
      deriving (Eq, Ord, Show, Read) 

newtype Clause = Clause { atoms :: S.Set Atom } 
    deriving (Eq, Show, Read) 

instance Ord Clause where 
    compare = comparing (Down . S.size . atoms) <> comparing atoms 

newtype Form = Form { clauses :: S.Set Clause } 
    deriving (Eq, Ord, Show, Read) 

type Interpretation = M.IntMap Bool 

-- the function of interest 
interpret :: Interpretation -> Form -> Maybe Bool 
interpret interp = evalForm 
    where evalAtom x@(Pos _) = M.lookup (index x) interp 
     evalAtom x@(Neg _) = not <$> M.lookup (index x) interp 
     evalClause (Clause x) 
      | S.member (Just False) evaluated = Just False 
      | evaluated == S.singleton (Just True) = Just True 
      | otherwise = Nothing 
      where evaluated = S.map evalAtom x 
     evalForm (Form x) 
      | S.member (Just True) evaluated = Just True 
      | evaluated == S.singleton (Just False) = Just False 
      | otherwise = Nothing 
      where evaluated = S.map evalClause x 

После профилированного моя программа Haskell, я обнаружил, что это распределение interpret составляет почти 40% всех распределений в моей программе (а также около 40% работы ЦП).

Есть ли способ уменьшить либо объем работы interpret, либо сумму, которую он выделяет? Это может потенциально выиграть у меня большие выигрыши в производительности (которые мне действительно понадобятся, поскольку мне нужно много раз запускать этот код для экспериментов).

Answer 1

Я бы экспериментировал с S.foldr.

Из вашего кода это выглядит так, как будто это AND-предложения, поэтому я предполагаю, что пустое предложение ложно.

evalClause (Clause x) = S.foldr f (Just False) $ S.map evalAtom x 
    where f b@(Just False) _    = b 
      f (Just True) y    = y 
      f Nothing  y@(Just False) = y 
      f Nothing  y    = Nothing 

и аналогичный для evalForm.

Возможно, было бы полезно использовать списки, а не наборы. Наборы, как реализовано, строги, и (я думаю) не будут инициировать некоторые оптимизации, такие как fusion/deorestation/etc. Списки лениво производятся и должны вести себя лучше в таком виде кода.

evalClause (Clause x) = foldr f (Just False) . map evalAtom $ S.toList x 
    ... 

Answer 2

Наблюдение:

Maybe Bool может иметь только три возможных значения - Nothing, Just False и Just True.

evaluated в обоих evalClause и evalForm имеют типа Set (Maybe Bool), который может быть представлен с тремя битами, которые умещаются в Int.

Я бы определил:

data MaybeBool = Nuthin | JustFalse | JustTrue 
    deriving (Eq, Ord, Enum, Bounded, Show, Read) 

и изменить подпись intepret возвратной MaybeBool

Затем определяют evaluated как BitSet, как это:

import Data.Bits 

evaluated = foldl' combine 0 (map evalAtom (S.toList x)) 
    where combine s a = s .|. (1 `shiftLeft` fromEnum a) 

evaluated будет Int между 0 и 7 с битом 0, если Nutin в наборе, бит 1 установлен, если JustFalse в наборе и бит 2, если JustTrue в комплекте. Это позволит исключить распределение наборов из ваших вычислений.