Parameterizing properties with DerivingVia - Haskell

Welcome to the Functional Programming Zulip Chat Archive. You can join the chat here.

Heneli Ta'angafala Kailahi (SP2'17)

I’m working through Okasaki’s PFDS, and I've found myself using DerivingVia as a low hassle way of getting different flavors of the same datatype

Heneli Ta'angafala Kailahi (SP2'17)

I can write a "primary" instance that's parameterized by some ad-hoc property(set) for cases where I want derived instances to be different

Heneli Ta'angafala Kailahi (SP2'17)

To derive Min and Max Heaps off one instance, I just pulled the comparison out of Heap.merge

Heneli Ta'angafala Kailahi (SP2'17)
-- |Int-ranked min leftist heap yo
data LeftHeap' prio a =
  | T Int a (LeftHeap' prio a) (LeftHeap' prio a)
  deriving (Show, Eq, Functor, Foldable)
type LeftHeap a = LeftHeap' MinPolicy a

data MinPolicy
data MaxPolicy

class MergeOrd p where
    compareByPriority :: Ord a => a -> a -> Bool

instance MergeOrd MinPolicy where ...
instance MergeOrd MaxPolicy where ...

instance (MergeOrd prio) => Heap (LeftHeap' prio) where
    merge :: (Ord a) => LeftHeap' prio a -> LeftHeap' prio a -> LeftHeap' prio a
    merge h1 h2
    | comparePriority @prio h1 h2 = ...
      | otherwise                    = ...

-- |Leftist Heap w/ minimum values at head
newtype MinHeap a = MinHeap
  { unMinHeap :: LeftHeap' MinPolicy a }
  deriving stock (Show, Eq)
  deriving Heap via (LeftHeap' MinPolicy)

-- |Leftist Heap w/ maximum values at head
newtype MaxHeap a = MaxHeap
  { unMaxHeap :: LeftHeap' MaxPolicy a }
  deriving stock (Show, Eq)
  deriving Heap via (LeftHeap' MaxPolicy)
Heneli Ta'angafala Kailahi (SP2'17)

And again with Banker’s Queues to change the condition triggering rebalances

Heneli Ta'angafala Kailahi (SP2'17)
data F_lte_R     -- ^ Rebalance when size of front list is equal to size of rear
data TwoF_lte_R  -- ^ Rebalance when twice the size of front list is equal to size of rear

class BalanceCondition c where
  needsRebalance :: Int -> Int -> Bool

instance BalanceCondition F_lte_R where ...
instance BalanceCondition TwoF_lte_R where ...

instance (BalanceCondition invariant) => Queue (BankersQueue' invariant) where
    ... -- some code branching on `needsRebalance @invariant`

type BankersQueue a = BankersQueue' F_lte_R a

newtype LessMovementBQ a = LessMovementBQ
  { unLessMovementBQ :: (BankersQueue' TwoF_lte_R a) }
  deriving stock (Show, Eq, Functor, Foldable)
  deriving Queue via (BankersQueue' TwoF_lte_R)
Heneli Ta'angafala Kailahi (SP2'17)

I’m sure I could have done some clever type-level stuffs by feeding the list sizes to BalanceCondition

Heneli Ta'angafala Kailahi (SP2'17)

But I’m content for now with how much boilerplate I saved and how simple the resulting code was

Heneli Ta'angafala Kailahi (SP2'17)

I bet there’s more fun to be had stacking properties encoding via style, and using GDP-style naming of properties