Haskell : Typeclasses and Functors

How does Haskell deal with abstracting the functor? It uses the typeclass mechanism.

A typeclass defines a family of types that support a common interface.

class Eq a where
  (==) :: a -> b -> Bool

• If you want to tell Haskell that a particular type is Eq, you have to declare it an instance of this class and provide the implementation of (==).

data Point = Pt Float Float
instance Eq Pt where
  (==) :: (Pt x1 y1) -> (Pt x2 y2) = x1 == x2 && y1 == y2

• Notice that, unlike in C++ or Java, you don’t have to specify the Eq class (or interface) when defining Point — you can do it later in client code. Typeclasses are also Haskell’s only mechanism for overloading functions (and operators). We will need that for overloading fmap for different functors.
• There is one complication, though: a functor is not defined as a type but as a mapping of types (a type constructor). We need a typeclass that’s not a family of types, as was the case with Eq, but a family of type constructors. Fortunately a Haskell typeclass works with type constructors as well as with types. So here’s the definition of the Functor class:

  class Functor f where
      fmap :: (a -> b) -> f a -> f b

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

• data List a = Nil | Con a (List a)
  
  instance Functor List where
    fmap _ Nil = Nil
    fmap f (Con a list) = Con (f a) (fmap f list)

   

  Functor Laws (Composition and Identity)

  Reader Functor
  Combination of the type constructor (->) r with the below implementation of fmap is called the reader functor.

• data (->) r a
  
  instance Functor ((->) r) where
    -- fmap :: (a -> b) -> (r -> a) -> (r -> b)
    fmap f g = f . g -- or (.) f g or fmap = (.)

  Functors as Containers
  Haskell’s laziness, a traditional container, like a list, may actually be implemented as a function. Consider, for instance, an infinite list of natural numbers, which can be compactly defined as:

  nats :: [Integer]
  nats = [1..]

  Functor Composition
  A composition of two functors, when acting on objects, is just the composition of their respective object mappings; and similarly when acting on morphisms.

  Bi-Functors
  Since functors are morphisms in Cat (the category of categories), a lot of intuitions about morphisms — and functions in particular — apply to functors as well.

Writer Functor

type Writer a = (a, String)

(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)
m1 >=> m2 = \x -> 
    let (y, s1) = m1 x
        (z, s2) = m2 y
    in (z, s1 ++ s2)

return :: a -> Writer a
return x = (x, "")

fmap f = id >=> (\x -> return (f x))

Monoids w.r.t. Category Theory

Monoid is just a single object category with a set of morphisms (functions) that follow rules of compositions (associativity and identity).

class Monoid m where
    mempty  :: m        -- can be viewed as single object category    
    mappend :: m -> m -> m  -- or m -> (m -> m)

On a general note, commutativity is NOT a property of monoid. That is (a + b) need not be same as that of (b + a)

Example : String as Monoid

instance Monoid String where
    mempty = ""
    mappend = (++)

Monoid as a Single Object Category
The second interpretation of the type signature of mappend as m->(m->m). It tells us that mappend maps an element of a monoid set to a function acting on that set.

Monoid is a semi-group with an identity element. (a semi-group is an algebraic structure consisting of a set together with an associative binary operation. )

Given a monoid (M,*), one can construct a small category with only one object and whose morphisms are the elements of M. The composition of morphisms is given by the monoid operation *.

Hom-Category
If C is a category containing objects A and B then Hom Category(A,B) is the collection of all morphisms from A to B:
Hom(A,B) = {fC | f: A -> B }
where: A = Dom(f) and B = Cod(f)

Set Theory	Category Theory
Set theory tends to look inside a set, at subsets and so on, to give us structure.	Category Theory theory tends to look outside the category, at the arrows, so the structure comes from the way that it interacts with other categories.

Approximate analogs of set theory concepts:

Set Theory	Category Theory
element of a set	terminal object
empty set	final object
injective functions, subobject	monomorphism(monic), if: m: M->X then X is a subobject of M
surjective functions	epimorphism(epic)
inverse function	isomorphism
intersection	pullback
function space	exponential
indexed family (special case of function)	cone (limit)

 

General 4 important properties of a group

Closure :
A set has closure under an operation if performance of that operation on members of the set always produces a member of the same set; in this case we also say that the set is closed under the operation.

Associativity :
A binary operation ∗ on a set S is called associative if it satisfies the associative law: (x ∗ y) ∗ z = x ∗ (y ∗ z) for all x, y, z in S.

Identity element or neutral element
Identity is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them.

Inverse
In abstract algebra, the idea of an inverse element generalizes concepts of a negation (sign reversal) in relation to addition, and a reciprocal in relation to multiplication. The intuition is of an element that can ‘undo’ the effect of combination with another given element.

Category theory is the study of mathematical abstraction in general. It is a set of concepts aiming to provide a common language for disparate parts of mathematics.

Category Theory : Introduction

A category consists of objects and arrows (also known as morphisms or can be called as functions) that go between them.

Composition process of hierarchical decomposition and re-composition is not meant to suite computer programming alone. It also reflects limitations of our human mind. Our brain can only deal with a small number of concepts at a time. One of the most cited papers in psychology, The Magical Number Seven, Plus or Minus Two, postulated that we can only keep 7 ± 2 “chunks” of information in our minds.

Properties of Categories

If a set posses following properties (associativity and identity), it is called as Category.

-- Associativity
h∘(g∘f) = (h∘g)∘f = h∘g∘f

-- Identity
f . id == f
id . f == f

General Notes:

• In Haskell because distinguishing between terminating and non-terminating functions is undecidable — the famous halting problem. That’s why computer scientists came up with a brilliant idea, or a major hack, depending on your point of view, to extend every type by one more special value called the bottom and denoted by _|_, or Unicode ⊥. This “value” corresponds to a non-terminating computation.
• Functions that may return bottom are called partial, as opposed to total functions, which return valid results for every possible argument.

Surjective
In mathematics, a function f from a set X to a set Y is surjective (or onto), or a surjection, if every element y in Y has a corresponding element x in X such that f(x) = y. The function f may map more than one element of X to the same element of Y.

Injective function
In mathematics, an injective function or injection or one-to-one function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function’s codomain is the image of at most one element of its domain.

A function f that is not injective is sometimes called many-to-one. However, the injective terminology is also sometimes used to mean “single-valued”, i.e., each argument is mapped to at most one value.

Injective term one-to-one function must not be confused with one-to-one correspondence (aka bijective function), which uniquely maps all elements in both domain and codomain to each other.

Homomorphism
A homomorphism is a map that preserves selected structure between two algebraic structures, with the structure to be preserved being given by the naming of the homomorphism.

Note that not all structure that an object possesses need be preserved by a homomorphism. For example, one may have a semigroup homomorphism between two monoids, and this will not be a monoid homomorphism if it does not map the identity of the domain to that of the codomain.

Particular definitions of homomorphism include the following:

• A semigroup homomorphism is a map that preserves an associative binary operation.
• A monoid homomorphism is a semigroup homomorphism that maps the identity element to the identity of the codomain.
• A group homomorphism is a homomorphism that preserves the group structure. It may equivalently be defined as a semigroup homomorphism between groups.
• A ring homomorphism is a homomorphism that preserves the ring structure. Whether the multiplicative identity is to be preserved depends upon the definition of ring in use.
• A linear map is a homomorphism that preserves the vector space structure, namely the abelian group structure and scalar multiplication. The scalar type must further be specified to specify the homomorphism, e.g. every R-linear map is a Z-linear map, but not vice versa.
• A module homomorphism is a map that preserves module structures.
• An algebra homomorphism is a homomorphism that preserves the algebra structure.
• A functor is a homomorphism between two categories.

A monomorphism is a generalization of an injective function in category theory.

Functors, Applicatives and Monads : Simple Ideas

Given some type constructor C[_] and two types A and B, we want to apply functions of type C[A]=>C[B] .
Unfortunately we have only functions of types A=>B,  A=>C[B] and C[A=>B] at hand, so we need adequate transformations for them:

a) ( A=>B ) => ( C[A]=>C[B] )
b) ( A=>C[B] ) => ( C[A]=>C[B] )
c) ( C[A=>B] ) => ( C[A]=>C[B] )

All these are transformations of some given functions into the function type we need, and all these transformations even have names.

a) ( A=>B )      => ( C[A]=>C[B] )   | Functor
b) ( A=>C[B] ) => ( C[A]=>C[B] )   | Monad
c) ( C[A=>B] ) => ( C[A]=>C[B] )   | Applicative

Apache Couch DB Introduction (Open Source NoSQL Database)

Our team has zeroed-in to Couch DB as their choice for NoSQL persistence storage.

Below is the gist of session where we gave quick glance of the important Couch DB features that matter the most for Game Integrity team.

Summary of Session

1. Problems with traditional RDBMS Vs. No SQL Promises

• Explicit ORM Mapping
• Schema Upgrades and maintenance
• Downtime for schema upgrade
• PL/SQL portability issue
• Query / Views flexibility (Index Vs Map-Reduce)
• Ease of Use (HTTP / JSON )

 2. Technical Overview

• Append only data, Immutability of data, leveraging Functional Programming platform (Erlang)
• MVCC (Multi Version Concurrency Control) using versioning
• Eventual Consistency, Conflict handling
• Data Replication using master to master strategy

3. Introduction to Map Reduce (Design / Views)

• Map (Data Filtering)
• Reduce (Data Aggregation and Statistics)
• Map-Reduce Sample using java-script

4. Bots Couch DB Usage and its production deployment strategy

• Nature of Bots Data and performance requirements
• Clubbing Jar Deployment along with NoSQL Artefacts
• View Upgrade / Deployment (Index Upgrades)

CouchDBIntroduction