naperian: Efficient representable functors

[ bsd3, data-structures, library ] [ Propose Tags ]

See the readme at https://github.com/aaronvargo/naperian#readme


[Skip to Readme]
Versions 0.1.0.0
Dependencies adjunctions (>=4.2.1), base (>=4.7 && <4.13), comonad (>=4.2.7), distributive (>=0.4.4), free (>=4.11), streams (>=3.2.1), transformers (>=0.3.0) [details]
License BSD-3-Clause
Copyright Aaron Vargo 2017
Author Aaron Vargo
Maintainer Aaron Vargo <fpfundamentalist@gmail.com>
Revised Revision 1 made by AaronVargo at Wed Nov 14 05:53:55 UTC 2018
Category Data Structures
Home page https://github.com/aaronvargo/naperian#readme
Source repo head: git clone https://github.com/aaronvargo/naperian
Uploaded by AaronVargo at Mon Aug 21 22:02:12 UTC 2017
Distributions NixOS:0.1.0.0
Downloads 278 total (12 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2017-08-21 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

For package maintainers and hackage trustees


Readme for naperian-0.1.0.0

[back to package description]

naperian

This package provides Naperian functors, a more powerful form of Distributive functor which is equal in power to a Representable functor (for some Rep), but which can be implemented asymptotically more efficiently for instances which don't support random access.

Distributive functors allow distribution of Functors:

distribute :: (Distributive f, Functor g) => g (f a) -> f (g a)

With Distributive, you can, for example, zip two containers by distributing the Pair Functor:

data Pair a = Pair a a deriving Functor

zipDistributive :: Distributive f => f a -> f a -> f (a, a)
zipDistributive xs ys = fmap f $ distribute (Pair xs ys)
  where f (Pair x y) = (x, y)

Note that the two containers must have elements of the same type. Naperian, however, allows the containers to have elements of different types:

zipNaperian :: Naperian f => f a -> f b -> f (a, b)

It does so by allowing distribution of Functor1s, where a Functor1 is a functor from Hask -> Hask to Hask:

class Functor1 w where
  map1 :: (forall a. f a -> g a) -> w f -> w g

distribute1 :: (Naperian f, Functor1 w) => w f -> f (w Identity)

The more polymorphic zip can then be implemented by distributing the Pair1 Functor1:

data Pair1 a b f = Pair1 (f a) (f b)
instance Functor1 (Pair1 a b) where ...

zipNaperian :: Naperian f => f a -> f b -> f (a, b)
zipNaperian as bs = fmap f $ distribute1 (Pair1 as bs)
  where f (Pair1 (Identity a) (Identity b)) = (a, b)

Naperian functors can be shown to be equivalent to Representable functors, for some Rep, by selecting Rep f = ∀x. f x -> x. That is, a position in a Naperian container can be represented as a function which gets the value at that position. tabulate can then be derived using the Functor1:

newtype TabulateArg a f = TabulateArg ((forall x. f x -> x) -> a)

The rest is left as an exercise for the reader.