roles (empty) → 0.2.0.0
raw patch · 7 files changed
+377/−0 lines, 7 filesdep +basedep +containersbuild-type:Customsetup-changed
Dependencies added: base, containers
Files
- .vim.custom +21/−0
- CHANGELOG.markdown +9/−0
- LICENSE +12/−0
- README.md +195/−0
- Setup.hs +2/−0
- roles.cabal +32/−0
- src/Data/Roles.hs +106/−0
+ .vim.custom view
@@ -0,0 +1,21 @@+" Add the following to your .vimrc to automatically load this on startup+" if filereadable(".vim.custom")+" so .vim.custom+" endif++function StripTrailingWhitespace()+ let myline=line(".")+ let mycolumn = col(".")+ silent %s/ *$//+ call cursor(myline, mycolumn)+endfunction++syntax on+set tags=TAGS;/+set listchars=tab:‗‗,trail:‗+set list++map <F2> :exec ":!hasktags -x -c --ignore src"<CR><CR>++au BufWritePre *.hs,*.markdown silent! cal StripTrailingWhitespace()+au BufWritePost *.hs silent! :exec ":!hasktags -x -c --ignore src"
+ CHANGELOG.markdown view
@@ -0,0 +1,9 @@+0.2+---+* Drop lens, add containers dependency+* Remove instances that rely on 'new' and 'eta' (for now)+ ++0.1+---+* Repository initialized
+ LICENSE view
@@ -0,0 +1,12 @@+Copyright (C) 2017, Matt Noonan+Copyright (C) 2014, Edward A. Kmett++Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:++1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.++2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.++3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,195 @@+# roles++Composable, class-based roles.++# Table of contents++ * [Motivation: What is the cost of a `newtype`?](#what-is-the-cost)+ * [Background](#background)+ * [The magical `Coercible` class](#magical)+ * [Lifting coercions](#lifting)+ * [Roles to the rescue](#roles)+ * [The `roles` library](#library)+ * [What problem does this library solve?](#what-problem)+ * [How can I use this library?](#how-can-i)+ * [History](#history)++# What is the cost of a `newtype`? <a name="what-is-the-cost"></a>++The conventional wisdom is that Haskell's `newtype` gives you a zero-cost+abstraction--wrapping and unwrapping of `newtype`s are purely a compile-time+operation. Unfortunately, this is not *quite* the case:++```haskell+-- A zero-cost abstraction... or is it?+newtype User = User String++-- 'name x' and 'x' will refer to the same in-memory entity at run-time...+name :: User -> String+name (User x) = x++-- ...but 'maybeName x' and 'x' will not be the same at run-time:+-- a new value of type 'Maybe String' is allocated, despite being+-- identical to the input!+maybeName :: Maybe User -> Maybe String+maybeName = fmap name+```++See the POPL '11 paper [Generative Type Abstraction and Type-level Computation](http://www.seas.upenn.edu/~sweirich/papers/popl163af-weirich.pdf) for a more+through investigation of the problem and a solution, and the ICFP '14 paper [Safe Zero-cost Coercions for Haskell](http://cs.brynmawr.edu/~rae/papers/2014/coercible/coercible-ext.pdf) for+implementation of the `Coercible` typeclass in Haskell. Still more information can be found [on the Haskell wiki](https://ghc.haskell.org/trac/ghc/wiki/Roles).++# Background <a name="background"></a>++## The magical `Coercible` class <a name="magical"></a>++The solution described in the second paper was to introduce a typeclass `Coercible a b` of the+form++```haskell+class Coercible a b where+ coerce :: a -> b+```++There is something a bit magical about a typeclass like this, that requires baked-in+compiler support:+Consider a declaration `newtype New = MkNew Old`. Within the module where `New` is+defined, we should be able to freely `coerce` between `New` and `Old`. But then again,+if `MkNew` is not exported, then *outside* of the module we should *not* be able to+`coerce` between `New` and `Old`. As a result, the `Coercible` class must involve special+compiler magic to ensure that `coerce` is only available in the appropriate modules.++## Lifting coercions <a name="lifting"></a>++Let's revisit the `maybeName` issue. Ideally, we would like to rewrite the example+to make the coercions explicit, to guarantee zero runtime cost:++```haskell+newtype User = User String++name :: User -> String+name = coerce++-- GHC knows that it can coerce 'User' to 'String', but+-- how about 'Maybe User' to 'Maybe String'?+maybeName :: Maybe User -> Maybe String+maybeName = coerce+```++For this to work, we would need instances of `Coercible User String` (provided by+GHC compiler magic, since we're in the module where `User` is defined) and+also `Coercible a b => Coercible (Maybe a) (Maybe b)`.++You might expect GHC could implement a generic "coercion lifting" rule of the form+`Coercible a b => Coercible (f a) (f b)`. Unfortunately this would be unsound+in the presence of type families:++```haskell+newtype User = MkUser String++type family Fam+type instance Fam String = Int+type instance Fam User = Double+```++If GHC naively added the coercion lifting rule, then we would be able to+coerce from `Double` to `Int` by:++```haskell+Coercible User String => Coercible (Fam User) (Fam String) -- a.k.a. Coercible Double Int!+```++This is obviously no good.++## Roles to the rescue <a name="roles"></a>++It seems that sometimes we can lift a `Coercion a b` to a `Coercion (f a) (f b)`+(e.g. for `Maybe`) and sometimes we cannot (e.g. for `Fam`). To figure out when+a coercion `a -> b` can be lifted to a coercion `f a -> f b`, GHC infers a *role*+for the type parameter of `f`. If `f` can safely support coercion-lifting, then+we say `f`'s type parameter has a *representational* role; otherwise, it has a+*nominal* role.++Happily, GHC will infer that `Maybe`'s type parameter is representational, while+`Fam`'s type parameter is nominal. This lets our definition `maybeName = coerce`+pass the compiler, while attempting to coerce an `Int` to a `Double` via+`Fam` will fail.++# The `roles` library <a name="library"></a>++## What problem does this library solve? <a name="what-problem"></a>++Unfortunately, in GHC Haskell there is currently (circa late 2017) no way to+write something like this:++```haskell+coerceFirst :: (Coercible a b, Functor f) => [f a] -> Maybe (f b)+coerceFirst [] = Nothing+coerceFirst (x:_) = Just (coerce x)+{- GHC says:+ • Couldn't match representation of type ‘f a’ with that of ‘f b’+ arising from a use of ‘coerce’+ NB: We cannot know what roles the parameters to ‘f’ have;+ we must assume that the role is nominal+-}+```++GHC rightly refuses to lift the coercion from `a` to `b` into a coercion from+`f a` to `f b`: it does not have any assurance that the functor+`f` uses its type parameter representationally.++In other words, this function needs to have a constraint `Representational f` that+means something like "`f`'s type parameter has a representational+role."++This library simply provides the `Representational` typeclass for a variety of+types in `base` and `containers`.++## How can I use this library? <a name="how-can-i"></a>++Since it is not made up of GHC pixie-dust magic, `Representational` needs a way to+convince GHC that the lifted coercion is allowed.+It does this via the lone function of the `Representational` class:++```haskell+class Representational f where+ rep :: Coercion a b -> Coercion (f a) (f b)+```++A value of type `Coercion a b` is like a certificate that tells GHC "you are allowed+to coerce `a` to `b`". You cash the certificate in by using `coerceWith`, yielding+an actual coercion from `a` to `b`. The `rep` function simply converts a certificate+for coercing `a` to `b` into a certificate for coercing `f a` into `f b`.++We can now fix the example from the previous section:++```haskell+coerceFirst :: (Coercible a b, Representational f, Functor f) => [f a] -> Maybe (f b)+coerceFirst [] = Nothing+coerceFirst (x:_) = Just (coerceWith (rep Coercion) x)+-- ~~~~~~~~~~~~~~~~~~~~~~~~~+-- |+-- This means: (1) Get a certificate verifying that we can coerce `a` to `b`.+-- This certificate is `Coercion`, and we got it by making use+-- of the constraint `Coercible a b`.+-- (2) Since `f` is `Representational`, we can use `rep` to upgrade+-- the certificate to a certificate for coercion from `f a` to `f b`.+-- (3) Use `coerceWith` to hand the certificate over to GHC, obtaining+-- an actual coercion from `f a` to `f b` in return.++{- GHC says: sounds good to me! -}+```++For another usage example, see the `withRecMap` function from `justified-containers`,+and the corresponding test case. A `Representational` constraint is used to ensure+that large maps are not duplicated in memory, despite undergoing a complex series+of `newtype`-related manipulations. An earlier version of `withRecMap` worked by+`fmap`ping newtype wrappers and unwrappers, which caused an accidental duplication+of the map.++## History <a name="history"></a>++This package is a fork of Edward Kmett's original `roles 0.1`. It offers+fewer instances of `Representational`, in exchange for a much smaller set+of dependencies. The instances that involve `new` and `eta` have been+removed, and instances for `containers` have been added.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ roles.cabal view
@@ -0,0 +1,32 @@+name: roles+category: Data+version: 0.2.0.0+license: BSD3+cabal-version: >= 1.8+license-file: LICENSE+author: Edward A. Kmett, Matt Noonan+maintainer: Matt Noonan <matt.noonan@gmail.com>+stability: provisional+homepage: http://github.com/matt-noonan/roles/+bug-reports: http://github.com/matt-noonan/roles/issues+copyright: Copyright (C) 2017 Matt Noonan, (C) 2014 Edward A. Kmett+synopsis: Composable class-based roles+description: Composable class-based roles+build-type: Custom+extra-source-files:+ .vim.custom+ CHANGELOG.markdown+ README.md++source-repository head+ type: git+ location: git://github.com/matt-noonan/roles.git++library+ build-depends: base >= 4.7 && < 5+ , containers++ exposed-modules: Data.Roles++ ghc-options: -Wall -fwarn-tabs -O2+ hs-source-dirs: src
+ src/Data/Roles.hs view
@@ -0,0 +1,106 @@+{-# LANGUAGE PolyKinds #-}+{-# LANGUAGE Rank2Types #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE PackageImports #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE DefaultSignatures #-}+module Data.Roles+ ( Representational(rep)+ , Phantom(phantom)+ ) where++import Control.Applicative+import Control.Monad.ST+import Data.Complex+import Data.Monoid+import Data.Proxy+import Data.Type.Coercion+import Data.Coerce+import Unsafe.Coerce+import Data.Map+import Data.IntMap++class Representational (t :: k1 -> k2) where+ -- | An argument is representational if you can lift a coercion of the argument into one of the whole+ rep :: Coercion a b -> Coercion (t a) (t b)+ default rep :: Phantom t => Coercion a b -> Coercion (t a) (t b)+ rep _ = phantom++class Representational t => Phantom (t :: k1 -> k2) where+ -- | An argument is phantom if you can 'coerce' the whole ignoring the argument+ phantom :: Coercion (t a) (t b)+ default phantom :: Coercible (t a) (t b) => Coercion (t a) (t b)+ phantom = Coercion++-- * Data.Proxy++instance Representational Proxy+instance Phantom Proxy++-- * Const++instance Representational Const where rep Coercion = Coercion+instance Representational (Const a)+instance Phantom (Const a)++-- * Data.Type.Coercion++instance Representational Coercion where rep = unsafeCoerce+instance Representational (Coercion a) where rep Coercion = Coercion++-- * Prelude++instance Representational (->) where rep Coercion = Coercion+instance Representational ((->) a) where rep Coercion = Coercion++instance Representational Either where rep Coercion = Coercion+instance Representational (Either a) where rep Coercion = Coercion++instance Representational (,) where rep Coercion = Coercion+instance Representational ((,) a) where rep Coercion = Coercion++instance Representational (,,) where rep Coercion = Coercion+instance Representational ((,,) a) where rep Coercion = Coercion+instance Representational ((,,) a b) where rep Coercion = Coercion++instance Representational (,,,) where rep Coercion = Coercion+instance Representational ((,,,) a) where rep Coercion = Coercion+instance Representational ((,,,) a b) where rep Coercion = Coercion+instance Representational ((,,,) a b c) where rep Coercion = Coercion++instance Representational (,,,,) where rep Coercion = Coercion+instance Representational ((,,,,) a) where rep Coercion = Coercion+instance Representational ((,,,,) a b) where rep Coercion = Coercion+instance Representational ((,,,,) a b c) where rep Coercion = Coercion+instance Representational ((,,,,) a b c d) where rep Coercion = Coercion++instance Representational (,,,,,) where rep Coercion = Coercion+instance Representational ((,,,,,) a) where rep Coercion = Coercion+instance Representational ((,,,,,) a b) where rep Coercion = Coercion+instance Representational ((,,,,,) a b c) where rep Coercion = Coercion+instance Representational ((,,,,,) a b c d) where rep Coercion = Coercion+instance Representational ((,,,,,) a b c d e) where rep Coercion = Coercion++instance Representational [] where rep Coercion = Coercion+instance Representational Maybe where rep Coercion = Coercion+instance Representational IO where rep Coercion = Coercion+instance Representational (ST s) where rep Coercion = Coercion++-- * containers+instance Representational (Map k) where rep Coercion = Coercion+instance Representational IntMap where rep Coercion = Coercion++-- * Data.Complex++instance Representational Complex where rep Coercion = Coercion++-- * Data.Monoid++instance Representational Sum where rep Coercion = Coercion+instance Representational Product where rep Coercion = Coercion+instance Representational Dual where rep Coercion = Coercion+instance Representational Endo where rep Coercion = Coercion+instance Representational First where rep Coercion = Coercion+instance Representational Last where rep Coercion = Coercion++