faldable-testing.hs

import Test.QuickCheck
import Algorithm.Search

...

-- conversion util
to :: List2 a -> [a]
to End = []
to (Elem x xs) = x: to xs

from :: [a] -> List2 a
from [] = End
from (x:xs) = Elem x (from xs)


-- 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

{-

  Using lists:
  > countChange [25, 10, 5, 1] 65
  Just [25,50,60,65]
  
  Using List2:
  > countChange (from [25, 10, 5, 1]) 65
  Just [5,15,40,65]

-}

-- as general property
countChangeProperty xs x = all (>0) xs && x > 0 ==> countChange xs x == countChange (from xs) x

{-

  > quickCheck countChangeProperty
  *** Failed! Falsified (after 43 tests and 13 shrinks):
  [1,2]
  15

-}