generic-fold.hs

class ToFrom f where
  to :: List2 a -> f a
  from :: f a -> List2 a

instance ToFrom Maybe where
  to End = Nothing
  to (Elem x _) = Just x
  from Nothing = End
  from (Just x) = Elem x End

instance ToFrom [] where
  to End = []
  to (Elem x xs) = x: to xs
  from [] = End
  from (x:xs) = Elem x (from xs)

{-

*Main> to (Elem 3 (Elem 4 End)) :: Maybe Int
Just 3
*Main> to (Elem 3 (Elem 4 End)) :: [Int]
[3,4]
*Main> from (to (Elem 3 (Elem 4 End)) :: Maybe Int)
Elem 3 End
*Main> from (to (Elem 3 (Elem 4 End)) :: [Int])
Elem 3 (Elem 4 End)

-}


-- generic algorithms (Foldable, Traversable, ...)
countChange :: (Ord a, Foldable f, Functor f, Num a) => f a -> a -> Maybe [a]
countChange coins target = bfs (add_one_coin `pruning` (> target)) (== target) 0
  where add_one_coin amt = fmap (+ amt) coins

countChangeProperty xs x = all (>0) xs && x > 0 ==> countChange xs x == countChange (from xs) x

{-

  *Main> :t countChangeProperty
  countChangeProperty
    :: (Foldable f, Ord a, Num a, Functor f, ToFrom f) =>
       f a -> a -> Property

-}