conkin: Tools for functors from Hask^k to Hask
Versions [RSS] [faq]  1.0.2 

Change log  ChangeLog.md 
Dependencies  base (>=4.9 && <4.11) [details] 
License  LicenseRefPublicDomain 
Author  Noah Luck Easterly 
Maintainer  noah.easterly@gmail.com 
Category  Control 
Home page  http://github.com/rampion/conkin 
Source repo  head: git clone git://github.com/rampion/conkin.git this: git clone git://github.com/rampion/conkin.git(tag v1.0.2) 
Uploaded  by NoahEasterly at 20171026T19:24:15Z 
Distributions  NixOS:1.0.2 
Downloads  889 total (10 in the last 30 days) 
Rating  (no votes yet) [estimated by Bayesian average] 
Your Rating 

Status  Docs available [build log] Last success reported on 20171026 [all 1 reports] 
Manual Flags
Name  Description  Default 

development  Enable all warnings and upgrade warnings to errors  Disabled 
Automatic Flags
Name  Description  Default 

Use f <flag> to enable a flag, or f <flag> to disable that flag. More info
Downloads
 conkin1.0.2.tar.gz [browse] (Cabal source package)
 Package description (as included in the package)
Readme for conkin1.0.2
[back to package description]One thing I haven't often seen people talk about doing in Haskell is working with data in columnmajor order, or as a struct of arrays. If we take a look though, there's some interesting possibilities and theory underlying this relatively simple concept.
The conkin
library is the result of my explorations along this line of thinking.
An example of use
Suppose we have a list of items we wish to manipulate in columnmajor order:
items :: [Item]
items = [ chocolateBar, toiletPaper, ibuprofen ]
chocolateBar, toiletPaper, ibuprofen :: Item
chocolateBar = Item 0xDE1EC7AB1E "chocolate bar" 1.50
toiletPaper = Item 0xDEFEC8 "toilet paper" 9.99
ibuprofen = Item 0x43A1A11 "ibuprofen" 5.25
Using the Functor
instance for lists, we can easily extract each field into its own list:
extractFields0 :: [Item] > ([UPC], [String], [Double])
extractFields0 items = ( upc <$> items, name <$> items, price <$> items )
{$
>>> extractFields0 items
( [ 0xDE1EC7AB1E , 0xDEFEC8 , 0x43A1A11 ]
, [ "chocolate bar" , "toilet paper" , "ibuprofen" ]
, [ 1.5 , 9.99 , 5.25 ]
)
}
We've lost bit of semantic meaning, however, as we've switched from our own custom data type to a generic tuple. We can regain this meaning if we define a type specifically for a collection of items, parameterized by the item type:
extractFields1 :: [Item] > ItemF []
extractFields1 items = ItemF (upc <$> items) (name <$> items) (price <$> items)
{$
>>> extractFields1 items
ItemF
{ _upc = [ 0xDE1EC7AB1E , 0xDEFEC8 , 0x43A1A11 ]
, _name = [ "chocolate bar" , "toilet paper" , "ibuprofen" ]
, _price = [ 1.5 , 9.99 , 5.25 ]
}
}
data ItemF f = ItemF
{ _upc :: f UPC
, _name :: f String
, _price :: f Dollars
}
deriving instance (Show (f String), Show (f Dollars), Show (f UPC)) => Show (ItemF f)
deriving instance (Eq (f String), Eq (f Dollars), Eq (f UPC)) => Eq (ItemF f)
With a little help from PatternSynonyms
we can derive the Item
type from ItemF
, making sure the two definitions don't slip out of step:
{$
>>> items
[ ItemF
{ _upc = Identity 0xDE1EC7AB1E
, _name = Identity "chocolate bar"
, _price = Identity 1.5
}
, ItemF
{ _upc = Identity 0xDEFEC8
, _name = Identity "toilet paper"
, _price = Identity 9.99
}
, ItemF
{ _upc = Identity 0x43A1A11
, _name = Identity "ibuprofen"
, _price = Identity 5.25
}
]
}
 import Data.Functor.Identity (Identity(..))
 ...
type Item = ItemF Identity
 {# LANGUAGE PatternSynonyms #}
 ...
pattern Item :: UPC > String > Dollars > Item
pattern Item upc name price = ItemF (Identity upc) (Identity name) (Identity price)
upc :: Item > UPC
upc = runIdentity . _upc
name :: Item > String
name = runIdentity . _name
price :: Item > Dollars
price = runIdentity . _price
So what else can we do with ItemF
? We can't make it a Functor
, it's got the wrong kind.
{$
>>> instance Functor ItemF where fmap = undefined
<BLANKLINE>
...
• Expected kind ‘* > *’, but ‘ItemF’ has kind ‘(* > *) > *’
• In the first argument of ‘Functor’, namely ‘ItemF’
In the instance declaration for ‘Functor ItemF’
}
But it's still got this parameter that it's covariant and homogenous in  all the fields must use the same container of kind * > *
, and changing what container we're using should be easy.
So let's define a different Functor
class for types of kind (k > *) > *
.
{$
>>> :i Conkin.Functor
class Conkin.Functor (f :: (k > *) > *) where
Conkin.fmap :: forall (a :: k > *) (b :: k > *).
(forall (x :: k). a x > b x) > f a > f b
...
}
 import qualified Conkin
 ...
instance Conkin.Functor ItemF where
fmap f (ItemF {..}) = ItemF
{ _upc = f _upc
, _name = f _name
, _price = f _price
}
Now we can use Conkin.fmap
to convert an individual Item
into a ItemF []
{$
>>> :t Conkin.fmap (\(Identity x) > [x])
Conkin.fmap (\(Identity x) > [x])
:: Conkin.Functor f => f Identity > f []
>>> Conkin.fmap (\(Identity x) > [x]) chocolateBar
ItemF
{ _upc = [ 0xDE1EC7AB1E ]
, _name = [ "chocolate bar" ]
, _price = [ 1.5 ]
}
}
We could stitch together multiple of these ItemF []
into one if ItemF []
had a Monoid
instance:
extractFields2 :: [Item] > ItemF []
extractFields2 = foldMap $ Conkin.fmap $ pure . runIdentity
{$
>>> extractFields2 items
ItemF
{ _upc = [ 0xDE1EC7AB1E , 0xDEFEC8 , 0x43A1A11 ]
, _name = [ "chocolate bar" , "toilet paper" , "ibuprofen" ]
, _price = [ 1.5 , 9.99 , 5.25 ]
}
}
 import Control.Applicative (Alternative(..))
 ...
instance Alternative a => Monoid (ItemF a) where
mempty = ItemF empty empty empty
left `mappend` right = ItemF
{ _upc = _upc left <> _upc right
, _name = _name left <> _name right
, _price = _price left <> _price right
}
Of course we could do this before with extractFields1
, but there's nothing specific to ItemF
in the definition of extractFields2
. The same definition would work for any Conkin.Functor
that formed a Monoid
:
{$
>>> :t foldMap $ Conkin.fmap $ pure . runIdentity
foldMap $ Conkin.fmap $ pure . runIdentity
:: (Applicative b, Conkin.Functor f, Monoid (f b), Foldable t) =>
t (f Identity) > f b
}
Another useful monoid is ItemF Maybe
. This could let us combine multiple partially specified items into one:
{$
>>> mempty { _price = Just 2.99 }
ItemF { _upc = Nothing , _name = Nothing , _price = Just 2.99 }
>>> mempty { _price = Just 2.99 } <> mempty { _upc = Just 0x0 }
ItemF { _upc = Just 0x0 , _name = Nothing , _price = Just 2.99 }
}
(Side note  I love being able to partially specify ItemF Maybe
using mempty
with record notation. All the succinctness of ItemF { _price = Just 2.99 }
, but none of the missing fields.)
We can use <>
(aka mappend
) to transform a partially specified item into a fully specified one:
withDefaults0 :: ItemF Maybe > Item
withDefaults0 partial = Conkin.fmap (Identity . fromJust) $ partial <> ItemF
{ _upc = Just 0x0
, _name = Just "unknown"
, _price = Just 0
}
{$
>>> withDefaults0 mempty
ItemF
{ _upc = Identity 0x0
, _name = Identity "unknown"
, _price = Identity 0.0
}
>>> withDefaults0 mempty { _price = Just 2.99, _name = Just "flyswatter" }
ItemF
{ _upc = Identity 0x0
, _name = Identity "flyswatter"
, _price = Identity 2.99
}
}
However, I'm not a big fan of this solution. We've abandoned some safety by using the partial fromJust
. If a future developer alters a default to be Nothing
, the compiler won't complain, we'll just get a runtime error.
What I'd rather be using is the safer fromMaybe
, but since that's a twoargument function, I can't just use it via fmap
. I need ItemF
to be an Applicative
.
We'll need a slightly different Applicative
class than Prelude
's, as ItemF
again has the wrong kind:
{$
>>> :i Conkin.Applicative
class Conkin.Functor f =>
Conkin.Applicative (f :: (k > *) > *) where
Conkin.pure :: forall (a :: k > *). (forall (x :: k). a x) > f a
(Conkin.<*>) :: forall (a :: k > *) (b :: k > *).
f (a ~> b) > f a > f b
...
>>> :i (~>)
type role (~>) representational representational nominal
newtype (~>) (a :: k > *) (b :: k > *) (x :: k)
= Conkin.Arrow {(~$~) :: a x > b x}
...
}
instance Conkin.Applicative ItemF where
pure a = ItemF a a a
ItemF fi fs fd <*> ItemF ai as ad
= ItemF (fi ~$~ ai) (fs ~$~ as) (fd ~$~ ad)
Now we can lift fromMaybe
:
withDefaults1 :: ItemF Maybe > Item
withDefaults1 = Conkin.liftA2 (\(Identity x) > Identity . fromMaybe x) ItemF
{ _upc = Identity 0x0
, _name = Identity "unknown"
, _price = Identity 0
}
{$
>>> withDefaults1 mempty
ItemF
{ _upc = Identity 0x0
, _name = Identity "unknown"
, _price = Identity 0.0
}
>>> withDefaults1 mempty { _price = Just 2.99, _name = Just "flyswatter" }
ItemF
{ _upc = Identity 0x0
, _name = Identity "flyswatter"
, _price = Identity 2.99
}
}
Using datadefault
's Default
class, we can generalize this idea to create a function that converts any partiallyspecified Conkin.Applicative
to a fully specified one.
withDefaults2 :: (Conkin.Applicative f, Default (f Identity)) => f Maybe > f Identity
withDefaults2 = Conkin.liftA2 (\(Identity x) > Identity . fromMaybe x) def
instance Default Item where
def = ItemF
{ _upc = Identity 0x0
, _name = Identity "unknown"
, _price = Identity 0
}
{$
>>> withDefaults2 mempty :: ItemF Identity
ItemF
{ _upc = Identity 0x0
, _name = Identity "unknown"
, _price = Identity 0.0
}
>>> withDefaults2 mempty { _price = Just 2.99, _name = Just "flyswatter" }
ItemF
{ _upc = Identity 0x0
, _name = Identity "flyswatter"
, _price = Identity 2.99
}
}
What also might be nice is a way to test whether a ItemF Maybe
is actually fully specified:
isAllJust :: Conkin.Foldable f => f Maybe > Bool
isAllJust = getAll . Conkin.foldMap (All . isJust)
{$
>>> isAllJust mempty { _upc = Just 0x1111111111 }
False
>>> isAllJust ItemF { _upc = Just 0xDEADBEEF, _name = Just "hamburger", _price = Just 1.99 }
True
}
At this point, it should not be surprising that we need a slightly different Foldable
in order to collapse ItemF
values:
{$
>>> :i Conkin.Foldable
class Conkin.Foldable (t :: (k > *) > *) where
Conkin.foldr :: forall (a :: k > *) b.
(forall (x :: k). a x > b > b) > b > t a > b
Conkin.foldMap :: forall m (a :: k > *).
Monoid m =>
(forall (x :: k). a x > m) > t a > m
...
}
instance Conkin.Foldable ItemF where
foldMap f (ItemF {..}) = f _upc <> f _name <> f _price
We could use isAllJust
to safely create an Item
from a fullyspecified ItemF Maybe
:
toItem0 :: ItemF Maybe > Maybe Item
toItem0 i  isAllJust i = Just $ Conkin.fmap (Identity . fromJust) i
 otherwise = Nothing
But the conkin
package already provides a function that does just that:
{$
>>> Conkin.apportion mempty { _upc = Just 0x1111111111 }
Nothing
>>> Conkin.apportion ItemF { _upc = Just 0xDEADBEEF, _name = Just "hamburger", _price = Just 1.99 }
Just
ItemF
{ _upc = Identity 0xDEADBEEF
, _name = Identity "hamburger"
, _price = Identity 1.99
}
>>> :t Conkin.apportion
Conkin.apportion
:: (Conkin.Traversable g, Applicative f) => g f > f (g Identity)
}
Although conkin
does require that ItemF
implement its custom Traversable
class, it provides helpers for tuplelike classes like ItemF
.
{$
>>> :m +Data.Functor.Compose
>>> :i Conkin.Traversable
class (Conkin.Foldable t, Conkin.Functor t) =>
Conkin.Traversable (t :: (i > *) > *) where
Conkin.traverse :: forall j (f :: (j > *) > *) (a :: i
> *) (b :: i > j > *).
Conkin.Applicative f =>
(forall (x :: i). a x > f (b x))
> t a > f (Compose t (Conkin.Flip b))
Conkin.sequenceA :: forall j (f :: (j > *) > *) (a :: i
> j > *).
Conkin.Applicative f =>
t (Compose f a) > f (Compose t (Conkin.Flip a))
...
}
instance Conkin.Traversable ItemF where
sequenceA (ItemF {..}) = Conkin.liftT3 ItemF _upc _name _price
We could also attempt to use apportion
to invert extractFields2
, but it mixes
up the columns:
{$
>>> items
[ ItemF
{ _upc = Identity 0xDE1EC7AB1E
, _name = Identity "chocolate bar"
, _price = Identity 1.5
}
, ItemF
{ _upc = Identity 0xDEFEC8
, _name = Identity "toilet paper"
, _price = Identity 9.99
}
, ItemF
{ _upc = Identity 0x43A1A11
, _name = Identity "ibuprofen"
, _price = Identity 5.25
}
]
>>> Conkin.apportion (extractFields2 items)
[ ItemF
{ _upc = Identity 0xDE1EC7AB1E
, _name = Identity "chocolate bar"
, _price = Identity 1.5
}
, ItemF
{ _upc = Identity 0xDE1EC7AB1E
, _name = Identity "chocolate bar"
, _price = Identity 9.99
}
, ItemF
{ _upc = Identity 0xDE1EC7AB1E
, _name = Identity "chocolate bar"
, _price = Identity 5.25
}
...
, ItemF
{ _upc = Identity 0x43A1A11
, _name = Identity "ibuprofen"
, _price = Identity 1.5
}
, ItemF
{ _upc = Identity 0x43A1A11
, _name = Identity "ibuprofen"
, _price = Identity 9.99
}
, ItemF
{ _upc = Identity 0x43A1A11
, _name = Identity "ibuprofen"
, _price = Identity 5.25
}
]
}
This is because of []
's Applicative
instance. If we use the ZipList
newtype wrapper, we can get the behaviour we desire:
{$
>>> import Control.Applicative (ZipList(..))
>>> Conkin.align (ZipList items)
ItemF
{ _upc =
ZipList { getZipList = [ 0xDE1EC7AB1E , 0xDEFEC8 , 0x43A1A11 ] }
, _name =
ZipList
{ getZipList = [ "chocolate bar" , "toilet paper" , "ibuprofen" ] }
, _price = ZipList { getZipList = [ 1.5 , 9.99 , 5.25 ] }
}
>>> Conkin.apportion (Conkin.align (ZipList items))
ZipList
{ getZipList =
[ ItemF
{ _upc = Identity 0xDE1EC7AB1E
, _name = Identity "chocolate bar"
, _price = Identity 1.5
}
, ItemF
{ _upc = Identity 0xDEFEC8
, _name = Identity "toilet paper"
, _price = Identity 9.99
}
, ItemF
{ _upc = Identity 0x43A1A11
, _name = Identity "ibuprofen"
, _price = Identity 5.25
}
]
}
}
Here we use the handy align
function as yet another way to implement extractFields
:
{$
>>> :t Conkin.align
Conkin.align
:: (Conkin.Applicative g, Traversable f) => f (g Identity) > g f
}
A little bit of theory
Typically in Haskell, we talk about the category Hask, where the objects are types of kind *
and the arrows are normal Haskell functions. In general, a functor is a mapping between categories, mapping each object or arrow in one category to an object or arrow (respectively) in another.
The Prelude
's Functor
typeclass actually describes endofunctors from Hask to Hask; given a Functor f
, we can map any type a
in Hask
to the type f a
in Hask (so f
must have kind * > *
), and we can map any arrow (function) a > b
in Hask to an arrow f a > f b
in Hask (using fmap
).
The conkin
package focuses on the functors from Hask^{k} to Hask. In Hask^{k}, the objects are types of kind k > *
, and the arrows are transformations a ~> b
where (a ~> b) x ~ (a x > b x)
. A functor from Hask^{k} to Hask must then be able to map any type a :: k > *
in Hask^{k} to a type f a :: *
in Hask (so f
must have kind (k > *) > *
), and must be able to map any arrow a ~> b
in Hask^{k} to an arrow f a > f b
in Hask.
(I'm not very well read in category theory, so it's thoroughly possible Hask^{k} has a more common name in literature, I just chose that one out of similarity with type exponentials.)
You can lift any functor from Hask to Hask to a functor from Hask^{k} to Hask using Dispose
:
{$
>>> :i Conkin.Dispose
type role Conkin.Dispose representational nominal nominal
newtype Conkin.Dispose (f :: * > *) (x :: k) (a :: k > *)
= Conkin.Dispose {Conkin.getDispose :: f (a x)}
...
}
And any functor from Hask^{k} to Hask can be lifted to a functor from Hask to Hask using Coyoneda
:
{$
>>> :i Conkin.Coyoneda
type role Conkin.Coyoneda representational representational
data Conkin.Coyoneda (t :: (k > *) > *) u where
Conkin.Coyoneda :: forall k (t :: (k > *) > *) u (a :: k > *).
(forall (x :: k). a x > u) > (t a) > Conkin.Coyoneda t u
...
}
Not only do both of these encodings preserve functorality, but they also preserve foldability, applicativity, and traversability (e.g. Traversable t => Conkin.Traversable (Conkin.Dispose t x)
).
Another interesting facet of functors from Hask^{k} to Hask is the similarity between their kind, (k > *) > *
, and the type of continuations, type Cont r a = (a > r) > r
. This continuation kind is where the conkin
package gets its name from.
If we start to look at these functors as types of kind Cont Type i
, then we can can start thinking of how to compose them
in an algebra, using
Conkin.Product f g :: Cont Type (i,j)
as the product type of functorsf :: Cont Type i
andg :: Cont Type j
Conkin.Coproduct f g :: Cont Type (Either i j)
as the coproduct type of functorsf :: Cont Type i
andg :: Cont Type j
Interestingly, Conkin.Product f g a
is isomorphic to f (Compose g a)
, making Conkin.sequenceA
the equivalent of Data.Tuple.swap
.
Notes and concerns
Existing Work
The conkin
package isn't unprecedented. In addition to Edward Kmett's even more general categories
package, there's also Gracjan Polak's fieldwise
package, which supports a similar set of operations for types of kind (k > *) > *
.
Boilerplate instances
Instances of Conkin
's Functor
, Applicative
, Foldable
, and Traversable
classes are mainly mechanical, and seem like excellent candidates for using XDeriveGeneric
and XDefaultSignatures
to reduce the amount of boilerplate needed for use. This is not currently true, as you cannot encode a type like ItemF
using the fundamental representational types GHC knows about:
{$
>>> deriving instance Generic1 (ItemF)
...
• Can't make a derived instance of ‘Generic1 ItemF’:
Constructor ‘ItemF’ applies a type to an argument involving the last parameter
but the applied type is not of kind * > *, and
Constructor ‘ItemF’ applies a type to an argument involving the last parameter
but the applied type is not of kind * > *, and
Constructor ‘ItemF’ applies a type to an argument involving the last parameter
but the applied type is not of kind * > *
• In the standalone deriving instance for ‘Generic1 (ItemF)’
}
It's very possible to handwrite instances of Generic1
for functors from Hask^{k} to Hask
using an fundamental representational type, Par2
:
newtype Par2 (x :: k) (a :: k > *) = Par2 { unPar2 :: a x }
instance Generic1 ItemF where
type Rep1 ItemF =
D1 ('MetaData "ItemF" "Main" "conkin" 'True)
(C1 ('MetaCons "ItemF" 'PrefixI 'True)
(S1 ('MetaSel ('Just "_upc") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
(Par2 UPC)
:*:
S1 ('MetaSel ('Just "_name") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
(Par2 String)
:*:
S1 ('MetaSel ('Just "_cost") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
(Par2 Dollars)))
from1 (ItemF {..}) = M1 (M1 (M1 (Par2 _upc) :*: M1 (Par2 _name) :*: M1 (Par2 _price)))
to1 (M1 (M1 (M1 (Par2 _upc) :*: M1 (Par2 _name) :*: M1 (Par2 _price)))) = ItemF {..}
However the verbosity of the above makes it less useful as a way to avoid boilerplate.
This is not necessarily the end of all hope; I could make a pull request to GHC including Par2
and updates to the DeriveGeneric
mechanism, or write some TemplateHaskell
macros to generate the instances. Until I do so, I've gone the fairly loweffort route of providing a few helper functions to make Conkin.Traversable
instances easier to write.
Use of unsafeCoerce
In my personal Haskell experience, my only uses of unsafeCoerce
until this package had been for newtype
wrappers and such (i.e. excellent candidates to use coerce
instead). This library marks the first time I found myself using unsafeCoerce
because I just couldn't think of another way to convince the compiler of something, in Dispose
's implementation of Conkin.Traversable
:
instance Prelude.Traversable t => Traversable (Dispose t x) where
sequenceA = teardown . Prelude.traverse setup . getDispose where
setup :: Compose f a x > Coyoneda f (Exists (a x))
setup = Coyoneda Exists . getCompose
teardown :: (Functor f, Prelude.Functor t) => Coyoneda f (t (Exists (a x))) > f (Compose (Dispose t x) (Flip a))
teardown (Coyoneda k fax) = Compose . Dispose . Prelude.fmap Flip . unwrap k <$> fax
 by parametricity, `t`'s implementation of `Prelude.sequenceA :: t (g e) >
 g (t e)` can't inspect the value of `e`, so all `Exists a` values
 must be wrapped `a x` values, so this should be an okay use
 of `unsafeGetExists`.
unwrap :: Prelude.Functor t => (b x > t (Exists a)) > b x > t (a x)
unwrap k bx = Prelude.fmap (unsafeGetExists bx) $ k bx
unsafeGetExists :: proxy x > Exists a > a x
unsafeGetExists _ (Exists az) = unsafeCoerce az
data Exists (a :: k > *) where
Exists :: a x > Exists a
I've managed to convince myself that my use of unsafeCoerce
is, well, safe, but only until someone finds a lawabiding Traversable
that proves me wrong. I should probably come back to this, and either come up with a more formal proof of validity, rather than the loose argument I present in the code.
Literate Haskell
This README.md
file is a literate haskell file, for use with markdownunlit
. To allow GHC to recognize it, it's softlinked as README.lhs
, which you can compile with
$ ghc pgmL markdownunlit README.lhs
Many of the above examples are doctest
compatible, and can be run with
$ doctest pgmL markdownunlit README.lhs
Alternately, you can have cabal manage the dependencies and compile and test this with:
$ cabal install happy
$ cabal install enabletests
$ cabal test readme