{-# LANGUAGE DeriveFoldable       #-}
{-# LANGUAGE DeriveFunctor        #-}
{-# LANGUAGE LambdaCase           #-}
{-# LANGUAGE StandaloneDeriving   #-}
{-# LANGUAGE UndecidableInstances #-}

module LogicRecSchemes where

import Data.Bifunctor
import Data.Foldable
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set)
import qualified Data.Set as Set

newtype Fix f = Fix { unFix :: f (Fix f) }

deriving instance (Eq (f (Fix f)))   => Eq (Fix f)
deriving instance (Ord (f (Fix f)))  => Ord (Fix f)
deriving instance (Show (f (Fix f))) => Show (Fix f)

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = go
  where
    go = alg . fmap go . unFix

data PropositionF a b =
    Var a
  | Not b
  | And b b
  | Or b b
  | If b b
  | Iff b b
  deriving (Eq, Functor, Foldable, Ord, Show)

type Proposition a = Fix (PropositionF a)

instance Bifunctor PropositionF where
  bimap f g = \case
    Var a    -> Var (f a)
    Not b    -> Not (g b)
    And b b' -> And (g b) (g b')
    Or b b'  -> Or (g b) (g b')
    If b b'  -> If (g b) (g b')
    Iff b b' -> Iff (g b) (g b')

(==>) :: Bool -> Bool -> Bool
(==>) True False = False
(==>) _    _     = True

evalCata :: Ord var => Map var Bool -> Proposition var -> Bool
evalCata ctx = cata (alg . bimap (ctx Map.!) id)
  where
    alg = \case
      Var a    -> a
      Not b    -> not b
      And b b' -> b && b'
      Or b b'  -> b || b'
      If b b'  -> b ==> b'
      Iff b b' -> b == b'

-- Example of where recursion schemes will come in handy later
collectVars :: Ord a => Proposition a -> Set a
collectVars = cata alg
  where
    alg = \case
      Var x -> Set.singleton x
      other -> Data.Foldable.fold other
