Matija    about    posts    reading

A little Haskell cheat sheet - Functor vs Applicative vs Monad

When learning about Haskell (from the really good book “Learn You a Haskell for Great Good” by Miran Lipovača) I came across the four typeclasses from the title - Functor, Applicative and Monad.
They all seem to be very cool and powerful, but after reading through all of them it was a bit hard to wrap my mind around it - what is exactly the difference between them, when should I prefer one over another?

This is why I wrote this small cheat sheet - mostly for myself to better remember and understand it, but if it helps somebody else as well even better!

So let’s dig in:

Functor

Motivation

If we have map for lists and its obvious how useful it is, why wouldn’t we have the same thing for any other type of data structure, like e.g. tree? So, what map is for lists, fmap is for any data structure.

More formally, from Data.Functor Hackage doc page:

Functors: uniform action over a parametrized type, generalizing the map function on lists.

One-line explanation

Functor is for mapping over parametrized types, such as [], Maybe, trees, …

Typeclass definition

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    (<$>) :: (a -> b) -> f a -> f b -- inline version of fmap

Functor typeclass consists of one function only, fmap. fmap works like this:

  • input 1: (a -> b) - function that does the mapping (transformation)
  • input 2: f a - value with a context (“wrapped” value)
  • output: f b - transformed value with the same type of context

<$> is just the infix version of fmap.

When to use it

When we have a value (e.g. Just 10) or data structure (e.g. tree) that provides context along with the data, and we want to transform that data while preserving the type of context.

When not to use it

With functor, we can not change the type of the given context - e.g. after applying a transformation the list will still be a list, Maybe, will still be a Maybe etc.

Examples

Mapping over a function

This is an interesting example since mapping over a function is a bit less intuitive than mapping over “container” types such as Maybe or Either. But, function is nothing else than a (parametrized) type with two parameters, (->) a b, just like Either a b. So when we map over a function, the result will again be a function. And it works in the exactly the same way, with b being affected. In the context of a function it can mean only one thing: the mapping function is applied to the result of the function that is being mapped over, which is a function composition. We can also see in the Prelude source code that is exactly how the function type implements Functor typeclass:

instance Functor ((->) r) where
    fmap = (.)

Let’s take a look at a few specific examples:

  • (+1) <$> (*3) - just as we mentioned, this will simply compose these two functions. So for arg given, it will return (arg * 3) + 1.
  • (+) <$> (*3) - very similar to the previous example, but with a twist that the mapping function takes two arguments, which means it returns a new function when given a single argument. For arg1 and arg2 given, it will return (arg1 * 3) + arg2.

More example ideas

  • Show mapping over a function (e.g. parametrized newtype, like Parser in Real World Haskell).

Sources and additional reading

Applicative

  • Map function in a context to the value in a context
  • Can be chained together
  • We can apply “normal” function to the values with context - “lifting” a function

Motivation

What if we wanted to apply “normal” function to the values with the context? E.g. what if we had two Maybe values and wanted to use (+) on them? Given Just 3 and Just 5 we’d expect to receive Just 8 as a result, while given Just 3 and Nothing we’d expect Nothing.

This is exactly what Applicative type class helps us achieve.

There is probably some more motivation but this is what I have for now.

One-line explanation

All Applicative instances must also be Functor instances. Given that, with Applicative we can apply function in a context to the value in a context.

Typeclass definition

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

We can see that <*> is very similar to <$>, only that given function also has a context. pure is a method that enables us to bring some value in a default context (e.g. a “normal” function we want to use on values with the context).

Examples

    (+) <$> Just 3 <*> Just 5 = Just 8

Here we can see how we “lifted” a function (+) to work with Maybe values. We have to start with <$> first since we are starting with a “normal” function without context, so (+) <$> Just 3 produces Just (3+) (or we could have started with pure (+) <*> Just 3). After that we can just add all the other arguments by chaining them with <*> function.

Monad

Motivation

I am not sure how well did I get the motivation, but here is what I have for now: when dealing with values with a context, monad is the most general tool for it. When we have values with context and they are flowing from one method to another, somebody always has to “handle” the context.

In order to avoid doing it manually (which would increase the complexity a lot, and its a repetitive process), the monads step in - with them, we can “pretend” we are dealing with “normal” functions while they appropriately handle the context for us.

One-line explanation

When dealing with values with context, Monad typeclass helps us by automatically handling the context for us.

Typeclass definition

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b
    (>>) :: m a -> m b -> m b
    fail :: String -> m a
  • return is just like pure in Applicative, putting value in a default, minimal context.
  • (>>=), pronounced “bind”, is the main Monad function. It allows us to “feed” a value with a context into a function that takes a pure value but returns also a value with a context.
  • (>>) is used when we want to “execute” one monad before another, without actually caring for its result (because it probably changes some state, has some side-effect).
  • fail - apparently never used explicitly in code, but by Haskell for some special cases. Did not see it in action so far.

Examples

  • Maybe example -> Show how would handling context look like without monad
  • Parsec example
  • IO example

WIP, ideas

I could write about the situations that drove the inception of the above concepts. E.g.:

  1. First we just had functions that returned a single, simple value.
  2. But soon, we also needed functions that returned multiple different values (e.g. because they can fail)
  3. The values with context were created to address that need.
  4. But then we needed to handle such types of values throughout the code -> we needed new tools to help us with that.
Be the first to comment!

SRM 739 Div II - C++ vs Haskell

SRM 739 was held on October 10th. The original editorial can be found here. Since I was participating and I am also currently learning Haskell, I decided to solve all the problems in Haskell as an exercise and then I found it interesting to compare it with C++ solutions.

HungryCowsEasy - Div 2 Easy

Short problem statement: On a straight line cows and barns are located, and each of them is assigned a position on that line (x coordinate). For each cow determine the barn that is closest to it. Among two equally close barns choose the one with the lower position.

Due to modest input size limits, here it is more than enough to employ a straightforward brute-force solution. For each cow we can examine all the barns and see which one is the closest. If two barns are equally close, one with the lower position is preferred.

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class HungryCowsEasy
{
public:
	vector <int> findFood(vector <int> cowPositions, vector <int> barnPositions)
	{
            vector<int> cowChoice;

            // Process each cow separately.
            for (int cowIdx = 0; cowIdx < cowPositions.size(); cowIdx++) {
                int cowPosition = cowPositions[cowIdx];

                // Find the nearest barn.
                int nearestBarnIdx = 0;
                for (int barnIdx = 0; barnIdx < barnPositions.size(); barnIdx++) {
                    int currBestDist = abs(cowPosition - barnPositions[nearestBarnIdx]);
                    int newDist = abs(cowPosition - barnPositions[barnIdx]);

                    if (newDist < currBestDist) {
                        nearestBarnIdx = barnIdx;
                    } else if (newDist == currBestDist) {
                        if (barnPositions[barnIdx] < barnPositions[nearestBarnIdx]) {
                            nearestBarnIdx = barnIdx;
                        }
                    }
                }
                cowChoice.push_back(nearestBarnIdx);
            }
	    return cowChoice;
	}
};

Haskell

1
2
3
4
5
6
7
8
9
10
11
12

findFood :: [Int] -> [Int] -> [Int]
findFood cowPoss barnPoss = map findBarnForCow cowPoss
    where
        findBarnForCow cowPos = fst $ foldr1 (determineBetterBarn cowPos) $ zip [0..] barnPoss

        determineBetterBarn cowPos barn1 barn2
            | dist1 < dist2 = barn1 
            | dist2 < dist1 = barn2
            | otherwise     = if snd barn1 < snd barn2 then barn1 else barn2
            where 
                dist1 = abs(cowPos - snd barn1)
                dist2 = abs(cowPos - snd barn2)

Comparison

Language Lines 100 runs
C++ 30 TBD
Haskell 12 TBD

Both solutions are short, but I really like how Haskell solution is more readable while being shorter when compared to C++ solution. In Haskell we could very easily create pairs (idx, value) and did not have to explicitly handle them as we did in C++.

ForumPostMedium - Div 2 Medium

Short problem statement: We are given two timestamps in hh:mm:ss format, time when the forum post was published and current time. We have to determine how long ago was a post published and express it through the appropriate string (e.g. “a few seconds ago”, “X minutes ago”, …).

This problem can actually be solved almost entirely analytically - we just transform both timestamps to seconds, get the difference and then transform it from seconds back to the required format (hour,min and sec diff). There is on case to be aware of - if current time is before the publishing time, it means the post was published the day before.

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class ForumPostMedium
{
public:
        int getTimeInSeconds(string time) {

            string delimiter = ":";
            string token;
            int pos = 0;
            vector<int> tokens;
            while ((pos = time.find(delimiter)) != string::npos) {
                token = time.substr(0, pos);
                tokens.push_back(stoi(token));

                time.erase(0, pos + delimiter.length());
            }
            tokens.push_back(stoi(time));

            return tokens[0] * 3600 + tokens[1] * 60 + tokens[2];
        }

	string getShownPostTime(string currentTime, string exactPostTime)
	{
            int currentTimeInSec = getTimeInSeconds(currentTime);
            int postTimeInSec = getTimeInSeconds(exactPostTime);

            int totalSecDiff = currentTimeInSec - postTimeInSec;
            if (postTimeInSec > currentTimeInSec) {
                totalSecDiff = 24 * 3600 - (postTimeInSec - currentTimeInSec);
            }

            // Get hour, min, and sec diff from sec diff.
            int hourDiff = totalSecDiff / 3600;
            int minDiff = (totalSecDiff % 3600) / 60;

            if (hourDiff == 0 && minDiff == 0) {
                return "few seconds ago";
            }
            if (hourDiff == 0) {
                return to_string(minDiff) + " minutes ago";
            }
            return to_string(hourDiff) + " hours ago";
	}
};

Haskell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

getShownPostTime :: String -> String -> String
getShownPostTime currentTime exactPostTime
    | hourDiff == 0 && minDiff == 0 = "few seconds ago"
    | hourDiff == 0                 = show minDiff ++ " minutes ago"
    | otherwise                     = show hourDiff ++ " hours ago"
    where
        -- Convert string timestamp notations to seconds.
        currentTimeInSec = hmsToSec currentTime
        exactPostTimeInSec = hmsToSec exactPostTime

        -- Calculate the difference in seconds between the currentTime and
        -- postTime.
        totalSecDiff
            -- This is the case where post has been published a day before (E.g.
            -- if currentTime is "17:23:34" and postTime is "19:02:19"
            | exactPostTimeInSec > currentTimeInSec = 24 * 3600 - absDiff 
            | otherwise                             = absDiff
            where absDiff = abs(currentTimeInSec - exactPostTimeInSec)

        -- Translate difference in seconds to hour diff and min diff.
        hourDiff = totalSecDiff `div` 3600
        minDiff = (totalSecDiff `mod` 3600) `div` 60

hmsToSec :: String -> Int
hmsToSec hmsStr = h * 3600 + m * 60 + s
    where (h:m:s:_) = map read $ splitByColon hmsStr

splitByColon :: String -> [String]
splitByColon [] = []
splitByColon (':':str) = splitByColon str
splitByColon str = firstToken : (splitByColon rest)
    where (firstToken, rest) = break (==':') str

Comparison

Language Lines 100 runs
C++ 43 TBD
Haskell 32 TBD

Not such a huge difference here! What is interesting is that both solutions are actually very similar, since this problem can be solved in a completely analytical way, we don’t need even one for loop in the C++ solution (except in the helper method to get time in seconds from the original format).
It was actually quite straightforward to write a Haskell solution from the C++ solution.

CheckPolygon - Div 2 Hard

Short problem statement: We are given points respectively describing polygon in a 2D space. The task is to determine whether a polygon is a regular polygon, which means it satisfies certain conditions, such as that two adjacent segments are not collinear and none two segments are intersecting.
If the polygon is regular we should also calculate and return its area.

Input size limits are also not a problem here, so we just need to check if polygon satisfies all the requirements. This task was mostly about geometry - determining whether two segments interesect with each other, checking if point lines on a segment, calculating area of the polygon etc. It was also important to keep all the calculations in integers so we don’t get into precision problems.

Here are some links I found useful in understanding the formulas employed in the solution:

  • Orientation of 3 ordered points - link
  • Area of a polygon (shoelace formula) - link
  • Check if two segments intersect - link
  • Check if three points are collinear - link

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

typedef pair<int, int> Point;
#define x first
#define y second

typedef pair<Point, Point> Segment;

class CheckPolygon
{
public:
        int orientation(Point a, Point b, Point c) {
            long long o = (long long)(b.y - a.y) * (c.x - b.x) - (long long)(c.y - b.y) * (b.x - a.x);

            if (o > 0) return 1;
            if (o < 0) return 2;
            return 0;
        }

        bool areCollinear(Point a, Point b, Point c) {
            // If area of a triangle is 0 -> points are collinear
            return orientation(a, b, c) == 0;
        }

        bool isPointOnSegment(Point point, Segment segment) {
            Point sA = segment.first;
            Point sB = segment.second;

            // Must be collinear and within the bounding rectangle of
            // the segment.
            return orientation(point, sA, sB) == 0
                && (point.x <= max(sA.x, sB.x) && point.x >= min(sA.x, sB.x))
                && (point.y <= max(sA.y, sB.y) && point.y >= min(sA.y, sB.y));
        }

        bool doSegmentsIntersect(Segment a, Segment b) {
            // NOTE(matija): what if segments are colinear?

            return orientation(a.first, a.second, b.first) != orientation(a.first, a.second, b.second) &&
                orientation(b.first, b.second, a.first) != orientation(b.first, b.second, a.second);
        }

        long long getPolygonArea(vector<Segment> segments) {
            long long area = 0;
            for (int i = 0; i < segments.size(); i++) {
                Point sA = segments[i].first;
                Point sB = segments[i].second;

                area += (long long)sA.x * sB.y - (long long)sB.x * sA.y;
            }
            return area;
        }

	string check(vector <int> X, vector <int> Y)
	{
            // Create segments of a polygon.
            vector<pair<Point, Point> > segments;
            for (int pointIdx = 0; pointIdx < X.size(); pointIdx++) {
                Point a = {X[pointIdx], Y[pointIdx]};
                Point b = {X[(pointIdx + 1) % X.size()], Y[(pointIdx + 1) % X.size()]};
                segments.push_back({a, b});
            }

            // Check every segment.
            for (int segmentIdx = 0; segmentIdx < segments.size(); segmentIdx++) {
                // Has positive length?
                // Is non-colinear with the next segment?
                // Does not intersect with other non-neighbouring segments?
                
                Segment s = segments[segmentIdx];
                int nextSegmentIdx = (segmentIdx + 1) % segments.size();
                int prevSegmentIdx = (segmentIdx - 1) < 0 ? segments.size() - 1 : segmentIdx - 1; 

                if (areCollinear(s.first, s.second, segments[nextSegmentIdx].second)) {
                    return "Not simple";
                }

                // Check with all non-neighbour segments.
                for (int i = 0; i < segments.size(); i++) {
                    if (i == segmentIdx || i == nextSegmentIdx || i == prevSegmentIdx) 
                        continue;

                    if (doSegmentsIntersect(s, segments[i])) {
                        return "Not simple";
                    }
                }
            }

            long long area = abs(getPolygonArea(segments));
            stringstream s;
            s << area/2 << '.' << "05"[area % 2];

            return s.str();
	}
};

Haskell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

type Point = (Int, Int)
type Segment = (Point, Point)

orientation :: Point -> Point -> Point -> Int
orientation (ax, ay) (bx, by) (cx, cy)
    | o > 0     = 1
    | o < 0     = 2
    | otherwise = 0
    where o = (by - ay) * (cx - bx) - (cy - by) * (bx - ax)

areCollinear :: Point -> Point -> Point -> Bool
areCollinear a b c = (==0) $ orientation a b c

isPointOnSegment :: Point -> Segment -> Bool
isPointOnSegment point@(px, py) (sPoint1, sPoint2) = 
    -- Point must be collinear with the segment.
    orientation point sPoint1 sPoint2 == 0 &&
    -- Point must be within the bounding box of the segment.
    px <= max sax sbx && px >= min sax sbx &&
    py <= max say sby && py >= min say sby
    where
        (sax, say) = sPoint1
        (sbx, sby) = sPoint2

doSegmentsIntersect :: Segment -> Segment -> Bool
doSegmentsIntersect (a1, a2) (b1, b2) = 
    orientation a1 a2 b1 /= orientation a1 a2 b2 &&
    orientation b1 b2 a1 /= orientation b1 b2 a2

getPolygonArea :: [Segment] -> Int
getPolygonArea = foldr addSegmentToArea 0
    where addSegmentToArea ((p1x, p1y), (p2x, p2y)) area = area + p1x * p2y - p2x * p1y

checkPolygon :: [Int] -> [Int] -> String
checkPolygon xs ys = 
    if all isGood segmentsWithNextAndNonAdj then areaStr else "Not simple"
    where
        isGood (s, next, nnss) = not (areCollinear sPoint1 sPoint2 nextPoint2) 
                                 && all (not . doSegmentsIntersect s) nnss
            where
                (sPoint1, sPoint2) = s
                (_, nextPoint2) = next

        segmentsWithNextAndNonAdj = getNextAndNonAdjacent segments

        segments = getSegmentsFromPoints $ zip xs ys

        areaStr = (show $ areaNum `div` 2) ++ decimalPart
            where 
                areaNum = abs $ getPolygonArea segments
                decimalPart = if areaNum `mod` 2 == 0 then ".0" else ".5"

getSegmentsFromPoints :: [Point] -> [Segment]
getSegmentsFromPoints ps = zipWith (\p1 p2 -> (p1, p2)) ps psCircL1
    where psCircL1 = take (length ps) $ drop 1 $ cycle ps 
        
getNextAndNonAdjacent :: [Segment] -> [(Segment, Segment, [Segment])]
getNextAndNonAdjacent xs = zipWith getNextAndNonAdjacentForOne xsIndexed (repeat xsIndexed)
    where
        xsIndexed = zip [1..] xs

        getNextAndNonAdjacentForOne (idx, x) xsIdx = (x, next, nonAdjElems) 
            where 
                next = snd $ head $ drop idx $ concat $ repeat xsIdx
                nonAdjElems = map snd $ filter (not . areAdjacent (length xsIdx) idx . fst) xsIdx

        areAdjacent listLength idx1 idx2 = idx1 == idx2 || diff == 1 || diff == listLength - 1
            where diff = abs (idx1 - idx2)

Comparison

Language Lines 100 runs
C++ 93 TBD
Haskell 68 TBD

Solutions are here again pretty similar! Problem can be nicely decomposed in a functional way, we need a function for checking each condition, and then we just need to perform checks for every segment of the polygon.

Be the first to comment!

Book: Lucky or Smart? Secrets to an Entreprenurial Life

Book by Bo Peabody, recommended by Mark Solon while in Techstars.

Main takeaways / quotes

Never let great be the enemy of good. A good decision made quickly is far better than a great decision made slowly.

A company that wants to attract luck should be: fundamentally innovative, morally compelling and philosophically positive. This is because:

  • Lots of smart people will gather around these sorts of companies
  • When smart people gather around these types of companies, they work hard
  • When they work hard, serendipity follows
Be the first to comment!