Skip to content

course-04.md

Latest commit

 

History

History
533 lines (381 loc) · 9.45 KB

course-04.md

File metadata and controls

533 lines (381 loc) · 9.45 KB

class: center, middle

Functional programming in Haskell

Lesson 4

          TN logo


Clément Hurlin

https://github.com/smelc/tn-fp-haskell-course

Previously

  • How to define generic types: Maybe a, [a]
  • How to define concrete functions: Maybe String -> String -> String

In this course:

Generic functions

Genericity in Haskell is twofold:

  • Polymorphism: functions that work for generic types
  • Classes constraints: require parameters to have some interface

???

  • Ask for functions that work for generic types:

    • List functions: filter, take, etc.
    • Map functions: elem
    • Other containers: fromMaybe, bimap

  • Ask for interfaces in Java:

    • equals, hashCode, clone are interfaces; which are maybe supported, maybe not
    • List, Map

Typeclasses: Eq

⚠️ The Haskell class keyword is unrelated to object-oriented classes 💣 
-- | Types whose values can be compared.
-- Expected to have the following properties:
-- Reflexivity: @x == x@ is @True@
-- Symmetry:    @x == y@ is @y == x@
-- etc.
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  (/=) a b = not (a == b)  -- Default implementation

--

Define:

instance Eq Bool where
  (==) a b = undefined

--

instance Eq a => Eq (Maybe a) where
  (==) _a _b = undefined

instance Eq a => Eq [a] where
  (==) _xs _ys = undefined

???

  • Discuss equals and hashCode in Java
instance Eq a => Eq [a] where -- Build bigger instances from smaller ones
  (==) [] []                         = True
  (==) (a : as) (b : bs) | a == b    = as == bs
  (==) _ _               | otherwise = False

More base typeclasses

data Ordering = LT | EQ | GT

-- | Totally ordered datatypes
class Ord a where
  compare :: a -> a -> Ordering
  (<=) :: a -> a -> Bool
  -- Other operators: <, >, >=, min, max

???

  • Ask for the Java equivalent of compare

--

-- | Types that can be pretty printed
class Show a where
  show :: a -> String

--

-- | Types whose values can be enumerated
class Enum a where
  succ :: a -> a
  pred :: a -> a
  -- Other functions

class Bounded a where
  minBound :: a
  maxBound :: a

???

  • Ask for types that are instances of Enum and Bounded:
    • Int and Bool

Be lazy, rely on the compiler

deriving 
data Version =
    Alpha
  | Beta
    -- | Version number of the form "x.y.z"
  | SemVer Int Int Int
  deriving (Eq, Show)
  • Makes the compiler generate implementation for Eq Version and Show Version 💪
  • Java 15 (2020) has this for record classes
  • Works for a number of classes: Enum, Bounded, Functor, Writer, etc.

???

  • Mention that IDEs do that
  • Ask them what editors they use and why

Typeclasses vs Java interfaces

Typeclasses bear similarities with Java interfaces, but:

  • When a Java class is defined, all its interfaces must be declared.
  • Typeclasses, however, don't have to be defined with the type.
class MonadIO m => MonadLogger m where
  log :: String -> m ()

-- | Generic REST GET interface
class REST a b where
  eval :: (MonadIO m, MonadLogger m) => a -> m b

--

data PR = MkPR {
  owner :: String,
  repo :: String,
  number :: Int
}

-- | Instance checking that a PR CI is green
instance REST PR Bool where
  eval = undefined

Typeclasses vs Java interfaces

In addition, because of dynamic dispatch and subtyping, compare:

class Num a where
  (+) :: a -> a -> a

and

interface Addable<A> {

  public A add(A right); // 'this' is the left operand
  
}

Typeclasses vs Java interfaces

Since there is no subtyping (and no concept of trait object or interface object), we can't build nor work on heterogeneous collections. Compare:

-- | Can sum a list of @a@s when @a@ has the 'Num' capability.
-- But all the items in the list must have the concrete type @a@,
-- and the returned value will have the same type @a@.
sumList :: Num a => [a] -> a
interface Num { ... }
class NInt implements Num { ... }
class NDouble implements Num { ... }
/** 'nums' can contain some items of concrete type NInt,
  * and some items of concrete type NDouble at the same time.
  * The returned value can be either a NInt or NDouble. */
Num sumList(nums: List<Num>) { }

Typeclasses: Semigroup

-- | A semigroup is a type whose values can be reduced or aggregated
-- Instances should satisfy @x <> (y <> z) = (x <> y) <> z@
class Semigroup a where
  (<>) :: a -> a -> a
data BankAction =
    -- | Une dépense
    Spend Int
    -- | Un gain
  | Earn  Int
    -- | Compte cloturé
  | Close

--

instance Semigroup BankAction where
  Spend i <> Spend j = Spend (i + j)
  Spend i <> Earn j  = Spend (i - j)
  Close   <> _       = Close
  _       <> Close   = Close
  Earn i  <> Spend j = Earn (i - j)
  Earn i  <> Earn j  = Earn (i + j)

???

  • Ask the version with Nat in place of Int

--

  • instance Semigroup [a]
  • instance Semigroup a => Semigroup (Maybe a)

Typeclasses: Monoid

class Semigroup a => Monoid a where
  -- | The neutral element
  mempty :: a
  -- | Merging operation
  mappend :: a -> a -> a
  -- | Reduction, has a default implementation
  mconcat :: [a] -> a

???

  • Show the laws on Hoogle
  • Ask for mempty and mappend on lists

--

-- Only >= 0 number of votes makes sense
type Nat = Word16

data Reactions = MkReactions {
    hearts :: Nat,
    thumbsUp :: Nat,
    thumbsDown :: Nat
  }

???

  • Ask to write mempty
  • Ask to write mappend
  • Implement instance Monoid (a, b)
instance (Monoid a, Monoid b) => Monoid (a,b) where
  mempty = (mempty, mempty)
  (a,b) `mappend` (c,d) = (a `mappend` c, b `mappend` d)
  • Ask for another monoid implementation (hits in search of multiple files)

Typeclasses: Functor

class Functor f where
  -- | Apply a function to an element wrapped in something ('f')
  fmap :: (a -> b) -> f a -> f b
> import Data.List.Extra
> :type upper
upper :: String -> String
> applyUpper = fmap upper
> :type applyUpper
applyUpper :: Functor f => f String -> f String

--

> applyUpper (Just "foo")
> applyUpper (Right "foo" :: Either Int String)

--

  • Instances we've seen before:
    • Maybe a
    • [a]

Be lazy, rely on the compiler

From course 2:

data Interval a = MkInterval {
    start :: a,
    end :: a
  }
  deriving Functor
  • Write Functor Interval

Typeclasses for QuickCheck testing

QuickCheck is a library for testing properties of functions.

-- | Random generation and shrinking of values.
class Arbitrary a where
  -- | A generator of 'a'
  arbitrary :: Gen a
  -- | Given an 'a', smaller versions of 'a'
  shrink :: a -> [a]

-- | Generates one of the given values
elements :: [a] -> Gen a

-- | Chooses one of the given generators, with a weighted random distribution.
frequency :: [(Int, Gen a)] -> Gen a

???

  • Show class Testable on Hoogle

newtype

-- | @makeURL "http" "google.fr" "search/advanced"@ returns
-- @"http://www.google.fr/search/advanced"@
makeURL :: String -> String -> String -> String
makeURL = undefined
What's error prone about this function for callers?

--

newtype Protocol = MkProtocol String

newtype Hostname = MkHostname String

newtype Segments = MkSegments [String]

makeURL' :: Protocol -> Hostname -> Segments -> String
makeURL' = undefined

newtype:

  • Cost-free (runtime) disambiguation 💪
  • ⚠️ It's just names! ⚠️

Phantom Types

data User = MkUser { name :: String, avatar :: FilePath, id :: Int }

-- | @authenticate user password@ tries to authenticate @user@ with @password@
authenticate :: User -> String -> Bool
authenticate = undefined
How to model that a user is authenticated to the system?

--

data Guest
data Authenticated

-- @type@ defines aliases (shortcuts)
type UserWithAuthStatus a = User

authenticate' :: User
              -> String
              -> Either String (UserWithAuthStatus Authenticated)
authenticate' = undefined

--

Phantom types:

  • Use type parameters as markers to distinguish data
  • Could you do that in Java?

Recap

Typeclasses:

  • Choose runtime behavior based on static types (/= dynamic dispatching)
  • Leverage the compiler's generation capabilities
  • Build APIs and features bottom up:
    • from small values, to more structured values.

Recommended reading