Functional Programming

• Referential transparency
• Functions as first-class citizens
• Higher-order functions
• Algebraic data types
• Pattern matching
• Recursion
• Types & type inference
• Haskell Specific: Type classes, Functors, Applicatives, Monads
• A Declarative Programming Paradigm.
• Foundation: Church’s Lambda calculus.
• Pure: No (or controlled) mutable state. Expressions are (by default) side effect free.

• Equational reasoning
• Proving correctness of programs

funName :: (TypeBound a) => a -> b        -- type definition
funName x = show x                        -- implementation
complexFun :: (Ord a) => [a] -> [a] -> [a]
complexFun [] _                 = []      -- pattern matching
complexFun _ []                 = []
complexFun (x:xs) (y:ys)        = [x, y]  -- list patterns
complexFun xs ys
                | length xs > 3 = xs      -- guards
                | otherwise     = ys

funName :: (TypeBound a) => a -> b        -- type definition
funName x = show x                        -- implementation
complexFun :: (Ord a) => [a] -> [a] -> [a]
complexFun [] _                 = []      -- pattern matching
complexFun _ []                 = []
complexFun (x:xs) (y:ys)        = [x, y]  -- list patterns
complexFun xs ys
                | length xs > 3 = xs      -- guards
                | otherwise     = ys

abs n
    | n >= 0 = n
    | otherwise = -n

abs n
    | n >= 0 = n
    | otherwise = -n

Patterns consist of variables and data constructors. They are matched in order, so more specific patterns should come first.

not :: Bool -> Bool
not False = True
not True = False
-- ==
not b = case b of
          True -> False
          False -> True

not :: Bool -> Bool
not False = True
not True = False
-- ==
not b = case b of
          True -> False
          False -> True

head :: [a] -> a
head (x : _) = x
tail :: [a] -> [a]
tail (_ : xs) = xs

head :: [a] -> a
head (x : _) = x
tail :: [a] -> [a]
tail (_ : xs) = xs

-- \boundvar -> body
(\x -> x + x) 5

-- \boundvar -> body
(\x -> x + x) 5

sum [1..5]

sum [1..5]

== Function composition

odd x = not (even x)
odd = not . even

odd x = not (even x)
odd = not . even

The term “point-free” does not refer to the “.” character used for function composition (the number of which typically increase), refers to the fact that the definition does not mention the data points on which functions act.

Every definition has a point-free form that can be computed automatically! http://pointfree.io

• Prefix notation is used for function application: max 7 2max 7 2
• If infix notation is desired, one may use so-called operators (e.g. +): 7 + 27 + 2
• Functions can be converted into operators using backticks: 7 `div` 27 `div` 2
• Operators can be converted into functions using brackets: (+) 7 2(+) 7 2

Notes:

• Operator symbols are formed from one or more symbol characters !#$%&*+./<=>?@^|- : (or any Unicode symbol or punctuation).
• An operator symbol starting with : may only be used for data constructors (e.g. : is the constructor for lists).

• A so-called fixity declaration is used to specify the associativity and precedence level (1 (highest) to 9 (lowest) ) of an operator. E.g.:

  • infixl 6 +infixl 6 + specifies (+) to be left associative with level 6
  • infixr 5 :infixr 5 : specifies (:) to be right associative with level 5
  • infix 4 ==infix 4 == specifies (==) to be neither left nor right associative (making parentheses mandatory while nesting), and with level 4
• Any operator lacking a fixity declaration is assumed to be infixl 9infixl 9.
• Function application has a higher precedence than any infix operator.

Always ternary.

abs :: Int -> Int
abs n = if n >= 0 then n else –n

abs :: Int -> Int
abs n = if n >= 0 then n else –n

[x ^ 2 | x <- [1 .. 5]]                 -- [1, 4, 9, 16, 25]
-- guards
[x | x <- [1 .. 12], 12 `mod` x == 0]   -- [2, 3, 4, 6, 12]
-- multiple generators
[(x, y) | x <- [1, 2], y <- [4, 5]]     -- [(1,4),(1,5),(2,4),(2,5)]
-- dependant generators
[(x, y) | x <- [1 .. 2], y <- [x .. 2]] -- [(1,1),(1,2),(2,2)]

[x ^ 2 | x <- [1 .. 5]]                 -- [1, 4, 9, 16, 25]
-- guards
[x | x <- [1 .. 12], 12 `mod` x == 0]   -- [2, 3, 4, 6, 12]
-- multiple generators
[(x, y) | x <- [1, 2], y <- [4, 5]]     -- [(1,4),(1,5),(2,4),(2,5)]
-- dependant generators
[(x, y) | x <- [1 .. 2], y <- [x .. 2]] -- [(1,1),(1,2),(2,2)]

A Type in Haskell is a name for a collection of related values.

In Haskell, a new name for an existing type can be defined using a type declaration.

type String = [Char]

type String = [Char]

Type declarations can also have type parameters

type Pair a = (a, a)
mult :: Pair Int -> Int
mult (m, n) = m * n

type Pair a = (a, a)
mult :: Pair Int -> Int
mult (m, n) = m * n

Type declarations can be nested but cannot be recursive

type Pos = (Int, Int)
type Trans = Pos -> Pos     -- OK
type Tree = (Int, [Tree])   -- NOK

type Pos = (Int, Int)
type Trans = Pos -> Pos     -- OK
type Tree = (Int, [Tree])   -- NOK

We can define new custom data types by declaring new types and functions that return values of these types. These functions (a.k.a. “data constructors” or “constructors”) are special since they cannot have a definition that results in a reduction rule. Thery therefore remain unchanged during execution and can be used to hold information.

data List a = Nil | Cons a (List a)

data List a = Nil | Cons a (List a)

ListList has values of the form of NilNil and ConsCons where is a generic. NilNil and ConsCons can be viewed as functions that construct values of type ListList.

A completely new type can be defined by specifying its values using a data declaration.

data Bool = False | True

data Bool = False | True

• The two values FalseFalse and TrueTrue are called the constructors for the type BoolBool.
• Type and constructor names must always begin with an upper-case letter.
• Data declarations are similar to context free grammars. The former specifies the values of a type, the latter the sentences of a language.

Such data types are often referred to as algebraic datatypes.

• Type variables within types are implicitly universally quantified at the topmost level. For example,
  a -> Maybe aa -> Maybe a actually denotes forall {a}. a -> Maybe aforall {a}. a -> Maybe a. The {}{} brackets around aa denotes that its instantiation can only be done automatically.
• You may ask ghci to explicitly print universal quantifiers as follows:

Prelude> :set -fprint-explicit-forallsPrelude> :t JustJust :: forall {a}. a -> Maybe aPrelude> :set -fprint-explicit-forallsPrelude> :t JustJust :: forall {a}. a -> Maybe a

• You may explicitly specify the universal quantification in polymorphic type signatures using the ExplicitForAllExplicitForAll extension.

Maybe and Pair are called Type Constructors since they construct one type from another. This behaviour is expressed using kinds, which is the type of a “type”. The type system for kinds is very simple:

K ::= * | K -> KK ::= * | K -> K
** Kind of ordinary/proper/concrete/basic types
->-> Kind of “type constructor” or “type operators”

• This is essentially the “simply typed lambda calculus” one level up, with one base type.
• Ordinary/proper/concrete/basic types are nothing more than nullary type constructors/operators. Analogy: A constant is nothing more than a nullary function.
• The word “type” is therefore often used for any type-level expression: ordinary/proper/concrete/basic types, and for type constructors/operators.

Examples: (Only types of kind * can have a value)

(->)(->) is also a type constructor!

The operator (->)(->) is overloaded:

• In the context of a type (e.g. id::a->a ), it denotes the type constructor for function types.
• In the context of a kind (e.g. List::*->* ), it denotes the kind constructor for type constructors.

Convenient syntax when data constructors have multiple parameters:

data Person = Person
  { name :: String
  , age :: Int
  , children :: [Person]
  } deriving (Show)
-- <=>
data Person = Person String Int [Person] -- positional constructor
  deriving (Show)
-- v selector functions v
name :: Person -> String
name (Person n _ _) = n
age :: Person -> Int
age (Person _ a _) = a
children :: Person -> [Person]
children (Person _ _ c) = c

data Person = Person
  { name :: String
  , age :: Int
  , children :: [Person]
  } deriving (Show)
-- <=>
data Person = Person String Int [Person] -- positional constructor
  deriving (Show)
-- v selector functions v
name :: Person -> String
name (Person n _ _) = n
age :: Person -> Int
age (Person _ a _) = a
children :: Person -> [Person]
children (Person _ _ c) = c

Construction:

alice :: Person
alice = Person "Alice" 5 []
bob :: Person
bob = Person {name = "Bob", age = 35, children = [alice]}

alice :: Person
alice = Person "Alice" 5 []
bob :: Person
bob = Person {name = "Bob", age = 35, children = [alice]}

Derived show contains labels and updates can use field labels:

-- >>> alice{age = age alice + 1}
-- Person {name = "Alice", age = 6, children = []}

-- >>> alice{age = age alice + 1}
-- Person {name = "Alice", age = 6, children = []}

= “Many forms”

Haskell uses type classes to achieve ad-hoc polymorphism.

elem :: Eq a => a -> [a] -> Bool -- Eq is a typeclass

elem :: Eq a => a -> [a] -> Bool -- Eq is a typeclass

Type classes are declared using class declarations:

-- Eq = name of the declared type class
class Eq a where               -- a = type parameter
  (==), (/=) :: a -> a -> Bool -- Required to be a member of Eq
  x /= y = not (x == y)        -- Default implementation (optional)

-- Eq = name of the declared type class
class Eq a where               -- a = type parameter
  (==), (/=) :: a -> a -> Bool -- Required to be a member of Eq
  x /= y = not (x == y)        -- Default implementation (optional)

Type classes may be extended:

-- Eq = name of the type class to be extended
class Eq a => Ord a where      -- Ord = name of resulting type class
  (<), (<=), (>=), (>) :: a -> a -> Bool -- Additional requirements

-- Eq = name of the type class to be extended
class Eq a => Ord a where      -- Ord = name of resulting type class
  (<), (<=), (>=), (>) :: a -> a -> Bool -- Additional requirements

• All members of the type class OrdOrd are also members of the type class EqEq.
• Members of OrdOrd therefore also require (==)(==) to be defined.

A type can be declared to be an instance of a type class using an instance declaration:

-- In order for (Maybe m) to be a member of the type class Eq, it is
-- required that the type m belongs to the type class Eq
instance Eq m => Eq (Maybe m) where
  Just x == Just y   = x == y
  Nothing == Nothing = True
  _ == _             = False

-- In order for (Maybe m) to be a member of the type class Eq, it is
-- required that the type m belongs to the type class Eq
instance Eq m => Eq (Maybe m) where
  Just x == Just y   = x == y
  Nothing == Nothing = True
  _ == _             = False

Just like it is possible to have higher- order functions, it is also possible to have higher-kinded types.

As far as the compiler is concerned, the only requirement for a type to be a member of a type class is that it should have a type correct instance declaration. There are of course additional semantic requirements that need to hold. These additional requirements are expressed as type class laws within the documentation of each type class.

Default implementations for some type classes can be generated automatically for data declarations using the deriving keyword:

data Bool = False | True
  deriving (Eq, Ord, Show, Read)

data Bool = False | True
  deriving (Eq, Ord, Show, Read)

In cases where a datatype only has one constructor, a newtype declaration is used.

Functors are types that can be used to wrap and extract values of other types, and allow us to lift unary functions over the wrapped value.

Definition

class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}

class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}

Type Class Laws

The fmapfmap function should not change the structure of the Functor, only its elements.

An instance of Functor has to abide by the following laws:

1. fmapfmap has to preserve identity

   • fmap id == idfmap id == id

2. fmapfmap has to preserve function composition

   • fmap (g . h) == fmap g . fmap hfmap (g . h) == fmap g . fmap h

fmap

-- <$> == fmap
(<$>) :: Functor f => (a -> b) -> f a -> f b

-- <$> == fmap
(<$>) :: Functor f => (a -> b) -> f a -> f b

Examples

(+1) <$> Nothing                            -- Nothing
(+1) <$> Just 1                             -- Just 2

(+1) <$> Nothing                            -- Nothing
(+1) <$> Just 1                             -- Just 2

Instances

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just x) = Just (f x)

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just x) = Just (f x)

What if we want to lift an n-ary function?

Applicative Functors provide a generic function to wrap values (purepure) and generalized function application (<*><*>).

Definition

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  liftA2 :: (a -> b -> c) -> f a -> f b -> f c
  (*>) :: f a -> f b -> f b
  (<*) :: f a -> f b -> f a
  {-# MINIMAL pure, ((<*>) | liftA2) #-}

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  liftA2 :: (a -> b -> c) -> f a -> f b -> f c
  (*>) :: f a -> f b -> f b
  (<*) :: f a -> f b -> f a
  {-# MINIMAL pure, ((<*>) | liftA2) #-}

Type Class Laws

1. Identity: purepure has to preserve identity

   • pure id <*> x == xpure id <*> x == x

2. Homomorphism: purepure has to preserve function application

   • pure (g x) == pure g <*> pure xpure (g x) == pure g <*> pure x

3. Interchange: Order of evaluation must not matter when applying an effectful function to a pure argument

   • x <*> pure y == pure (\f -> f y) <*> xx <*> pure y == pure (\f -> f y) <*> x

4. Composition: <*><*> has to be associative

   • x <*> (y <*> z) == (pure (.) <*> x <*> y) <*> zx <*> (y <*> z) == (pure (.) <*> x <*> y) <*> z

pure

We also need a function pure to lift 0-ary functions (constants):

pure :: a -> f a
f <$> x == (pure f) <*> x

pure :: a -> f a
f <$> x == (pure f) <*> x

Similarities to plain function application

($)   ::   (a -> b) ->   a ->   b
(<*>) :: f (a -> b) -> f a -> f b
(+) $ 11 $ 31                               -- 42
Just (+) <*> Just 11 <*> Just 31            -- Just 42

($)   ::   (a -> b) ->   a ->   b
(<*>) :: f (a -> b) -> f a -> f b
(+) $ 11 $ 31                               -- 42
Just (+) <*> Just 11 <*> Just 31            -- Just 42

Examples

(+) <$> Nothing <*> Just 2                  -- Nothing
(+) <$> Just 1 <*> Just 2                   -- Just 3
(,) <$> [1,2] <*> [6,7]                     -- [(1,6),(1,7),(2,6),(2,7)]
-- intuition: all possible ways of multiplying the two input lists
pure (*) <*> [1,2] <*> [3,4]                -- [3,4,6,8]
-- in the context of lists, pure (*) == [(*)]
[(*),(+)] <*> [1,2] <*> [3,4]               -- [3,4,6,8,4,5,5,6]

(+) <$> Nothing <*> Just 2                  -- Nothing
(+) <$> Just 1 <*> Just 2                   -- Just 3
(,) <$> [1,2] <*> [6,7]                     -- [(1,6),(1,7),(2,6),(2,7)]
-- intuition: all possible ways of multiplying the two input lists
pure (*) <*> [1,2] <*> [3,4]                -- [3,4,6,8]
-- in the context of lists, pure (*) == [(*)]
[(*),(+)] <*> [1,2] <*> [3,4]               -- [3,4,6,8,4,5,5,6]

Instances

instance Applicative Maybe where
  pure x = Just x
  Nothing <*> _ = Nothing
  (Just f) <*> mx = fmap f mx
instance Applicative IO where
  pure = return
  mf <*> mx = do
    f <- mf
    x <- mx
    return (f x)

instance Applicative Maybe where
  pure x = Just x
  Nothing <*> _ = Nothing
  (Just f) <*> mx = fmap f mx
instance Applicative IO where
  pure = return
  mf <*> mx = do
    f <- mf
    x <- mx
    return (f x)

So far, we have seen how functors and applicative functors help us to:

• apply pure functions to “effectful” arguments
• compose function application with multiple “effectful” arguments

What is missing is how to apply and compose “effectful” functions with “effectful” arguments.

Definition

class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  {-# MINIMAL (>>=) #-}

class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  {-# MINIMAL (>>=) #-}

Type Class Laws

1. Left identity

   • return x >>= f = f xreturn x >>= f = f x

2. Right identity

   • mx >>= return == mxmx >>= return == mx

3. Associativity

   • (mx >>= f) >>= g == mx >>= (\x -> (f x >>= g))(mx >>= f) >>= g == mx >>= (\x -> (f x >>= g))

Bind

Function that binds an effectful value into an effectful function

(>>=) :: m a -> (a -> m b) -> m b

(>>=) :: m a -> (a -> m b) -> m b

Kleisi arrow

The Kleisli arrow (<=<<=<) is analogous to normal function composition, except that it works on monadic functions

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

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

Examples

safediv 8 0 >>= flip safediv 2              -- Nothing
safediv 8 2 >>= flip safediv 2              -- Just 2
safediv :: Int -> Int -> Maybe Int
safediv n m = if m == 0 then Nothing else Just $ div n m
do {x <- [1,2]; y <- [3,4]; return (x,y)}   -- [(1,3),(1,4),(2,3),(2,4)]
-- <=>
[1,2] >>= \x -> [3,4] >>= \y -> return (x,y)
-- <=>
[1,2] >>= \x -> [3,4] >>= return . (x,)
-- <=>
[1,2] >>= \x -> (x,) <$> [3,4]
-- <=>
(,) <$> [1,2] <*> [3,4]

safediv 8 0 >>= flip safediv 2              -- Nothing
safediv 8 2 >>= flip safediv 2              -- Just 2
safediv :: Int -> Int -> Maybe Int
safediv n m = if m == 0 then Nothing else Just $ div n m
do {x <- [1,2]; y <- [3,4]; return (x,y)}   -- [(1,3),(1,4),(2,3),(2,4)]
-- <=>
[1,2] >>= \x -> [3,4] >>= \y -> return (x,y)
-- <=>
[1,2] >>= \x -> [3,4] >>= return . (x,)
-- <=>
[1,2] >>= \x -> (x,) <$> [3,4]
-- <=>
(,) <$> [1,2] <*> [3,4]

Instances

instance Monad Maybe where
  Nothing >>= _ = Nothing
  (Just x) >>= f = f x
instance Monad [] where
  xs >>= f = [y | x <- xs, y <- f x]

instance Monad Maybe where
  Nothing >>= _ = Nothing
  (Just x) >>= f = f x
instance Monad [] where
  xs >>= f = [y | x <- xs, y <- f x]

• A collection of related values, types, classes, etc.
• Name: Identifier that starts with a capital letter.
• Naming convention for hierarchy: separated using “.” (e.g. Data.ListData.List, Data.List.NonEmptyData.List.NonEmpty, Data.SetData.Set, …)
• Each module Dir.NameDir.Name must be contained in a file Dir/Name.hsDir/Name.hs.

module BinarySearchTree
( T, toList
) where
data T a = Leaf | Node (T a) a (T a)
  deriving Show
toList :: T a -> [a]
-- ...
import qualified BinarySearchTree
  as Set (T, toList)

module BinarySearchTree
( T, toList
) where
data T a = Leaf | Node (T a) a (T a)
  deriving Show
toList :: T a -> [a]
-- ...
import qualified BinarySearchTree
  as Set (T, toList)

Interactive programs can be written in Haskell by using types to distinguish pure expressions from impure actions that may involve side effects.

IO a -- The type of actions that return a value of type a

IO a -- The type of actions that return a value of type a

One may also use a let statement within a do block to perform a pure computation. Note that the let statement here is different from the let … in … statement for expresisons.

act :: IO (Char, Char)
act = do {x <- getChar;
          y <- getChar;
          let {p = (x,y)};
          return p}
-- <=>
act = do
        x <- getChar
        y <- getChar
        let p = (x,y)
        return p

act :: IO (Char, Char)
act = do {x <- getChar;
          y <- getChar;
          let {p = (x,y)};
          return p}
-- <=>
act = do
        x <- getChar
        y <- getChar
        let p = (x,y)
        return p

Composing IO actions

(>>=) :: Monad m => m a -> (a ->  m b) ->  m b
do {x <- getChar; putChar x}
-- <=>
getChar >>= putChar

(>>=) :: Monad m => m a -> (a ->  m b) ->  m b
do {x <- getChar; putChar x}
-- <=>
getChar >>= putChar

• Creator: Alonzo Church

<M> ::= <id> | λ<id>. <M> | <M> <M> | ( <M> ) <id> ::= a | b | c | ... | 0 | 1 | 2 | ... | + | - | * | ...
<M> ::= <id> | λ<id>. <M> | <M> <M> | ( <M> ) <id> ::= a | b | c | ... | 0 | 1 | 2 | ... | + | - | * | ...


Reserved words: “”, “.”, “(“, “)”

type Id = String
data Term
  = Var Id
  | Abs Id Term
  | App Term Term

type Id = String
data Term
  = Var Id
  | Abs Id Term
  | App Term Term

Rules:

• The scope of a abstraction extends as far right as possible:
• Application is left associative:

“Not Free In”

nfin :: Id -> Term -> Bool
x `nfin` (Var y) = x /= y
x `nfin` (Abs y m) = x == y || nfin x m
x `nfin` (App m n) = x `nfin` m && x `nfin` n

nfin :: Id -> Term -> Bool
x `nfin` (Var y) = x /= y
x `nfin` (Abs y m) = x == y || nfin x m
x `nfin` (App m n) = x `nfin` m && x `nfin` n

The term denotes the term with all free occurrences of the variable replaced by the term .

-- NOTE: renameBoundVars does what it sounds like
type Subst = (Id, Term)
applySubst :: Subst -> Term -> Term
applySubst (x, l) (Var y) = if x == y then l else Var y
applySubst (x, l) (Abs y m)
  | x == y                = Abs y m
  | x /= y && y `nfin` l  = Abs y $ applySubst (x, l) m
  | otherwise
    =
      applySubst (x, l) $ alphaConvert (Abs y m) newId -- newId `nfin` m
applySubst s (App m n)    = App (applySubst s m) (applySubst s n)

-- NOTE: renameBoundVars does what it sounds like
type Subst = (Id, Term)
applySubst :: Subst -> Term -> Term
applySubst (x, l) (Var y) = if x == y then l else Var y
applySubst (x, l) (Abs y m)
  | x == y                = Abs y m
  | x /= y && y `nfin` l  = Abs y $ applySubst (x, l) m
  | otherwise
    =
      applySubst (x, l) $ alphaConvert (Abs y m) newId -- newId `nfin` m
applySubst s (App m n)    = App (applySubst s m) (applySubst s n)

alphaConvert :: Term -> Id -> Term
alphaConvert (Abs x m) y =
  if y `nfin` m
    then Abs y $ applySubst (x, Var y) m
    else Abs x m
alphaConvert x _ = x

alphaConvert :: Term -> Id -> Term
alphaConvert (Abs x m) y =
  if y `nfin` m
    then Abs y $ applySubst (x, Var y) m
    else Abs x m
alphaConvert x _ = x

Replacing formal parameters (placeholders) with actual parameters (values)

betaReduce :: Term -> Maybe Term
betaReduce (App (Abs x m) n) = applySubst (x, n) m
betaReduce = id

betaReduce :: Term -> Maybe Term
betaReduce (App (Abs x m) n) = applySubst (x, n) m
betaReduce = id

Although not strictly necessary, it is very useful to introduce abbreviations for terms to make them more readable. This can be done by introducing definitions as equalities of the following form to a context within which a term can be reduced.

The substitution of a defined symbol with its definition is referred as reduction

For any that does not contain any free occurances of the following equality holds:

(\x -> f x) == f     -- TODO: rewrite in lambda notation
\x -> f (g x) == f . g

(\x -> f x) == f     -- TODO: rewrite in lambda notation
\x -> f (g x) == f . g