CSE 130 discussion week 6

Box.after.hs

{-# LANGUAGE FlexibleInstances #-}
-- | Fun with typeclasses
module Box where
import Prelude hiding (Functor(..), Applicative(..), Monad(..), Monoid(..), (.))
infixr 6 <>

--------------------------------------------------------------------------------
-- * Parametricity and typeclasses
-- see https://www.schoolofhaskell.com/school/starting-with-haskell/introduction-to-haskell/5-type-classes

-- This is a dummy wrapper around a value
data Box a = Box { unwrap :: a }


-- unwrap :: Box a -> a
b10 :: Box Int
b10 = Box 10

-- Exercise 0
instance (Show a) => Show (Box a) where
  show (Box a) = "Box: " ++ show a

-- Exercise 1
class Boxy f where
  replace :: (a -> b) -> f a -> f b

instance Boxy Box where
  replace f b = Box (f (unwrap b))

-- exercise 2
class Applicative f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

instance Applicative Box where
  pure  x = Box x
  -- (<*>) :: Box (a -> b) -> Box a -> Box b
  f <*> v = Box ((unwrap f) (unwrap v))

-- Exercise 3
class Applicative f => Monad f where
  (>>=) :: f a -> (a -> f b) -> f b

instance Monad Box where
  a >>= aToB = aToB (unwrap a)

instance Applicative [] where
  zap x = [x]
  _ <*> _ = undefined

instance Monad [] where
  --   (>>=) :: [a] -> (a -> [b]) -> [b]
  [] >>= aToBs =  []
  (x:xs) >>= aToBs = aToBs x ++ (xs >>= aToBs)


(.) :: (b -> c) -> (a -> b)  -> (a -> c)
g . f = \x -> g (f x)

-- Exercise 4
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
g <=< f = \x -> (f x) >>= g

-- (f x) :: m b
-- g     :: b -> m c
-- (>>=) :: m a -> (a -> m b) -> m b
-- -----------
-- m b -> m c

--------------------------------------------------------------------------------
-- * ASIDE: How GHC compiles typeclasses
--
-- The compiler runs a transformation pass to remove typeclasses and lower the
-- program into a simpler form, one with ONLY functions and algebraic data types.

{-
---- CODE
-- STEP 1
-- In standard library
-- class Show a where
--   show :: a -> String

data Int = <INT_REPRS>  -- these are machine representations known to compiler
instance Show Int where
  show i = <INT_TO_STRING>

-- code.hs
data Animal = Cat | Dog | Mouse
instance Show Animal where
  show Cat   = "cat"
  show Dog   = "dog"
  show Mouse = "mouse"

-- STEP 2
twoStrs :: Show a => a -> [String]
twoStrs e = [show e, show e]

-- STEP 3
cat2       = twoStrs Cat
fortyTwo2  = twoStrs 42
---- END CODE


-- ** STEP 1: turn class into record type, instances to values of that type
data Show a = ShowC { show :: a -> String }
-- show :: Show a -> (a -> String)

showInt :: Show Int
showInt = ShowC  { show i = <INT_TO_STRING> }

showAnimal :: Show Animal
showAnimal = ShowC {show = show' }
  where
  show' Cat   = "cat"
  show' Dog   = "dog"
  show' Mouse = "mouse"

-- ** STEP 2: change => into ->
twoStrs :: Show a -> a -> [String]
twoStrs s e = [show s e, show s e]

-- ** STEP 3: insert extra arg to function calls
--           / transform calls to partially applied version
cat2       = twoStrs showAnimal Cat
fortyTwo2  = twoStrs showInt 42
-}
--------------------------------------------------------------------------------
-- * MORE MORE MORE MORE MORE MORE

class Comonad w where
  smaller  :: w a -> a
  bigger   :: w a -> w (w a)
  -- Give a default implementation of 'bigger' in terms of 'extend'
  bigger  boxa  = extend id boxa

  extend   :: (w a -> b) -> w a -> w b
  -- If we strengthen the hierarchy with a class defined above,
  -- we can give a default implementation of extend in terms of bigger.
  -- What is the extra class we need? Add it to ____ w => Cofuzzy w
  -- and give the default impl.
  extend   = undefined

(=>=) :: Comonad w => (w a -> b) -> (w b -> c) -> w a -> c
_ =>= _ = undefined

instance Comonad Box where
  smaller   (boxa) = unwrap boxa
  bigger    (boxa) = Box boxa
  extend    boxaTob boxa = Box (boxaTob boxa)


--------------------------------------------------------------------------------
-- * HINT FOR pipe

class Addable a where
  zero :: a
  plus :: a -> a -> a
  -- Satisfying these laws:
  -- 0 + a = a + 0 = a         --- zero is left & right identity of plus
  -- (a + b) + c = a + (b + c) --- plus is associative

-- fancy infix operator
(<>) :: Addable a => a -> a -> a
(<>) = plus

-- What types are Addable?
-- Of course, integers are. Think of two ways to define this
instance Addable Int where
  zero = 1
  plus = (*)  --- 0 * a = a

-- Also strings...
instance Addable String where
  zero = ""
  plus = (++)

-- Strings are just Lists of Chars... what is Addable [a]?
instance Addable [a] where
  zero = []
  plus = (++)

-- What about functions of type a -> a ??
instance Addable ((->) a a) where
  zero = id  -- id = \x -> x
-- (.) :: (b -> c) -> (a -> b)  -> (a -> c)
-- g . f = \x -> g (f x)
  plus = (.)  --- zero . f = f
              --- g . zero = g

class Squishable f where
  -- If we know how to add two 'a's, we can add lists of them
  squish :: Addable a => f a -> a

instance Squishable []  where
  -- Remember that the things in the list are 'Addable'
  -- squish []     = zero
  -- squish (x:xs) = plus x (squish xs)

  -- What does this translate to? Recall that
  -- foldr f b []     = b
  -- foldr f b (x:xs) = f x (foldr f b xs)
  --
  -- UNCOMMENT & FILL IN
  squish = foldr plus zero

{- BONUS: We have just derived a law for foldr

Theorem: universal property of fold

  -- f []         = b
  -- f (x:xs)     = g x (f xs)

====

    f = foldr g b

-}

-- -- TOO MUCH TIME
-- class (Boxy t, Squishable t) => Collectable t where
--   collect :: Warm f => (a -> f b) -> t a -> f (t b)

-- instance Boxy [] where
--   replace _ _  = undefined

-- -- THIS IS HARD!
-- instance Collectable [] where
--   collect _ _ = undefined


--------------------------------------------------------------------------------
-- * FYI...
--
-- Using Hoogle (https://www.haskell.org/hoogle/), find the proper names for all
-- the typeclasses above
--
-- Boxy        =
-- Warm        =
-- Fuzzy       =
-- Cofuzzy     =
-- Addable     =
-- Squishable  =
-- Collectable =
--
-- What is the source of the in-joke with Warm and Fuzzy?
--

Box.blank.hs

{-# LANGUAGE FlexibleInstances #-}
-- | Fun with typeclasses
module Box where
import Prelude hiding (Functor(..), Applicative(..), Monad(..), Monoid(..))
infixr 6 <>

--------------------------------------------------------------------------------
-- * Parametricity and typeclasses
-- see https://www.schoolofhaskell.com/school/starting-with-haskell/introduction-to-haskell/5-type-classes

-- This is a dummy wrapper around a value
data Box a = Box a

b10 = Box 10

-- Exercise 0
instance Show (Box a) where
  show _ = undefined

-- Exercise 1
class Boxy f where
  replace :: (a -> b) -> f a -> f b

instance Boxy Box where
  replace _ _ = undefined

-- Exercise 2
class Boxy f => Warm f where
  zap   :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

instance Warm Box where
  zap   _ = undefined
  _ <*> _ = undefined

-- Exercise 3
class Warm f => Fuzzy f where
  (>>=) :: f a -> (a -> f b) -> f b

instance Fuzzy Box where
  _ >>= _ = undefined

-- Exercise 4
(>=>) :: Fuzzy m => (a -> m b) -> (b -> m c) -> (a -> m c)
_ >=> _ = undefined

--------------------------------------------------------------------------------
-- * ASIDE: How GHC compiles typeclasses
--
-- The compiler runs a transformation pass to remove typeclasses and lower the
-- program into a simpler form, one with ONLY functions and algebraic data types.

{-
---- CODE
-- STEP 1
-- In standard library
data Int = <INT_REPRS>  -- these are machine representations known to compiler
instance Show Int where
  show i = <INT_TO_STRING>

-- code.hs
data Animal = Cat | Dog | Mouse
instance Show Animal where
  show Cat   = "cat"
  show Dog   = "dog"
  show Mouse = "mouse"

-- STEP 2
twoStrs :: Show a => a -> [String]
twoStrs e = [show e, show e]

-- STEP 3
cat2       = twoStrs Cat
fortyTwo2  = twoStrs 42
---- END CODE
-}

-- ** STEP 1: turn class into record type, instances to values of that type
-- ** STEP 2: change => into ->
-- ** STEP 3: insert extra arg to function calls
--           / transform calls to partially applied version

--------------------------------------------------------------------------------
-- * MORE MORE MORE MORE MORE MORE

class Cofuzzy w where
  smaller  :: w a -> a
  bigger   :: w a -> w (w a)
  -- Give a default implementation of 'bigger' in terms of 'extend'
  bigger   = undefined

  extend   :: (w a -> b) -> w a -> w b
  -- If we strengthen the hierarchy with a class defined above,
  -- we can give a default implementation of extend in terms of bigger.
  -- What is the extra class we need? Add it to ____ w => Cofuzzy w
  -- and give the default impl.
  extend   = undefined

(=>=) :: Cofuzzy w => (w a -> b) -> (w b -> c) -> w a -> c
_ =>= _ = undefined

instance Cofuzzy Box where
  smaller   _   = undefined
  bigger    _   = undefined
  extend    _ _ = undefined


--------------------------------------------------------------------------------
-- * HINT FOR pipe

class Addable a where
  zero :: a
  plus :: a -> a -> a
  -- Satisfying these laws:
  -- 0 + a = a + 0 = a         --- zero is left & right identity of plus
  -- (a + b) + c = a + (b + c) --- plus is associative

-- fancy infix operator
(<>) :: Addable a => a -> a -> a
(<>) = plus

-- What types are Addable?
-- Of course, integers are. Think of two ways to define this
instance Addable Int where
  zero = undefined
  plus = undefined

-- Also strings...
instance Addable String where
  zero = undefined
  plus = undefined

-- Strings are just Lists of Chars... what is Addable [a]?
instance Addable [a] where
  zero = undefined
  plus = undefined

-- What about functions of type a -> a ??
instance Addable ((->) a a) where
  zero = undefined
  plus = undefined

class Squishable f where
  -- If we know how to add two 'a's, we can add lists of them
  squish :: Addable a => f a -> a

instance Squishable []  where
  -- Remember that the things in the list are 'Addable'
  squish []     = undefined
  squish (x:xs) = undefined

  -- What does this translate to? Recall that
  -- foldr f b []     = b
  -- foldr f b (x:xs) = f x (foldr f b xs)
  --
  -- UNCOMMENT & FILL IN
  -- squish = foldr undefined undefined

{- BONUS: We have just derived a law for foldr

Theorem: universal property of fold

FILL IN
-}

-- TOO MUCH TIME
class (Boxy t, Squishable t) => Collectable t where
  collect :: Warm f => (a -> f b) -> t a -> f (t b)

instance Boxy [] where
  replace _ _  = undefined

-- THIS IS HARD!
instance Collectable [] where
  collect _ _ = undefined


--------------------------------------------------------------------------------
-- * FYI...
--
-- Using Hoogle (https://www.haskell.org/hoogle/), find the proper names for all
-- the typeclasses above
--
-- Boxy        =
-- Warm        =
-- Fuzzy       =
-- Cofuzzy     =
-- Addable     =
-- Squishable  =
-- Collectable =
--
-- What is the source of the in-joke with Warm and Fuzzy?
--