packages feed

polydata (empty) → 0.1.0.0

raw patch · 7 files changed

+552/−0 lines, 7 filesdep +basedep +constraint-manipdep +hspecsetup-changed

Dependencies added: base, constraint-manip, hspec, indextype

Files

+ LICENSE view
@@ -0,0 +1,19 @@+Copyright 2017 Clinton Mead++Permission is hereby granted, free of charge, to any person obtaining a copy of+this software and associated documentation files (the "Software"), to deal in+the Software without restriction, including without limitation the rights to+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies+of the Software, and to permit persons to whom the Software is furnished to do+so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in all+copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE+SOFTWARE.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ polydata.cabal view
@@ -0,0 +1,35 @@+name:                 polydata+version:              0.1.0.0+synopsis:             Wrap together data and it's constraints.+description:+  This package allows one to pass data, particularly functions, together with a constraint which describes how+  polymorphic that data is. This constraint can then be used in a generic way to produce quite polymorphic functions,+  for example, a "map" function that works on a pair of two different types, +license: MIT+license-file: LICENSE+copyright: Clinton Mead (2017)+author:               Clinton Mead+maintainer:           clintonmead@gmail.com+category:             Data+build-type:           Simple+cabal-version:        >=1.10+tested-with: GHC == 8.0.2+bug-reports: https://github.com/clintonmead/polydata/issues++source-repository head+  type: git+  location: https://github.com/clintonmead/polydata.git++library+  exposed-modules: Data.Poly, Data.Poly.Function, Data.Poly.Functor+  build-depends:        base == 4.9.*, indextype == 0.2.*, constraint-manip == 0.1.*+  hs-source-dirs:       src+  default-language:     Haskell2010++Test-Suite tests+  type: exitcode-stdio-1.0+  main-is: Tests.hs+  other-modules: Data.Poly, Data.Poly.Function, Data.Poly.Functor+  build-depends:        base == 4.9.*, indextype == 0.2.*, constraint-manip == 0.1.*, hspec == 2.4.*+  hs-source-dirs:       test, src+  default-language:     Haskell2010
+ src/Data/Poly.hs view
@@ -0,0 +1,215 @@+{-# LANGUAGE GADTs #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE ConstraintKinds #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE UndecidableSuperClasses #-}+{-# LANGUAGE FlexibleInstances #-}++{-|+This package allows one to wrap data in a type: 'Poly', which explicitly carries around that's type's polymorphism.++This idea is motivated by this problem:++How does one write a function @g@ such that++>>> g f (x,y) = (f x, f y)++that works for all @a@ and @b@ where @f a@ and @f b@ are valid.++Lets try some approaches in ghci:++>>> let g f (a,b) = (f a, f b)+>>> :t+g :: (t1 -> t) -> (t1, t1) -> (t, t)++No good. As untyped function arguments are by default monomorphic, we've forced the pair to have two elements+the same type.++We could try this:++>>> let g (f :: (forall a b. a -> b)) (a,b) = (f a, f b)+>>> :t g+g :: (forall a2 b. a2 -> b) -> (a1, a) -> (t1, t)++but the only function with type @(forall a b. a -> b)@ is @undefined@, so that's pretty useless.++Perhaps we could do this:++>>> let g (f :: (forall a. Num a => a -> a)) (a,b) = (f a, f b)+>>> :t g+g :: (Num t1, Num t) =>+     (forall a. Num a => a -> a) -> (t1, t) -> (t1, t)++This is nice, then we can do something like:++>>> let h = g (+2) (1::Int, 2.5::Float)+>>> h+(3,4.5)+>>> :t h+h :: (Int, Float)++However, this only works for Numeric functions now.++So what we're going to do is connect the function's constraints with the function itself,+so we get a definition of @g@ like this:++> g :: (c (a -> a'), c (b -> b')) => Poly c -> (a, b) -> (a' -> b')++And indeed you can see polymorphic map function that works on heterogeneous tuples in 'Data.Poly.Functor'.++The 'Poly' type is quite generic, and indeed "Data.Poly.Function"+has some helper functions for constructing polymorphic functions directly.+-}+module Data.Poly (+  Poly(Poly, getPoly),+  GetPolyConstraint,+  IsPoly+  )+where++import GHC.Exts (Constraint)+{-|+'Poly' has the following data definition:++> data Poly (c :: * -> Constraint) where+>   Poly :: { getPoly :: (forall a. c a => a) } -> Poly c++Haddock has trouble parsing it, presumably because it's confused by @(c :: * -> Constraint)@.++Here's a first example, which is a polymorphic version of 'toInteger':++> polyToInteger = Poly @((IsFunc 1) &&& ((Arg 0) `IxConstrainBy` Integral) &&& ((Result 1) `IxIs` Integer)) toInteger++So lets look from left to right for what constraints we're passing to 'polyToInteger':++> (IsFunc 1)++'Control.IndexT.Function.IsFunc' constrains a type to be a function, in this case of one variable++> ((Arg 0) `IxConstrainBy` Integral)++'Control.ConstraintManip.Arg' @0@ specifies the first argument (this is zero based)+'Control.ConstraintManip.IxConstrainBy' constrains the argument given to the constraint given,+in this case 'Integral'++> ((Result 1) `IxIs` Integer)++So the 'Control.ConstraintManip.Result' (of the one argument function) is 'Integer'.++So then we can do:++> getPoly polyToInteger (10 :: Int) -- (10 :: Integer)++Our second example is probably simpler:++> triple = Poly @((IsHomoFunc 1) &&& ((Arg 0) `IxConstrainBy` Num)) (*3)++'Control.IndexT.Function.IsHomoFunc' is like 'Control.IndexT.Function.IsFunc' but ensures the two arguments are the same.++'Control.ConstraintManip.IxConstrainBy' we've already seen. Note that here:++> (Arg 0) `IxConstrainBy` Num++and++> (Result 1) `IxConstrainBy` Num++have the same effect because the first argument and the result are already constrained to have the same type from+'Control.IndexT.Function.IsHomoFunc'.++Two more examples, with two arguments, are:++> add = Poly @((IsHomoFunc 2) &&& ((Arg 0) `IxConstrainBy` Num)) (+)++and++> eq = Poly @((IsHomoArgFunc 2) &&& ((Arg 0) `IxConstrainBy` Eq) &&& ((Result 2) `IxIs` Bool)) (==)++'Control.IndexT.Function.IsHomoArgFunc', unlike 'Control.IndexT.Function.IsHomoFunc', just specifies that the arguments are+identical, the result may be different.++At this point it's probably worth looking at "Data.Poly.Function", which has a range of convience functions for making the+above definitions easier.++If you've now looked at "Data.Poly.Function", you've seen two ways to define the constraints to pass to 'Poly':++1) Use the convienience functions in "Data.Poly.Function"+2) Combine constraints of one variable with '(Control.ConstraintManip.&&&)' as detailed above.++But sometimes these above two methods aren't flexible enough to generate the polymorphic constraint required.++Consider 'Data.Foldable.foldl''++> foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b++with something this complicated, its sometimes best to define the constraint directly ourselves.+So here it is:++> type FoldConstraint t = (+>   IsFunc 3 t, -- A fold is a function of three args+>   IndexT 1 t ~ ResultT 3 t, -- The second (i.e. arg 1) is equal to the result+>   IsFunc 2 (IndexT 0 t), -- the first argument (i.e. the fold function) is a function of two args+>   (IndexT 0 (IndexT 0 t)) ~ (ResultT 2 (IndexT 0 t)), -- the first argument of the function which is the first argument is the same as it's third+>   IndexT 1 t ~ (IndexT 0 (IndexT 0 t)), -- also, the first argument of the function which is the first argument is the same as the second argument of the function+>   IsData 1 (IndexT 2 t), -- the third argument is a data type with one variable+>   Foldable (GetConstructor1 (IndexT 2 t)), -- the constructor of that third argument is Foldable+>   IndexC 1 0 (IndexT 2 t) ~ IndexT 1 (IndexT 0 t) -- the parameter to the constructor of Foldable is the same as the second argument of the fold function+>   )++You'll want to look at the package "indextype" to get some details on these functions.++But if you go through the above slowly, you'll see that this constraint completely describes the sort of functions that+have the same signature as 'Data.Foldable.foldl''.++So then we can do this:++> class (FoldConstraint t) => FoldConstraintC t+> instance (FoldConstraint t) => FoldConstraintC t+>+> pfoldl' = Poly @FoldConstraintC foldl'+> polyFold (Poly foldFunc) =+>   (foldFunc (+) 0 [1,2,3], foldFunc (+) 0 [1.5,2.5,3.5], foldFunc (++) "" ["Hello", ", ", "World"])++And we can then do:++>>> (polyFold pfoldl') :: (Int, Float, String)+(6,7.5,"Hello, World")++Note that this wrapping approach preserves the polymorphism until inside the function.++At this point, you may ask, why not just define a new datatype with a polymorphic parameter each time you want to do this?++Well, firstly, you'd have to define a new datatype each time you want to pass a different type of function polymorphically,+which is a bit of boilerplate, although it's arguably less than this.++But more importantly, having a \"constraint\" on the type, instead of the actual type, allows as to use that constraint to+build more complex constraints.++A good example of that is 'Data.Poly.Functor.hmap'.++For complex functions, there can be a lot to write these constraints, but constraints are composable, so you can split+out common parts.++However, I have a feeling there is a mechanical way to generate these constraints using Template Haskell.+This will be my next addition to the library.+-}+data Poly (c :: * -> Constraint) where+  Poly :: { getPoly :: (forall a. c a => a) } -> Poly c++{-|+Gets the type of the constraint in a 'Poly'+-}+type family GetPolyConstraint a :: * -> Constraint where+  GetPolyConstraint (Poly c) = c++type family IsPolyT a :: Constraint where+  IsPolyT a = a ~ Poly (GetPolyConstraint a)++{-+Constraint that asserts @t@ is a @Poly u@ for some @u@.+-}+class (IsPolyT a) => IsPoly a+instance (IsPolyT a) => IsPoly a+
+ src/Data/Poly/Function.hs view
@@ -0,0 +1,138 @@+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE ConstraintKinds #-}+{-# LANGUAGE UndecidableSuperClasses #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE TypeOperators #-}++module Data.Poly.Function (+  -- $mkPolyDoc+  mkPolyHomoFunc1,+  mkPolyFunc1,+  mkPolyHomoFunc2,+  mkPolyHomoArgFunc2,+  -- $convinienceConstraintDocs+  Equal,+  Empty+  )++where++import Data.Poly (Poly(Poly))+import Control.IndexT (IndexT)+import Control.IndexT.Function (+  ResultT,+  IsFunc,+  IsHomoFunc,+  IsHomoArgFunc+  )++import Control.ConstraintManip (+  type (&&&),+  Arg, Result,+  IxConstrainBy+  )++{- $mkPolyDoc+The easiest way to use these mkPoly* functions is by adding the extension:++> \{\-# LANGUAGE TypeApplications #\-\}++at the top of your source file (<https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#visible-type-application GHC Documentation on the Type Application extension>).++Examples of this will be included in the documentation for each convience function.++Note that all of these convience functions are just type restricted versions of 'Poly', that's all,+and are all defined in this form:++> f = Poly++Also not that this is far from an exhaustive list of what can be done, there's a more general approach+described in the documentation for `Poly'+-}++{-|+'mkPolyHomoFunc1 simply represents a function from @t -> t@, possibly constrained.++For example, this is how to write a polymorphic version of "triple":++> mkPolyHomoFunc1 @Num (*3)++-}+mkPolyHomoFunc1 :: forall c. (forall t. c t => t -> t) -> Poly ((IsHomoFunc 1) &&& ((Arg 0) `IxConstrainBy` c))+mkPolyHomoFunc1 = Poly++{-|+'mkPolyFunc1 is for one argument functions with differing arguments.++For example, this is how to write a polymorphic version of 'toInteger':++> mkPolyFunc1 @Integral @(Equal Integer) toInteger++Note that something like @Just :: t -> Maybe t@ this convience function is not helpful for,+because the two constraints you pass here are separate.+-}+mkPolyFunc1 :: forall c1 c2. (forall t1 t2. (c1 t1, c2 t2) => t1 -> t2) -> Poly ((IsFunc 1) &&& ((Arg 0) `IxConstrainBy` c1) &&& ((Result 1) `IxConstrainBy` c2))+mkPolyFunc1 = Poly++{-|+'mkPolyHomoFunc2 simply represents a function from @t -> t -> t@, possibly constrained.++For example, this is how to write a polymorphic version of "add":++> mkPolyHomoFunc2 @Num (+)+-}+mkPolyHomoFunc2 :: forall c. (forall t. c t => t -> t -> t) -> Poly ((IsHomoFunc 2) &&& ((Arg 0) `IxConstrainBy` c))+mkPolyHomoFunc2 = Poly++{-|+'mkPolyArgFunc2 represents a function from @t -> t -> r@, with two constraints, one for the arguments, one for the result.++For example, this is how to write a polymorphic version of "eq":++> mkPolyHomoArgFunc2 @Eq @(Equal Bool) (==)+-}+mkPolyHomoArgFunc2 :: forall c1 c2. (forall t1 t2. (c1 t1, c2 t2) => t1 -> t1 -> t2) -> Poly ((IsHomoArgFunc 2) &&& ((Arg 0) `IxConstrainBy` c1) &&& ((Result 2) `IxConstrainBy` c2))+mkPolyHomoArgFunc2 = Poly+++class (IsFunc 1 f, c1 (IndexT 0 f), c2 (ResultT 1 f)) => PolyFunc1Constraints c1 c2 f+instance (IsFunc 1 f, c1 (IndexT 0 f), c2 (ResultT 1 f)) => PolyFunc1Constraints c1 c2 f++class (IsHomoFunc 1 f, c (IndexT 0 f)) => PolyHomoFunc1Constraints c f+instance (IsHomoFunc 1 f, c (IndexT 0 f)) => PolyHomoFunc1Constraints c f++{- $convinienceConstraintDocs+Below are some convience constraints that make it easier to write polymorphic functions.+-}++{-|+Handy type class for expressing an "is equal to" constraint, because as a class it can be partially applied.++For example, whilst @Num@ is a constraint function from @(* -> Constraint)@ such that @(Num t)@ succeeds only if+@t@ is a @Num@, @Equal Int@ is a constraint function such that @(Equal Int) t@ succeeds only if @t@ is an @Int@.++For example:++> mkPolyFunc1 @Integral @(Equal Integer) toInteger++Is a polymorphic 'toInteger' function.+-}+class (a ~ b) => Equal a b+instance (a ~ b) => Equal a b++{-|+The empty constraint:++> Empty a++always succeeds.+-}+class Empty a+instance Empty a++
+ src/Data/Poly/Functor.hs view
@@ -0,0 +1,76 @@+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE ConstraintKinds #-}++module Data.Poly.Functor (+  PolyFunctor, hmap, PolyFunctorConstraint+  )+where++import GHC.Exts (Constraint)+import Data.Poly (Poly(Poly))+import Control.IndexT (IndexT)+import Control.IndexT.Tuple (IsTuple)++type family PolyFunctorConstraint (c :: * -> Constraint) t :: Constraint++{-|+A very generic class for a map function on heterogeneous data structures (i.e. those with differing types).++This allows you to do things like:++>>> hmap triple (3 :: Int, 4.5 :: Float)+(9 :: Int, 13.5 :: Float)++'hmap' takes as it's function a 'Poly', as of course you'd want a polymorphic function.++The return type defined in the class is very vague, indeed it's just @t@ to be detailed in the instances,+because unlike a normal 'map' function, how 'hmap' changes the type depends a lot on the type it's applied to,+there's no simple @f a -> f b@.++Currently only instances are defined are for 2 and 3 tuples, nag me if you want larger ones.++It's worth noting how the instances are defined, for example, for the 2 tuples, there are 3 instances defined.+This is primarily to help type inference. We don't know too much about the types 'hmap' will produce, but we do know,+if we feed 'hmap' a pair, we should get a pair back. Likewise, if the result of 'hmap' is a pair, then the input+should be a pair.++So we provide both instances where the input is a pair, and when the output is a pair. In both of these instances,+we then in the constraints section (which happens after instance selection) ensure the other argument is also a pair.++The \"know both are pairs already\" case just needs to be added as a specific overlapping instance so the compiler+has a most specific match when it already knows both input and output are pairs.+-}++class PolyFunctor t where+  hmap :: forall c. PolyFunctorConstraint c t => Poly c -> t++type instance PolyFunctorConstraint c ((a0,a1) -> (b0,b1)) = (c (a0 -> b0), c (a1 -> b1))++instance (IsTuple 2 a) => PolyFunctor (a -> (b0,b1)) where+  hmap = hmapTuple2++instance (IsTuple 2 b) => PolyFunctor ((a0,a1) -> b) where+  hmap = hmapTuple2++instance {-# OVERLAPPING #-} PolyFunctor ((a0,a1) -> (b0,b1)) where+  hmap = hmapTuple2++hmapTuple2 (Poly f) (x, y) = (f x, f y)++type instance PolyFunctorConstraint c ((a0,a1,a2) -> (b0,b1,b2)) = (c (a0 -> b0), c (a1 -> b1), c (a2 -> b2))++instance (IsTuple 3 a) => PolyFunctor (a -> (b0,b1,b2)) where+  hmap = hmapTuple3++instance (IsTuple 3 b) => PolyFunctor ((a0,a1,a2) -> b) where+  hmap = hmapTuple3++instance {-# OVERLAPPING #-} PolyFunctor ((a0,a1,a2) -> (b0,b1,b2)) where+  hmap = hmapTuple3++hmapTuple3 (Poly f) (x, y, z) = (f x, f y, f z)
+ test/Tests.hs view
@@ -0,0 +1,67 @@+{-# LANGUAGE PolyKinds #-}+{-# LANGUAGE TypeOperators #-}+{-# LANGUAGE TypeApplications #-}+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE ConstraintKinds #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE UndecidableSuperClasses #-}+{-# LANGUAGE FlexibleInstances #-}++module Main where++import Data.Poly+import Data.Poly.Functor+import Data.Poly.Function+import Control.IndexT.Constructor+import Control.IndexT.Function+import Control.IndexT++import Control.ConstraintManip+import Data.List (foldl')++import Test.Hspec (hspec, it, shouldBe)++polyToInteger = Poly @((IsFunc 1) &&& ((Arg 0) `IxConstrainBy` Integral) &&& ((Result 1) `IxIs` Integer)) toInteger+triple = Poly @((IsHomoFunc 1) &&& ((Arg 0) `IxConstrainBy` Num)) (*3)+add = Poly @((IsHomoFunc 2) &&& ((Arg 0) `IxConstrainBy` Num)) (+)+eq = Poly @((IsHomoArgFunc 2) &&& ((Arg 0) `IxConstrainBy` Eq) &&& ((Result 2) `IxIs` Bool)) (==)++type FoldConstraint t = (+  IsFunc 3 t, -- A fold is a function of three args+  IndexT 1 t ~ ResultT 3 t, -- The second (i.e. arg 1) is equal to the result+  IsFunc 2 (IndexT 0 t), -- the first argument (i.e. the fold function) is a function of two args+  (IndexT 0 (IndexT 0 t)) ~ (ResultT 2 (IndexT 0 t)), -- the first argument of the function which is the first argument is the same as it's third+  IndexT 1 t ~ (IndexT 0 (IndexT 0 t)), -- also, the first argument of the function which is the first argument is the same as the second argument of the function+  IsData 1 (IndexT 2 t), -- the third argument is a data type with one variable+  Foldable (GetConstructor1 (IndexT 2 t)), -- the constructor of that third argument is Foldable+  IndexC 1 0 (IndexT 2 t) ~ IndexT 1 (IndexT 0 t) -- the parameter to the constructor of Foldable is the same as the second argument of the fold function+  )++class (FoldConstraint t) => FoldConstraintC t+instance (FoldConstraint t) => FoldConstraintC t+++pfoldl' = Poly @FoldConstraintC foldl'++polyToInteger' = mkPolyFunc1 @Integral @(Equal Integer) toInteger+triple' = mkPolyHomoFunc1 @Num (*3)+add' = mkPolyHomoFunc2 @Num (+)+eq' = mkPolyHomoArgFunc2 @Eq @(Equal Bool) (==)++polyFold :: Poly FoldConstraintC -> (Int, Float, String)+polyFold (Poly foldFunc) =+  (foldFunc (+) 0 [1,2,3], foldFunc (+) 0 [1.5,2.5,3.5], foldFunc (++) "" ["Hello", ", ", "World"])++main = hspec $ do+  it "mkPolyFunc1 test" $ getPoly polyToInteger (10 :: Int) `shouldBe` 10+  it "hmap triple test" $ hmap triple (6 :: Int, 4.5 :: Float) `shouldBe` (18, 13.5)+  it "add test" $ getPoly add' (6 :: Int) 5 `shouldBe` 11+  it "eq test" $ getPoly eq (6 :: Int) 6 `shouldBe` True+  it "mkPolyFunc1' test" $ getPoly polyToInteger' (10 :: Int) `shouldBe` 10+  it "hmap triple' test" $ hmap triple' (6 :: Int, 4.5 :: Float) `shouldBe` (18, 13.5)+  it "add' test" $ getPoly add' (6 :: Int) 5 `shouldBe` 11+  it "eq' test" $ getPoly eq' (6 :: Int) 6 `shouldBe` True+  it "polyFold test" $ polyFold pfoldl' `shouldBe` (6,7.5,"Hello, World")