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.11), 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>
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 196 total (8 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

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.