Skip to content

Instantly share code, notes, and snippets.

@Icelandjack
Last active March 13, 2019 03:51
Show Gist options
  • Save Icelandjack/6b9745d30cc57900b51269942c3cd504 to your computer and use it in GitHub Desktop.
Save Icelandjack/6b9745d30cc57900b51269942c3cd504 to your computer and use it in GitHub Desktop.
Row Types for Type Classes

Type classes in terms of row types

type Semigroup s = { Monoid s with mappend :: s -> s -> s | _ }

type Pointed f = { Applicative f with pure  :: forall a. a -> f a | _ }
type Apply   f = { Applicative f with (<*>) :: forall a b. f (a -> b) -> f a -> f b | _ }
type Bind    m = { Monad       m with (>>=) :: forall a b. m a -> (a -> m b) -> m b | _ }

https://youtu.be/YTaNkWjd-ac?t=3604 Edward wants to split MonadReader and MonadWriter up into algebraic (ask + tell) and non-algebraic.. Edward describes a painful change he's putting off, this on the other hand is fine

type AlgMonadReader r m = { MonadReader r m with ask :: m r | _ }

type AlgMonadWriter w m = { MonadWriter r m with tell :: w -> m () | _ }

Here is a PureScript ticket created by Kmett (purescript/purescript-transformers#63) that proposes this

More info: http://comonad.com/reader/2011/monads-from-comonads/

Sadly this breaks down a little for Writer and Reader as the mtl unfortunately has historically included a bunch of extra baggage in these classes. In particular, in reader, the notion of local isn't always available, blocking some otherwise perfectly good MonadReader instances, and I've chosen not to repeat this mistake in comonad-transformers.

@Icelandjack
Copy link
Author

Icelandjack commented Sep 22, 2017

I don't know which is the better formulation...

instance (Monoid a) { mappend } => Monoid (Maybe a) where
  mempty = Nothing

  Nothing `mappend` Nothing = Nothing
  Just a  `mappend` Nothing = Just a
  Nothing `mappend` Just b  = Just b
  Just a  `mappend` Just b  = Just (mappend a b)

or

-- (r / a), for all rows (r) which lack a field (a)
Monoid a / mempty => Monoid (Maybe a)

Monoid a / (mempty :: a) => Monoid (Maybe a)

or taking it completely by label (+ type? namespaced? who knows)

{mappend : a -> a -> a} => Monoid (Maybe a)

{mappend} => Monoid (Maybe a)

{mappend @a} => Monoid (Maybe a)

@Icelandjack
Copy link
Author

Icelandjack commented Sep 22, 2017

This would help me make use of Bits default methods

bitDefault :: (Bits a, Num a) => Int -> a 

testBitDefault :: (Bits a, Num a) => a -> Int -> Bool

popCountDefault :: (Bits a, Num a) => a -> Int

whose type could be changed to

bitDefault :: (Bits a with shiftL, Num a) => Int -> a
bitDefault = \i -> 1 `shiftL` i

testBitDefault ::  (Bits a with (bit, (.&.)), Num a) => a -> Int -> Bool
testBitDefault = \x i -> (x .&. bit i) /= 0

popCountDefault :: (Bits a with (.&.), Num a) => a -> Int
popCountDefault = go 0
 where
   go !c 0 = c
   go c w = go (c+1) (w .&. (w - 1))

We can then define a newtype

newtype WrapBits a = WrapBits a 

-- ignoring wrapping
instance (Bits a / bit / testBit / popCount, Num a) => Bits (WrapBits a) where
  bit = bitDefault
  testBit = testBitDefault
  popCount = popCountDefault

  shift = shift
  rotate = rotate
  bitSize = bitSize
  bitSizeMaybe = bitSizeMaybe
  isSigned = isSigned

@Icelandjack
Copy link
Author

I suck at row types, maybe a better approach is

type Semigroup s = forall rest. { mappend :: s -> s -> s | rest }

type Pointed f = forall rest. { Functor f, pure :: forall a. a -> f a | rest }
type Apply   f = forall rest. { Functor f, (<*>) :: forall a b. f (a -> b) -> f a -> f b | rest }
type Bind    m = forall rest. { Applicative m, (>>=) :: forall a b. m a -> (a -> m b) -> m b | rest }

@Icelandjack
Copy link
Author

Icelandjack commented Sep 23, 2017

More basic example, which emulates MINIMAL or something something (methods defined in terms of other methods)

newtype WrapEq  a = WEq  a
newtype WrapNeq a = WNeq a

instance (Eq a / (/=)) => Eq (WrapEq a) where
  WEq a == WEq b = a == b
  WEq a /= WEq b = not (a == b)

instance (Eq a / (==)) => Eq (WrapNeq a) where
  WNeq a == WNeq b = not (a /= b)
  WNeq a /= WNeq b = a /= b

if Eq were defined as

class Eq a where
  (==) :: a -> a -> a 
  (/=) :: a -> a -> a

@Icelandjack
Copy link
Author

Icelandjack commented Sep 23, 2017

type Semigroupoid cat = Category cat / id

type Semigroup a = Monoid a / mempty

instance Semigroupoid cat =>  Semigroup (Join cat a) where
  Join f `mappend` Join g = Join (f . g)

instance Category cat => Monoid (Join cat a) where
  mempty = Join id

@Icelandjack
Copy link
Author

Icelandjack commented Sep 26, 2017

How do we distinguish method-less classes? Thinking with newtypes

class Semigroup s where
  (<>) :: s -> s -> s

class Semigroup m => Monoid m where
  mempty :: m

class Monoid g => Group g where
  invert :: g -> g -> g

class Group g => Abelian g

Not ideal but (are we assuming { Monoid g, inverse :: g -> g -> g } dumps everything from Monoid g into scope? does that defeat the purpose)

newtype Semigroup s = Semigroup { (<>) :: s -> s -> s }
  deriving newtype (Has "(<>)")

newtype Monoid m = Monoid { Semigroup m, mempty :: m }
  deriving newtype (Has "(<>)", Has "mempty")

newtype Group g = Group { Monoid g, inverse :: g -> g -> g }
  deriving newtype (Has "(<>)", Has "mempty", Has "inverse")

newtype Abelian g = Abelian (Group g)
  deriving newtype (Has "(<>)", Has "mempty", Has "inverse")

@Icelandjack
Copy link
Author

Icelandjack commented Sep 27, 2017

newtype Semigroupoid :: (k -> k -> Type) -> Constraint where
  Semigroupoid :: Category cat / id -> Semigroupoid cat
class Semigroupoid cat => Category cat where

@Icelandjack
Copy link
Author

Icelandjack commented Sep 27, 2017

Hans idea

newtype Semigroupoid cat = Semigroupoid { (.) :: forall b c a. cat b c -> cat a b -> cat a c }

newtype Category cat = Category { id :: forall a. cat a a, Semigroupoid cat }

and separately defined superclass relationship

class Semigroupoid cat => Category cat

@Icelandjack
Copy link
Author

id, instance resolution kicks in.. look at things in scope, finds Control.Category.id from Control.Category.Category

id must have type id :: Category cat => cat a a


@Icelandjack
Copy link
Author

http://openaccess.city.ac.uk/1141/1/Constructors.pdf

data FoldL b a = FoldL (a -> b -> a) a

Although FoldL is not a functor, it nevertheless has operations similar to unit and mult. These can be described using a type class similar to Monoidal, but without the Functor superclass:

class Zip z where 
  zunit :: z ()
  zmult :: z a -> z b -> z (a, b)

consider removing super classes

@Icelandjack
Copy link
Author

Type Inference for GADTs and Anti-unification

(==) :: forall a. {(==) : a -> a -> Bool}. a -> a -> Bool

@Icelandjack
Copy link
Author

https://twitter.com/nomeata/status/979823045471866881

I believe this could be solved the same way

@Icelandjack
Copy link
Author

Icelandjack commented Apr 11, 2018

This is an interesting idea, several ways of expressing this: what is the relationship between Arbitrary and EquivArbitrary

class EquivArbitrary a where
  arbitraryFrom :: Gen (Gen a)
  default
   arbitraryFrom :: Arbitrary a => Gen (Gen a)
  arbitraryFrom = pure arbitrary

class EquivArbitrary a => Arbitrary a where
  arbitrary :: Gen a
  arbitrary = join arbitraryFrom
class Arbitrary a where
  {-# Minimal arbitrary | arbitraryFrom #-}
  arbitrary :: Gen a
  arbitrary = join arbitraryFrom

  arbitraryFrom :: Gen (Gen a)
  arbitraryFrom = pure arbitrary

@Icelandjack
Copy link
Author

Icelandjack commented Apr 17, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment