first-class-families 0.6.0.0 → 0.7.0.0

raw patch · 6 files changed

+260/−21 lines, 6 filesdep +Globdep +doctestdep ~basePVP ok

version bump matches the API change (PVP)

Dependencies added: Glob, doctest

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• CHANGELOG.md +8/−1
• README.md +3/−2
• first-class-families.cabal +14/−1
• src/Fcf/Classes.hs +16/−0
• src/Fcf/Data/List.hs +203/−17
• test/doctest.hs +16/−0

@@ -1,6 +1,13 @@+# 0.7.0.0++- Add `Unfoldr`, `Concat`, `ConcatMap`, `Replicate`, `Take`, `Drop`,+  `TakeWhile`, `DropWhile`, `Reverse` to `Data.List`. (gspia)+- Change `Elem`, `Lookup`, `Zip` to be `data` instead of `type` synonyms.+- Fix performance of `Filter` and `Find`.+ # 0.6.0.0 -- Add `Fcf.Utils.Case` and `(Fcf.Combinators.>>=)`+- Add `Fcf.Utils.Case` and `(Fcf.Combinators.>>=)` (TheMatten) - Deprecate `Fcf.Bool.Guarded` - GHC 8.8 compatibility 

@@ -8,7 +8,7 @@ type instance FromMaybe a ('Just b) = b ``` -With first-class-families, it translates to a `data` declaration+With first-class-families (fcfs), it translates to a `data` declaration and instances for a single `Eval` family:  ```haskell@@ -19,7 +19,8 @@ type instance Eval (FromMaybe a ('Just b)) = b ``` -That way, the `FromMaybe` constructor can be passed to higher-order fcfs.+That way, the `FromMaybe` constructor can be partially applied,+and passed to higher-order fcfs such as `Map`:  ```haskell Eval (Map (FromMaybe 0) '[ 'Just 1, 'Nothing ])  =  '[ 1, 0 ] :: [Nat]

@@ -1,5 +1,5 @@ name:                first-class-families-version:             0.6.0.0+version:             0.7.0.0 synopsis:   First class type families description:@@ -46,6 +46,19 @@   build-depends:     base,     first-class-families++test-suite fcf-doctest+  type:                exitcode-stdio-1.0+  hs-source-dirs:      test+  main-is:             doctest.hs+  default-language:    Haskell2010+  if impl(ghc >= 8.6)+    build-depends:+      base,+      doctest,+      Glob+  else+    buildable: False  source-repository head   type:     git

@@ -11,9 +11,25 @@   , Bimap   ) where + import Fcf.Core ++-- $+-- >>> import Fcf.Core++ -- | Type-level 'fmap' for type-level functors.+--+-- === __Example__+--+-- >>> import Fcf.Data.Nat+-- >>> import qualified GHC.TypeLits as TL+-- >>> data AddMul :: Nat -> Nat -> Exp Nat+-- >>> type instance Eval (AddMul x y) = (x TL.+ y) TL.* (x TL.+ y)+-- >>> :kind! Eval (Map (AddMul 2) '[0, 1, 2, 3, 4])+-- Eval (Map (AddMul 2) '[0, 1, 2, 3, 4]) :: [Nat]+-- = '[4, 9, 16, 25, 36] data Map :: (a -> Exp b) -> f a -> Exp (f b)  -- []

@@ -9,9 +9,12 @@ -- | Lists. module Fcf.Data.List   ( Foldr+  , Unfoldr   , UnList   , Cons   , type (++)+  , Concat+  , ConcatMap   , Filter   , Head   , Last@@ -19,6 +22,7 @@   , Init   , Null   , Length+  , Replicate   , Find   , FindIndex   , Elem@@ -28,6 +32,11 @@   , Zip   , Unzip   , Cons2+  , Take+  , Drop+  , TakeWhile+  , DropWhile+  , Reverse   ) where  import qualified GHC.TypeLits as TL@@ -39,9 +48,33 @@ import Fcf.Data.Nat import Fcf.Utils +-- $+-- >>> import Fcf.Core+-- >>> import Fcf.Combinators+-- >>> import qualified GHC.TypeLits as TL+++-- | Append an element for type-level lists.+--+-- === __Example__+--+-- >>> :kind! Eval (Cons 1 '[2, 3])+-- Eval (Cons 1 '[2, 3]) :: [Nat]+-- = '[1, 2, 3]+-- >>> :kind! Eval (Cons Int '[Char, Maybe Double])+-- Eval (Cons Int '[Char, Maybe Double]) :: [*]+-- = '[Int, Char, Maybe Double]+-- data Cons :: a -> [a] -> Exp [a] type instance Eval (Cons a as) = a ': as +-- | Foldr for type-level lists.+--+-- === __Example__+--+-- >>> :kind! Eval (Foldr (+) 0 '[1, 2, 3, 4])+-- Eval (Foldr (+) 0 '[1, 2, 3, 4]) :: Nat+-- = 10 data Foldr :: (a -> b -> Exp b) -> b -> [a] -> Exp b type instance Eval (Foldr f y '[]) = y type instance Eval (Foldr f y (x ': xs)) = Eval (f x (Eval (Foldr f y xs)))@@ -50,16 +83,68 @@ data UnList :: b -> (a -> b -> Exp b) -> [a] -> Exp b type instance Eval (UnList y f xs) = Eval (Foldr f y xs) +-- Helper for the Unfoldr.+data UnfoldrCase :: (b -> Exp (Maybe (a, b))) -> Maybe (a, b) -> Exp [a]+type instance Eval (UnfoldrCase f ('Just ab)) =+  Eval (Fst ab) ': Eval (Unfoldr f (Eval (Snd ab)))+type instance Eval (UnfoldrCase _ 'Nothing) = '[]++-- | Type-level Unfoldr.+--+-- === __Example__+--+-- >>> data ToThree :: Nat -> Exp (Maybe (Nat, Nat))+-- >>> :{+-- type instance Eval (ToThree b) =+--   If (Eval (b Fcf.>= 4))+--     'Nothing+--     ('Just '(b, b TL.+ 1))+-- :}+--+-- >>> :kind! Eval (Unfoldr ToThree 0)+-- Eval (Unfoldr ToThree 0) :: [Nat]+-- = '[0, 1, 2, 3]+--+-- See also the definition of `Replicate`.+data Unfoldr :: (b -> Exp (Maybe (a, b))) -> b -> Exp [a]+type instance Eval (Unfoldr f c) = Eval (UnfoldrCase f (f @@ c))++-- | Type-level list catenation.+--+-- === __Example__+--+-- >>> :kind! Eval ('[1, 2] ++ '[3, 4])+-- Eval ('[1, 2] ++ '[3, 4]) :: [Nat]+-- = '[1, 2, 3, 4]+-- data (++) :: [a] -> [a] -> Exp [a] type instance Eval ((++) '[] ys) = ys type instance Eval ((++) (x ': xs) ys) = x ': Eval ((++) xs ys) +-- | Concat for lists.+--+-- === __Example__+--+-- >>> :kind! Eval (Concat ( '[ '[1,2], '[3,4], '[5,6]]))+-- Eval (Concat ( '[ '[1,2], '[3,4], '[5,6]])) :: [Nat]+-- = '[1, 2, 3, 4, 5, 6]+-- >>> :kind! Eval (Concat ( '[ '[Int, Maybe Int], '[Maybe String, Either Double Int]]))+-- Eval (Concat ( '[ '[Int, Maybe Int], '[Maybe String, Either Double Int]])) :: [*]+-- = '[Int, Maybe Int, Maybe String, Either Double Int]+--+data Concat :: [[a]] -> Exp [a]+type instance Eval (Concat lsts) = Eval (Foldr (++) '[] lsts)++-- | ConcatMap for lists.+data ConcatMap :: (a -> Exp [b]) -> [a] -> Exp [b]+type instance Eval (ConcatMap f lst) = Eval (Concat (Eval (Map f lst)))+ data Filter :: (a -> Exp Bool) -> [a] -> Exp [a] type instance Eval (Filter _p '[]) = '[] type instance Eval (Filter p (a ': as)) =-  If (Eval (p a))-    (a ': Eval (Filter p as))-    (Eval (Filter p as))+  Eval (If (Eval (p a))+    ('(:) a <$> Filter p as)+    (Filter p as))  data Head :: [a] -> Exp (Maybe a) type instance Eval (Head '[]) = 'Nothing@@ -88,12 +173,30 @@ type instance Eval (Length '[]) = 0 type instance Eval (Length (a ': as)) = 1 TL.+ Eval (Length as) +-- Helper for the Replicate.+data NumIter :: a -> Nat -> Exp (Maybe (a, Nat))+type instance Eval (NumIter a s) =+  If (Eval (s > 0))+    ('Just '(a, s TL.- 1))+    'Nothing+++-- | Type-level `Replicate` for lists.+--+-- === __Example__+--+-- >>> :kind! Eval (Replicate 4 '("ok", 2))+-- Eval (Replicate 4 '("ok", 2)) :: [(TL.Symbol, Nat)]+-- = '[ '("ok", 2), '("ok", 2), '("ok", 2), '("ok", 2)]+data Replicate :: Nat -> a -> Exp [a]+type instance Eval (Replicate n a) = Eval (Unfoldr (NumIter a) n)+ data Find :: (a -> Exp Bool) -> [a] -> Exp (Maybe a) type instance Eval (Find _p '[]) = 'Nothing type instance Eval (Find p (a ': as)) =-  If (Eval (p a))-    ('Just a)-    (Eval (Find p as))+  Eval (If (Eval (p a))+    (Pure ('Just a))+    (Find p as))  -- | Find the index of an element satisfying the predicate. data FindIndex :: (a -> Exp Bool) -> [a] -> Exp (Maybe Nat)@@ -103,14 +206,24 @@     (Pure ('Just 0))     (Map ((+) 1) =<< FindIndex p as)) -type Elem a as = IsJust =<< FindIndex (TyEq a) as+-- | Type-level `Elem` for lists.+--+-- === __Example__+--+-- >>> :kind! Eval (Elem 1 '[1,2,3])+-- Eval (Elem 1 '[1,2,3]) :: Bool+-- = 'True+-- >>> :kind! Eval (Elem 1 '[2,3])+-- Eval (Elem 1 '[2,3]) :: Bool+-- = 'False+--+data Elem :: a -> [a] -> Exp Bool+type instance Eval (Elem a as) = Eval (IsJust =<< FindIndex (TyEq a) as)  -- | Find an element associated with a key.--- @--- 'Lookup' :: k -> [(k, b)] -> 'Exp' ('Maybe' b)--- @-type Lookup (a :: k) (as :: [(k, b)]) =-  (Map Snd (Eval (Find (TyEq a <=< Fst) as)) :: Exp (Maybe b))+data Lookup :: k -> [(k, b)] -> Exp (Maybe b)+type instance Eval (Lookup (a :: k) (as :: [(k, b)])) =+  Eval (Map Snd (Eval (Find (TyEq a <=< Fst) as)) :: Exp (Maybe b))  -- | Modify an element at a given index. --@@ -129,15 +242,88 @@ type instance Eval (ZipWith f (a ': as) (b ': bs)) =   Eval (f a b) ': Eval (ZipWith f as bs) --- |--- @--- 'Zip' :: [a] -> [b] -> 'Exp' [(a, b)]--- @-type Zip = ZipWith (Pure2 '(,))+data Zip :: [a] -> [b] -> Exp [(a, b)]+type instance Eval (Zip as bs) = Eval (ZipWith (Pure2 '(,)) as bs)  data Unzip :: Exp [(a, b)] -> Exp ([a], [b]) type instance Eval (Unzip as) = Eval (Foldr Cons2 '( '[], '[]) (Eval as))  data Cons2 :: (a, b) -> ([a], [b]) -> Exp ([a], [b]) type instance Eval (Cons2 '(a, b) '(as, bs)) = '(a ': as, b ': bs)+++-- | Type-level list take.+--+-- === __Example__+--+-- >>> :kind! Eval (Take 2 '[1,2,3,4,5])+-- Eval (Take 2 '[1,2,3,4,5]) :: [Nat]+-- = '[1, 2]+data Take :: Nat -> [a] -> Exp [a]+type instance Eval (Take n as) = Take_ n as++type family Take_ (n :: Nat) (xs :: [a]) :: [a] where+  Take_ 0 _         = '[]+  Take_ _ '[]       = '[]+  Take_ n (x ': xs) = x ': Take_ (n TL.- 1) xs++-- | Type-level list drop.+--+-- === __Example__+--+-- >>> :kind! Eval (Drop 2 '[1,2,3,4,5])+-- Eval (Drop 2 '[1,2,3,4,5]) :: [Nat]+-- = '[3, 4, 5]+data Drop :: Nat -> [a] -> Exp [a]+type instance Eval (Drop n as) = Drop_ n as++type family Drop_ (n :: Nat) (xs :: [a]) :: [a] where+  Drop_ 0 xs        = xs+  Drop_ _ '[]       = '[]+  Drop_ n (x ': xs) = Drop_ (n TL.- 1) xs++-- | Type-level list takeWhile.+--+-- === __Example__+--+-- >>> :kind! Eval (TakeWhile ((>=) 3) '[1, 2, 3, 4, 5])+-- Eval (TakeWhile ((>=) 3) '[1, 2, 3, 4, 5]) :: [Nat]+-- = '[1, 2, 3]+data TakeWhile :: (a -> Exp Bool) -> [a] -> Exp [a]+type instance Eval (TakeWhile p '[]) = '[]+type instance Eval (TakeWhile p (x ': xs)) =+  Eval (If (Eval (p x))+      ('(:) x <$> TakeWhile p xs)+      (Pure '[]))++-- | Type-level list dropWhile.+--+-- === __Example__+--+-- :kind! Eval (DropWhile ((>=) 3) '[1, 2, 3, 4, 5])+-- Eval (DropWhile ((>=) 3) '[1, 2, 3, 4, 5]) :: [Nat]+-- = '[4, 5]+data DropWhile :: (a -> Exp Bool) -> [a] -> Exp [a]+type instance Eval (DropWhile p '[]) = '[]+type instance Eval (DropWhile p (x ': xs)) =+  Eval (If (Eval (p x))+      (DropWhile p xs)+      (Pure (x ': xs)))+++-- Helper for Reverse. This corresponds to rev in the data list lib.+data Rev :: [a] -> [a] -> Exp [a]+type instance Eval (Rev '[]       ys) = ys+type instance Eval (Rev (x ': xs) ys) = Eval (Rev xs (x ': ys))+++-- | Type-level list reverse.+--+-- === __Example__+--+-- >>> :kind! Eval (Reverse '[1,2,3,4,5])+-- Eval (Reverse '[1,2,3,4,5]) :: [Nat]+-- = '[5, 4, 3, 2, 1]+data Reverse :: [a] -> Exp [a]+type instance Eval (Reverse l) = Eval (Rev l '[]) 

@@ -0,0 +1,16 @@+import System.FilePath.Glob (glob)+import Test.DocTest++exts :: [String]+exts =+  [ "-XDataKinds"+  , "-XKindSignatures"+  , "-XTypeFamilies"+  , "-XTypeOperators"+  , "-XUndecidableInstances"+  ]++main :: IO ()+main = do+  xs <- glob "src/**/*.hs"+  doctest (exts ++ xs)