Review for Osanda Malith’s Browser Freak utility

Automation is a practice and a skill that every IT professional should exercise. In penetration testing and security checks, automation is more than that; it is essential. Boring, tiring, repeated tasks, and tasks with many steps, if not left to the computer, they might not be done at all. Therefore, security professionals need to automate as many aspects of their work as possible.

Osanda Malith’s Browser Freak is an interesting step in this direction. Browser Freak’s mission is to dump the passwords stored in various browsers. This is something very useful to the security administrator and penetration expert, but also an eye opener for the regular user.

Now, NirSoft provides the tools that dump the passwords stored in various browsers and they should be commended for that. What Browser Freak accomplishes is that it automates the downloading, unzipping, and running of these tools. Impressive! This is great thinking: we should automate every aspect of our jobs, not only the core functionality. A professional security expert might not find the downloading automation to be critical to her mission, because she might download the tools once, then use them many times. Thus, she might only find the automated execution of the tools useful. But an “accidental” penetration tester will find the whole package useful, since she might not be bothered doing any of the task, if it is not fully automated, from end to end. But Browser Freak’s holistic approach should also be useful to the seasoned expert, since by running it, the penetration tester is assured that she has the latest version of the tools, since these are downloaded automatically.

Great thinking, Osanda, and great clean code! Osanda Malith’s Browser Freak is just a batch file (named BrowserFreak.bat). This batch file creates and runs VBscript scripts “. The code in these VBscripts accomplishes the tasks at hand in a manner that is clear and easy to follow. Osanda Malith told me that he could have chosen PowerShell, but he opted for the batch file and VBscript approach because he wanted his utility to be able to run not only in new systems, but in legacy ones as well.

Browser Freak is a nice utility that is a joy to run and has a menu that guides you. You can just run it; no familiarity or experience with it is necessary; the menu will help you select what you need to accomplish. Using this utility will save you time. But there is something more important than that: this utility provides you with all the options you need in a centralized interface, helping you perform the corresponding task in a much easier manner. Instead of using notes to remember sites and utilities, then using a browser to download the utilities, using a zipping utility to unzip, and running the utilities afterwards, Browser Freak will do all that for you and delete the downloaded files afterwards, if you choose so from the menu.

I  hope that in the future we will see more end-to-end automation tools like this one.

Posted in Security

MasterMind solver

In July 2003, I wrote a blog post titled “An Excel VBA macro that solves MasterMind”. In that blog post, I presented a program that solved MasterMind. I wrote the program in VBA and it runs inside Excel. It is still in this blog, should you wish to access it. The program behaves as a person that tries to solve MasterMind, meaning that it begins by proposing a permutation. The user has to supply the number of blacks and whites for the proposed permutation, then the program proposes another permutation and so on, until the program finds the correct permutation. It will be easy for me to write that program in C#, should the need arise.

In this blog post, I am going to present another program I just wrote in C#. I call this program “MasterMind solver” and it is made specifically to solve MasterMind puzzles in the form that the puzzles site Brain Teasers provides.

I am a member of the Mathematics community in Google Plus. It is a great community and I find a lot of interesting posts there. Some posts come from the puzzles site “Brain Teasers” I mentioned above and a few of them are about MasterMind. From the Mathematics community in Google Plus I found out about these puzzles and about the puzzles site “Brain Teasers”. Actually, “Brain Teasers” has its own community on Google plus, as well: It is called with the same name as the site: Brain Teasers.

I created a C# Windows form application using Visual Studio 2005, in order to solve the MasterMind puzzles that the puzzles site “Brain Teasers” provides. The application consists of a single exe file called MMsolver.exe. There is no need to install this application. You just copy the exe file to any folder and you are good to go. It is an application with a single form and to run it, the .NET Framework v2.0 or higher is required.

If you visit the following link,  you will be able to get the executable MMsolver.exe, as well as the project/solution with the source code in the form of a zip file named MMsolver.zip.

Get the application MMsolver.exe and the source code MMsolver.zip here.

You only need MMsolver.exe in order to run the application. The zip file is for those who wish to learn how the ‘magic’ happens. Actually, I will provide a screenshot of the single form and the source code here as well.

MMsolver

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace MMsolver
{
   public partial class Form1 : Form
   {
      public Form1()
      {
         InitializeComponent();
      }

      private void Form1_Load(object sender, EventArgs e)
      {
         generateValidPermutations();
      }

      private void btnInsert_Click(object sender, EventArgs e)
      {
         String myPermutation = txtPermutation.Text;
         String myBlacks = txtBlacks.Text;
         String myWhites = txtWhites.Text;

         if (myPermutation.Length != 4)
         {
            MessageBox.Show("Incorrect permutation. Error 1001.");
            txtPermutation.Focus();
            return;
         }

         if (myPermutation.Substring(0, 1) == "1" ||
             myPermutation.Substring(0, 1) == "2" ||
             myPermutation.Substring(0, 1) == "3" ||
             myPermutation.Substring(0, 1) == "4" ||
             myPermutation.Substring(0, 1) == "5" ||
             myPermutation.Substring(0, 1) == "6")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect permutation. Error 1002.");
            txtPermutation.Focus();
            return;
         }

         if (myPermutation.Substring(1, 1) == "1" ||
             myPermutation.Substring(1, 1) == "2" ||
             myPermutation.Substring(1, 1) == "3" ||
             myPermutation.Substring(1, 1) == "4" ||
             myPermutation.Substring(1, 1) == "5" ||
             myPermutation.Substring(1, 1) == "6")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect permutation. Error 1003.");
            txtPermutation.Focus();
            return;
         }

         if (myPermutation.Substring(2, 1) == "1" ||
             myPermutation.Substring(2, 1) == "2" ||
             myPermutation.Substring(2, 1) == "3" ||
             myPermutation.Substring(2, 1) == "4" ||
             myPermutation.Substring(2, 1) == "5" ||
             myPermutation.Substring(2, 1) == "6")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect permutation. Error 1004.");
            txtPermutation.Focus();
            return;
         }

         if (myPermutation.Substring(3, 1) == "1" ||
             myPermutation.Substring(3, 1) == "2" ||
             myPermutation.Substring(3, 1) == "3" ||
             myPermutation.Substring(3, 1) == "4" ||
             myPermutation.Substring(3, 1) == "5" ||
             myPermutation.Substring(3, 1) == "6")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect permutation. Error 1005.");
            txtPermutation.Focus();
            return;
         }

         if (myBlacks.Length != 1)
         {
            MessageBox.Show("Incorrect number of blacks. Error 1006.");
            txtBlacks.Focus();
            return;
         }

         if (myBlacks == "0" || myBlacks == "1" || myBlacks == "2" || myBlacks == "3" || myBlacks == "4")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect number of blacks. Error 1007.");
            txtBlacks.Focus();
            return;
         }

         if (myWhites.Length != 1)
         {
            MessageBox.Show("Incorrect number of whites. Error 1008.");
            txtWhites.Focus();
            return;
         }

         if (myWhites == "0" || myWhites == "1" || myWhites == "2" || myWhites == "3" || myWhites == "4")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect number of whites. Error 1009.");
            txtWhites.Focus();
            return;
         }

         int intMyBlacks = Convert.ToInt32(myBlacks);
         int intMyWhites = Convert.ToInt32(myWhites);

         if (intMyBlacks + intMyWhites > 4)
         {
            MessageBox.Show("The sum of black and white circles must not be more that 4. Error 1010.");
            txtBlacks.Focus();
            return;
         }

         if (intMyBlacks == 3 && intMyWhites == 1)
         {
            MessageBox.Show("You cannot have 3 black cricles and 1 white circle. You may have 4 black circles and 0 white circles. Error 1011.");
            txtBlacks.Focus();
            return;
         }

         lsbEntries.Items.Add(txtPermutation.Text + " " + txtBlacks.Text + " " + txtWhites.Text);

         generateValidPermutations();

         txtPermutation.Text = "";
         txtBlacks.Text = "";
         txtWhites.Text = "";

         txtPermutation.Focus();
      }

      private void btnRemove_Click(object sender, EventArgs e)
      {
         if (lsbEntries.SelectedIndex > -1)
         {
            lsbEntries.Items.RemoveAt(lsbEntries.SelectedIndex);

            generateValidPermutations();
         }

         txtPermutation.Focus();
      }

      private void btnDelete_Click(object sender, EventArgs e)
      {
         if (lsbEntries.Items.Count != 0)
         {
            lsbEntries.Items.Clear();

            generateValidPermutations();
         }

         txtPermutation.Focus();
      }

      private void generateValidPermutations()
      {
         System.Collections.Generic.List<String> myInputList = new System.Collections.Generic.List<String>();
         System.Collections.Generic.List<String> myOutputList = new System.Collections.Generic.List<String>();

         lsbPermutations.Items.Clear();
         lblTotal.Text = "Total number of valid permutations = 0";

         for (int i = 1; i <= 6; i++)
            for (int j = 1; j <= 6; j++)
               for (int k = 1; k <= 6; k++)
                  for (int l = 1; l <= 6; l++)
                     myInputList.Add(i.ToString() + j.ToString() + k.ToString() + l.ToString());

         foreach (String myEntry in lsbEntries.Items)
         {
            foreach (String myPermutation in myInputList)
            {
               int a1 = Convert.ToInt32(myPermutation.Substring(0, 1));
               int a2 = Convert.ToInt32(myPermutation.Substring(1, 1));
               int a3 = Convert.ToInt32(myPermutation.Substring(2, 1));
               int a4 = Convert.ToInt32(myPermutation.Substring(3, 1));

               int myBlacksCount = 0;
               int myWhitesCount = 0;

               int b1 = Convert.ToInt32(myEntry.Substring(0, 1));
               int b2 = Convert.ToInt32(myEntry.Substring(1, 1));
               int b3 = Convert.ToInt32(myEntry.Substring(2, 1));
               int b4 = Convert.ToInt32(myEntry.Substring(3, 1));
               int b5 = Convert.ToInt32(myEntry.Substring(5, 1));
               int b6 = Convert.ToInt32(myEntry.Substring(7, 1));

               if (a1 == b1)
               {
                  myBlacksCount = myBlacksCount + 1;
                  a1 = 0;
                  b1 = 0;
               }

               if (a2 == b2)
               {
                  myBlacksCount = myBlacksCount + 1;
                  a2 = 0;
                  b2 = 0;
               }

               if (a3 == b3)
               {
                  myBlacksCount = myBlacksCount + 1;
                  a3 = 0;
                  b3 = 0;
               }

               if (a4 == b4)
               {
                  myBlacksCount = myBlacksCount + 1;
                  a4 = 0;
                  b4 = 0;
               }

               if (a1 != 0)
               {
                  if (a1 == b2)
                  {
                     myWhitesCount = myWhitesCount + 1;
                     b2 = 0;
                  }
                  else
                  {
                     if (a1 == b3)
                     {
                        myWhitesCount = myWhitesCount + 1;
                        b3 = 0;
                     }
                     else
                     {
                        if (a1 == b4)
                        {
                           myWhitesCount = myWhitesCount + 1;
                           b4 = 0;
                        }
                     }
                  }
               }

               if (a2 != 0)
               {
                  if (a2 == b1)
                  {
                     myWhitesCount = myWhitesCount + 1;
                     b1 = 0;
                  }
                  else
                  {
                     if (a2 == b3)
                     {
                        myWhitesCount = myWhitesCount + 1;
                        b3 = 0;
                     }
                     else
                     {
                        if (a2 == b4)
                        {
                           myWhitesCount = myWhitesCount + 1;
                           b4 = 0;
                        }
                     }
                  }
               }

               if (a3 != 0)
               {
                  if (a3 == b1)
                  {
                     myWhitesCount = myWhitesCount + 1;
                     b1 = 0;
                  }
                  else
                  {
                     if (a3 == b2)
                     {
                        myWhitesCount = myWhitesCount + 1;
                        b2 = 0;
                     }
                     else
                     {
                        if (a3 == b4)
                        {
                           myWhitesCount = myWhitesCount + 1;
                           b4 = 0;
                        }
                     }
                  }
               }

               if (a4 != 0)
               {
                  if (a4 == b1)
                  {
                     myWhitesCount = myWhitesCount + 1;
                     b1 = 0;
                  }
                  else
                  {
                     if (a4 == b2)
                     {
                        myWhitesCount = myWhitesCount + 1;
                        b2 = 0;
                     }
                     else
                     {
                        if (a4 == b3)
                        {
                           myWhitesCount = myWhitesCount + 1;
                           b3 = 0;
                        }
                     }
                  }
               }

               if (myBlacksCount == b5 && myWhitesCount == b6)
               {
                  myOutputList.Add(myPermutation);
               }

            } // end foreach myPermutation

            myInputList.Clear();
            foreach (String myValue in myOutputList)
            {
               myInputList.Add(myValue);
            }
            myOutputList.Clear();

         } // end foreach myEntry

         foreach (String myPermutation in myInputList)
         lsbPermutations.Items.Add(myPermutation);

         lblTotal.Text = "Total number of valid permutations = " + myInputList.Count.ToString();

      } // End of generateValidPermutations procedure
   }
}

The nice thing about MMsolver is that it autoupdates the list with the valid permutations. This way, the user can experience how the number of valid permutations diminishes as she adds entry after entry of restrictions.

I tried to make MMsolver robust. Thus, MMsolver provides rudimentary checks to make sure the entries are valid. But it does not check everything, which may or may not be what the user expects. Let me explain.

The checks that MMsolver performs are the following: It checks that the permutation consists of 4 correct digits (each from 1 to 6). It also checks that the blacks and whites each consist of 1 correct digit (from 0 to 4).  But it also checks that the sum of blacks and whites does not exceed 4. And it also checks that the user does not enter a response of 3 blacks and 1 white, because something like that bears no meaning. So, these checks cover everything that has to do with the permutation alone, with the blacks alone, with the whites alone, and with the blacks and the whites viewed together. These checks do not cover the permutation with the blacks and the whites viewed together.

What this means is that an entry like 1111 1 1 will be accepted. This entry corresponds to a permutation of 1111, number of blacks = 1, and number of whites = 1. If you enter this entry, the number of valid permutations will drop to zero. This is because such an entry is illogical. You cannot have four “colors” that are the same and also have whites greater than zero. If the “colors” (digits) are all the same in a permutation, then only the number of blacks can be nonzero.

And there are other cases of illogical entries as well. For example, the entry 1112 0 3 is invalid. The same goes for the entry 1112 1 3. But MMsolver will accept all these entries as valid.

Not only that, MMsolver will not check to compare between entries. Thus, if the user enters an entry of 1234 1 1 and later enters another entry for 1234 that conflicts with the previous one, MMsolver will accept these two entries as valid, although the number of valid permutations will drop to zero. For example, the entries 1234 1 1 and 1234 1 2, are in conflict. One entry states that for that particular permutation the number of whites is 1 and the other entry states that for that particular permutation the number of whites is 2. Again, MMsolver will not check for this discrepancy.

It would not have been that difficult for MMsolver to check for these and other illogical cases, but it may be nice that it leaves all this experimenting to the user. It is just that the user has to be aware of all those issues.

Closing, I would like to present two examples that show how the program solves the MasterMind puzzles from the puzzles site Brain Teasers. I will present two puzzles from this site, featured at the time I am writing this blog post. The puzzles are their copyright.

We have the following puzzle:

mastermind-1394935204

The solution for this puzzle is:

1394935204

So, we see that this MasterMind puzzle has one valid solution: 3543.

We have the following puzzle:

mastermind-1394503204

The solution for this puzzle is:

1394503204

So, we see that this last MasterMind puzzle has three valid solutions: 4223, 4232, and 4322.

Posted in Development

From SkyDrive to OneDrive

Now that SkyDrive is named OneDrive, you may have to update the HTML pages where you publish the links of everything you share from OneDrive.

There is no need to change anything on your OneDrive and on your shares. The links have been updated by Microsoft to point to OneDrive instead of SkyDrive.

Just go to the HTML pages where you publish the links and for each link change skydrive.live.com to onedrive.live.com.

Posted in Administration

Trees as Monads

We first encountered trees in Haskell in my blog post titled “Trees in Haskell”. In that blog post we studied binary trees. Then we continued our study of binary trees in my blog post titled “Examples of Functors in Haskell”. In that blog post, we saw how binary trees can act not only as type constructors, but also as Functors.

In this blog post, we will study three different types of trees and see how they behave as Functors, Applicatives, and Monads. The first type of tree that we will study is the binary tree. So far, we only elevated the binary tree to a Functor. We are now going to see if and how a binary tree can function as an Applicative and as a Monad. Hint: a binary tree is inappropriate as an Applicative and as a Monad.  Then we are going to study another type of tree that again is inappropriate as an Applicative, but can function as a Monad.  After that, we are going to study yet a third type of tree that is appropriate in all cases.

But who is to say if a type constructor (for trees in this case) is inappropriate or not, as a Functor, Applicative, or Monad? Well, common logic might have something to do with that, but it really is a matter of opinion; it is a subjective matter. Anyway, we are going to discuss what it means for each tree type constructor to be a Functor, Applicative and Monad and the reader can form her own opinion from there. Of course, it is up to the reader to provide her own definition for the Functor, Applicative and Monad instances for any type of tree she wishes to do so, in order to prove her view of how these should be in each case.

First type of tree: good as a Functor, bad as an Applicative, bad as a Monad.

The first type of tree we are going to study is the binary tree, the one we have been studying in previous posts (“Trees in Haskell” and “Examples of Functors in Haskell”). Its definition, i.e. type constructor, is:

data MyTree a = MyEmptyNode
              | MyFilledNode a (MyTree a) (MyTree a)

We can see that the characteristic of a binary tree is that the value (of type a) is held alongside two other trees (of type MyTree a), in each MyFilledNode.

We have seen how this type of tree functions as a Functor, but let us recapitulate: This type of tree behaves nicely as a Functor. Specifically, we program fmap so that the function f of type a -> b is applied to each value of type a throughout the tree. Thus, we apply f to the value of type a and to each of the left and right subtrees all the way down.

Let us now see why everyone (as far as I know) thinks that it is a bad idea to elevate this type of tree to an Applicative or a Monad.

First of all, let us study this type of tree as an Applicative. Elevating this type of tree to an Applicative – what would that entail? When we elevated the list Functor to an Applicative, we programmed <*> so that a list of functions and another list of elements would produce a list with every output of each function applied to each element. Logical and useful. But now, for this type of tree to function as an Applicative, we have to program <*> in a way so that it will utilize two such trees, one with functions and one with values. So what would the output of <*>  look like?

Again, we have a binary tree of functions and a binary tree of values. What should an Applicative instance do? To visualize the situation we are in and the decision we have to make for the implementation of our Applicative, here is an example:

BinaryTreeApplicative

In this example, we have two trees, one with four functions and one with three elements, each one a list. How would we go on applying the functions in the left tree to the functions in the right tree? Remember that the type signature of an Applicative is  (<*>) :: f (a -> b) -> f a -> f b, where f is the Functor/Applicative. Thus, an applicative takes a tree of functions of type a -> b and a tree of elements of type a and produces a tree of elements of type b. Thus, the output of any applicative we can come up, has to be a tree. One tree; not more than one tree. In this case, it has to be one tree of lists, since the output of each of the functions is a new list.

Thus, we cannot devise a solution where we produce a multitude of trees; the Applicative declaration does not allow us to do that with this type of tree that we have. We have to come up with one tree only as the Applicative output. So what will we put into this tree and where? There is no easy answer that everyone can agree on. Whats more, everyone thinks that it is best that binary trees should not be elevated into an Applicative, because there is no real value in doing so. In the program that follows, I provide a rudimentary, unthoughtful, just plain stupid implementation for an Applicative: I only apply the function in the root of the left (functions) tree to the right (elements) tree and discard(!) every other of the left tree’s functions.

Binary trees are also unintuitive as Monads. A Monad is declared as (>>=)  :: m a -> (a -> m b) -> m b, where m is the Monad. In our case, bind (>>=) will take a binary tree as input, as well as a function. This function will take an element of the tree as input and it will produce a binary tree as output. The output of bind has to be of type m b, thus in our case the output of bind is a binary tree. One binary tree; not more than one binary tree.

Perhaps there is no useful and intuitive way to program bind for a binary tree. Indeed, every node that is filled, has an element and two subtrees. If we apply a function of type a -> m b (as the very declaration of Monad demands) to such a node, the function applied to the element will produce a binary tree that we would have nowhere to put. This is because that position can only hold an element (not a tree) and the other two positions are filled with the left and right subtree, that may not be empty (that may not be MyEmptyNode trees) .

In essence, it is difficult, if not impossible, to apply a function a -> m b to a binary tree. In the program that follows, I provide a rudimentary, unthoughtful, just plain stupid implementation for a Monad: I only apply the function to the root element of the input binary tree, and provide this as the output, discarding(!) the left and right subtrees of the input tree altogether.

module Main where

import Control.Applicative

data MyTree a = MyEmptyNode
              | MyFilledNode a (MyTree a) (MyTree a)
              deriving (Show)

instance Functor MyTree where
   fmap f MyEmptyNode          = MyEmptyNode
   fmap f (MyFilledNode x y z) = MyFilledNode (f x) (fmap f y) (fmap f z)

instance Applicative MyTree where
   pure x = MyFilledNode x MyEmptyNode MyEmptyNode
   (MyFilledNode f fy fz) <*> (MyFilledNode x y z) = MyFilledNode (f x) MyEmptyNode MyEmptyNode
   _ <*> _ = MyEmptyNode

instance Monad MyTree where
   return x = MyFilledNode x MyEmptyNode MyEmptyNode
   (MyFilledNode x y z) >>= f = f x
   MyEmptyNode >>= _ = MyEmptyNode

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that MyTree behaves as a type constructor."

      let tree1 = MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
      print tree1

      let tree2 = MyFilledNode "ABC" (MyFilledNode "AB" MyEmptyNode MyEmptyNode) (MyFilledNode "ABCDEF" MyEmptyNode MyEmptyNode)
      print tree2

      putStrLn "Tests that prove that MyTree behaves as a Functor."

      print (fmap (*2) tree1)
      print (fmap length tree2)

      putStrLn "Tests that prove that MyTree behaves as an Applicative."

      print ((MyFilledNode (*2) MyEmptyNode MyEmptyNode) <*> tree1)
      print ((MyFilledNode init MyEmptyNode MyEmptyNode) <*> tree2)

      putStrLn "Tests that prove that MyTree behaves as a Monad."

      print (tree1 >>= (\x -> MyFilledNode (x+200) MyEmptyNode MyEmptyNode))
      print (tree2 >>= (\x -> MyFilledNode (tail x) MyEmptyNode MyEmptyNode))

      putStrLn "Program ends."

The output of the previous program follows:

Program begins.
Tests that prove that MyTree behaves as a type constructor.
MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
MyFilledNode "ABC" (MyFilledNode "AB" MyEmptyNode MyEmptyNode) (MyFilledNode "ABCDEF" MyEmptyNode MyEmptyNode)
Tests that prove that MyTree behaves as a Functor.
MyFilledNode 10 (MyFilledNode 6 MyEmptyNode MyEmptyNode) (MyFilledNode 4 MyEmptyNode MyEmptyNode)
MyFilledNode 3 (MyFilledNode 2 MyEmptyNode MyEmptyNode) (MyFilledNode 6 MyEmptyNode MyEmptyNode)
Tests that prove that MyTree behaves as an Applicative.
MyFilledNode 10 MyEmptyNode MyEmptyNode
MyFilledNode "AB" MyEmptyNode MyEmptyNode
Tests that prove that MyTree behaves as a Monad.
MyFilledNode 205 MyEmptyNode MyEmptyNode
MyFilledNode "BC" MyEmptyNode MyEmptyNode
Program ends.

 

Second type of tree: good as a Functor, bad as an Applicative, good as a Monad.

There is a type of tree that is easy to understand as a structure and that solves the problem that we had with the binary tree (mis)behaving as Monad. This tree holds an element at each leaf, whereas each node has no elements; it only has a left subtree and a right subtree.

data MyTree a = MyLeaf a
              | MyNode (MyTree a) (MyTree a)

The structure of this type of tree is exactly what makes it easy and intuitive to implement it as a Monad. But before we discuss that, let us see how it should behave as a Functor and as an Applicative.

This type of tree provides an intuitive Functor: just as in the case of the binary tree, we apply the function we are given to each leaf element and also to each subtree all the way down.

This type of tree has the same problems functioning as an Applicative that we encountered in our study of the binary tree. The only case where both the binary tree and this type of tree perhaps could function relatively adequately is when the functions tree and the elements tree have exactly the same structure and depths. But when we have an arbitrary functions tree and an arbitrary elements tree, as it may well be the case, we have no intuitive way to create an adequate Applicative. In the program that follows, I provide a rudimentary, unthoughtful, just plain stupid implementation for an Applicative: I only consider a functions tree with only one function(!) and I apply this function to the elements tree.

The great thing about this type of tree is that we can provide a very useful implementation of it as a Monad. Indeed, as you will see in the following program, we apply the function a -> m b to each leaf and also bind it to both subtrees in each node. Indeed, because each element is tuck away in a leaf, we are left with subtrees only in the nodes, a situation that allows us to apply the function a -> b to leaf elements  as well as subtrees.

The problem we had with binary trees was that the element coexisted with the subtrees in each node. Thus, a function a -> m b that essentially returned a tree, had no space in the binary tree structure to place three trees where an element and two trees should be. By separating the element and the subtrees in this type of tree, we can elevate it into an intuitive and useful Monad.

module Main where

import Control.Applicative

data MyTree a = MyLeaf a
              | MyNode (MyTree a) (MyTree a)
              deriving (Show)

instance Functor MyTree where
   fmap f (MyLeaf x) = MyLeaf (f x)
   fmap f (MyNode x y) = MyNode (fmap f x) (fmap f y)

instance Applicative MyTree where
   pure = MyLeaf
   (MyLeaf f) <*> (MyLeaf x) = MyLeaf (f x)
   (MyLeaf f) <*> (MyNode x y) = MyNode (fmap f x) (fmap f y)

instance Monad MyTree where
   return = MyLeaf
   (MyLeaf x) >>= f = f x
   (MyNode x y) >>= f = MyNode (x >>= f) (y >>= f)

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that MyTree behaves as a type constructor."

      let tree1 = MyNode (MyLeaf 3) (MyNode (MyLeaf 4) (MyLeaf 5))
      print tree1

      let tree2 = MyNode (MyLeaf "ABC") (MyNode (MyLeaf "DEFG") (MyLeaf "HIJKL"))
      print tree2

      putStrLn "Tests that prove that MyTree behaves as a Functor."

      print (fmap (*2) tree1)
      print (fmap length tree2)

      putStrLn "Tests that prove that MyTree behaves as an Applicative."

      print ((MyLeaf (*2)) <*> tree1)
      print ((MyLeaf init) <*> tree2)

      putStrLn "Tests that prove that MyTree behaves as a Monad."

      print (tree1 >>= (\x -> MyLeaf (x+200)))
      print (tree2 >>= (\x -> MyLeaf (tail x)))

      putStrLn "Program ends."

The output of the previous program follows:

Program begins.
Tests that prove that MyTree behaves as a type constructor.
MyNode (MyLeaf 3) (MyNode (MyLeaf 4) (MyLeaf 5))
MyNode (MyLeaf "ABC") (MyNode (MyLeaf "DEFG") (MyLeaf "HIJKL"))
Tests that prove that MyTree behaves as a Functor.
MyNode (MyLeaf 6) (MyNode (MyLeaf 8) (MyLeaf 10))
MyNode (MyLeaf 3) (MyNode (MyLeaf 4) (MyLeaf 5))
Tests that prove that MyTree behaves as an Applicative.
MyNode (MyLeaf 6) (MyNode (MyLeaf 8) (MyLeaf 10))
MyNode (MyLeaf "AB") (MyNode (MyLeaf "DEF") (MyLeaf "HIJK"))
Tests that prove that MyTree behaves as a Monad.
MyNode (MyLeaf 203) (MyNode (MyLeaf 204) (MyLeaf 205))
MyNode (MyLeaf "BC") (MyNode (MyLeaf "EFG") (MyLeaf "IJKL"))
Program ends.

 

Third type of tree: good as a Functor, good as an Applicative, good as a Monad.

There is a third type of tree that functions well as a Functor, Applicative, and Monad! The structure of this remarkable type is as follows:

data MyTree a = MyNode a [MyTree a]

I mentioned this type of tree at the end of my blog post titled “Trees in Haskell”.  I thought I would close my presentation there, because the gentleman with the chainsaw seemed to get a little upset. But now (and having looked over my shoulder) I can continue.

The two previous types of trees that we studied had one thing in common, they were lousy Applicatives. Well, this type of tree is a great Functor, Applicative, and Monad. Let us see why.

This type of tree has the characteristic of having the element together with the subtrees in the node, as the binary tree does. But the difference in this type of tree is that the subtrees are tucked in a list. This is a huge improvement. It means that in each node, the number of subtrees can be as many as we need. The subtrees can expand “horizontally” in number, something that the other types of trees did not allow. We will see how the concept of the list of subtrees permits this type of tree to be a successful, useful and intuitive Functor, Applicative, and Monad.

First of all, as a Functor, fmap applies the function to the element of the Node as well as to each element/subtree in the list. Easy enough.

As an Applicative, we have to program <*> in order to accommodate a tree of functions and a tree of elements. Let us call the tree of functions as (MyNode f treeFunctionList) and let us call the tree of elements as (MyNode x treeElementList). First of all, our Applicative should apply the function f to element x, and the output should be the element of the resulting node. The list that will accompany this element will include (i) all the outputs of all applications of the function f to the list of the elements (map (fmap f) treeElementList) , as well as (ii) all the applications of all functions in the list of functions to all elements in the list of elements (map (<*> (MyNode x treeElementList)) treeFunctionList). Thus, the Node will have f x as element and it will also have a list of every possible application of each function from the tree of functions and each element from the list of elements. The reason all these can be accommodated is that we have a list, i.e. a “horizontally” expanding structure that can keep all possible combinations of application of functions to elements.

Let us now see why this type of tree can also function as a useful Monad. According to the Monad declaration, the function a -> m b, that we apply to the tree m a we receive as input, should produce a tree m b as output. In our case, in order for our Monad to be intuitive and useful,  we should apply the function f :: a -> m b to (i) the root element of the input tree, as follows: f x, as well as (ii) the treelist of the input tree, as follows: map (>>= f) treeList. The application of the function f to the root element x will produce a tree, thus an element and a treelist. The element will be the root element and the treelist will be the first part of the resulting list, the second part being the result of map (>>= f) treeList.

Again, what makes all this possible is that we have a list of trees next to our root element and we can use this list to tuck in the trees that are produced from all the operations. For example, the input’s root element alone, with the application of the function f produces a whole tree. And a whole tree is also each subtree of the list that accompanies the input’s root element. Thus, it is the list’s unlimited expansion capability that can hold all these trees that are produced and that can make this Monad functional and useful.

module Main where

import Control.Applicative

data MyTree a = MyNode a [MyTree a]
                deriving (Show)

instance Functor MyTree where
   fmap f (MyNode x treeList) = MyNode (f x) (map (fmap f) treeList)

instance Applicative MyTree where
   pure x = MyNode x []
   (MyNode f treeFunctionList) <*> (MyNode x treeElementList) =
      MyNode (f x) ( (map (fmap f) treeElementList) ++ (map (<*> (MyNode x treeElementList)) treeFunctionList) )

instance Monad MyTree where
   return x = MyNode x []
   MyNode x treeList >>= f = MyNode x' (treeList' ++ map (>>= f) treeList)
      where MyNode x' treeList' = f x

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that MyTree behaves as a type constructor."

      let tree1 = MyNode 5 [MyNode 3 [], MyNode 2 []]
      print tree1

      let tree2 = MyNode "ABC" [MyNode "DEFG" [], MyNode "HIJKL" []]
      print tree2

      putStrLn "Tests that prove that MyTree behaves as a Functor."

      print (fmap (*2) tree1)
      print (fmap length tree2)

      putStrLn "Tests that prove that MyTree behaves as an Applicative."

      print ((MyNode (*2) []) <*> tree1)
      print ((MyNode (*2) [MyNode (+100) [], MyNode (+1000) []]) <*> tree1)
      print ((MyNode init []) <*> tree2)
      print ((MyNode init [MyNode reverse [MyNode tail []]]) <*> tree2)

      putStrLn "Tests that prove that MyTree behaves as a Monad."

      print (tree1 >>= (\x -> MyNode (x+200) []))
      print (tree2 >>= (\x -> MyNode (tail x) []))

      putStrLn "Program ends."

The output of the previous program follows:

Program begins.
Tests that prove that MyTree behaves as a type constructor.
MyNode 5 [MyNode 3 [],MyNode 2 []]
MyNode "ABC" [MyNode "DEFG" [],MyNode "HIJKL" []]
Tests that prove that MyTree behaves as a Functor.
MyNode 10 [MyNode 6 [],MyNode 4 []]
MyNode 3 [MyNode 4 [],MyNode 5 []]
Tests that prove that MyTree behaves as an Applicative.
MyNode 10 [MyNode 6 [],MyNode 4 []]
MyNode 10 [MyNode 6 [],MyNode 4 [],MyNode 105 [MyNode 103 [],MyNode 102 []],MyNode 1005 [MyNode 1003 [],MyNode 1002 []]]
MyNode "AB" [MyNode "DEF" [],MyNode "HIJK" []]
MyNode "AB" [MyNode "DEF" [],MyNode "HIJK" [],MyNode "CBA" [MyNode "GFED" [],MyNode "LKJIH" [],MyNode "BC" [MyNode "EFG" [],MyNode "IJKL" []]]]
Tests that prove that MyTree behaves as a Monad.
MyNode 205 [MyNode 203 [],MyNode 202 []]
MyNode "BC" [MyNode "EFG" [],MyNode "IJKL" []]
Program ends
Posted in Development

The difference between function application and bind in Haskell

If you have read my blog posts so far, you will have understood the difference between normal function application in Haskell and the monadic bind (>>=).

What I essentially talk about, is the difference between

f x

and

x >>= f

You cannot use one in place of the other.

The first, f x, means that we have a function f of type a -> b and an object x of type a. We apply the function f to object x and we get an object f x of type b.

The second, x >>= f, means  that we have a type constructor turned into a Monad. Let us call our type constructor/Monad m. We have an object x of type m a and a function f of type a -> m b. x >>= f means that we “apply” the function f to object x. Notice that I wrote the word “apply” in quotes. I did that because this is not normal function application. We “force” the object of type m a as input to a function f that takes not an object of type m a but an object of type a. This is why we need to use >>=, instead of normal function application. >>= has been programmed to take an object of type m a and a function of type a -> m b and return an object of type m b.

Thus, when we see something like f x, we should think of a normal object x of type a and a normal function f :: a -> b. And we know that f x is of (normal) type b.

But when we see something like x >>= f, we should think of a type constructor/Monad m, of an elevated object x of type m a and of a function f :: a -> m b that takes a normal object of type a and returns an elevated object of type m b. And we know that x >>= f is of (elevated) type m b.

Posted in Development

The List Monad

Like Maybe, [] is also a type constructor elevated into a Functor, Applicative, and Monad.

The code that turns [] into a Functor follows:

instance Functor [] where
   fmap = map

The previous code can be written equivalently:

instance Functor [] where
   fmap _ [] = []
   fmap f (x:xs) = f x : fmap f xs

The code that turns [] into an Applicative follows:

instance Applicative [] where
   pure x = [x]
   fs <*> xs = [ f x | f <- fs, x <- xs ]

The previous code can be written equivalently:

instance Applicative [] where
   pure a = [a]          
   [] <*> _  = []
   (f:fs) <*> as = map f as ++ fs <*> as

The code that turns [] into a Monad follows:

instance  Monad []  where
   return x = [x]
   m >>= k = concat (map k m)

The previous code can be written equivalently:

instance Monad [] where
   return x = [x]
   xs >>= f =
      let yss = map f xs
      in concat yss

Just as in the case of Maybe, we do not have to include any of the previous code, because it is already built in Haskell. But, just as in the case of Maybe, studying this code will be of great help to us.

OK, let us discuss what we just saw. First of all, for [] to become a Functor, we need to decide how we want to apply a function to a list of elements. The decision taken by Haskell is to apply the function to each element of the list. There is a way to apply a function to all elements of a list. A function that does that already exist and it is the map function. Thus, the fmap function that we must create to do this job is the map function.

For [] to become an Applicative, we need to decide how we want to apply a list of functions to a list of elements. The decision taken by Haskell is to apply each function from the list of functions to all elements from the list of elements.

For [] to become a Monad, we must decide how to implement bind (>>=). Bind has to take a list object m and a function k with type signature of the type of a list element to the type of the list, thus something like a -> [b]. The decision taken by Haskell is to take the list m and apply the function k (of type a -> [b]) to each element of the list. Since we will get a list of lists as output, whereas we only want a list, in order to be consistent with the type of >>=, we need to flatten the resulting list of lists to a list, and this can e done by applying the function concat.

The astute reader will remember my blog post “The correspondence between Monads in Category Theory and Monads in Haskell”. I that blog post, I have explained how to derive the following relationship between bind and other functions for a Monad:

m >>= k is equivalent to join . fmap k . m

In the case of the [] Monad, this holds true, (as it should for all Monads).

Indeed, join for the [] Monad is the concat function. This is because join for any Monad has the type M (M a) -> M a, i.e. join “flattens” the Monad space. As far as list are concerned, concat has the type [[a]] -> [a]. Thus concat is the join function for lists.Also, fmap for the [] Monad is the fmap function. Thus:

join . fmap k . m can be written as concat . map k . m, or, equivalently, as concat (map k m), which is the definition used for >>= in the previous code.

Again, let me stress why we need join, i.e. concat. We need join because fmap applies a function k of type a -> m b, thus a function of type a -> [b]. This function is applied to an object of type m a, thus an object of type [a]. The result will be an object of type m (m b), thus [[b]]. Thus, we need a join in the end, in order to collapse, to flatten the m (m b) to m b, thus to flatten the [[b]] to [b].

So, when we write concat (map k m)m is of type [a], k if of type a -> [b], the output of map k m is of type [[b]] and the output of concat (map k m) is of type [b].

Thus, a great way to create the definition for >>= is to use the following equation that we learned and proved in my blog post “The correspondence between Monads in Category Theory and Monads in Haskell”:

g >>= f is equivalent to join . fmap f . g

Of course, for a simple case like the Maybe Monad, this may be overkill. For the Maybe Monad, bind is implemented as follows:

Just x >>= f  = f x

We could have implemented it using join ad fmap, but it would have been overkill and redundant. Instead of the simple definiton

Just x >>= f  = f x

we would have

Just x >>= f  = join (fmap f  (Just x))

where f is of type a -> Maybe b. Thus fmap would have created an object of type Just (f x), and since f x is of type a -> Maybe b, the object Just (f x) would be of type Just (Just x)). Thus we would need the join in the declaration to flatten Just (Just x)) to Just x. So we save ourselves the back and forth by the simpler definition

Just x >>= f  = f x.

But, yes, in cases that are more complex, it may be a good practice, or the only practice, to create bind (g >>= f) as join . fmap f . g.

OK, let us see now how [] functions as a type constructor, Functor, Applicative and Monad, using a small proof-of-concept program:

module Main where

import Control.Applicative

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that [] behaves as a type constructor."

      print ([1])
      print ([1,2,3,4])
      print ([("hello",100),("world",200)])

      putStrLn "Tests that prove that [] behaves as a Functor."

      print (fmap length ["this", "is", "a", "nice", "bike"])
      print (fmap (\x -> x + 1) [100, 200, 300])

      putStrLn "Tests that prove that [] behaves as an Applicative."

      print ([(*2),(+100)] <*> [1,2,3,4])
      print ([fst, snd] <*> [(1,2),(100,200)])

      putStrLn "Tests that prove that [] behaves as a Monad."

      print ([10,20,30] >>= (\x -> [x+1, x+2, x+3]))
      print ([(1,2), (3,4), (5,6)] >>= (\x -> [(snd x, fst x)]))

      putStrLn  "Bonus section: >>= behaves like the function concatMap."

      print (concatMap (\x -> [x+1, x+2, x+3]) [10,20,30])
      print (concatMap (\x -> [(snd x, fst x)]) [(1,2), (3,4), (5,6)])

      putStrLn "Program ends."

This is the output of the previous program:

Program begins.
Tests that prove that [] behaves as a type constructor.
[1]
[1,2,3,4]
[("hello",100),("world",200)]
Tests that prove that [] behaves as a Functor.
[4,2,1,4,4]
[101,201,301]
Tests that prove that [] behaves as an Applicative.
[2,4,6,8,101,102,103,104]
[1,100,2,200]
Tests that prove that [] behaves as a Monad.
[11,12,13,21,22,23,31,32,33]
[(2,1),(4,3),(6,5)]
Bonus section: >>= behaves like the function concatMap.
[11,12,13,21,22,23,31,32,33]
[(2,1),(4,3),(6,5)]
Program ends.
Posted in Development

The Maybe Monad

Maybe is predefined and built in Haskell. Maybe is a type constructor whose definition is built-in as:

data Maybe a = Nothing | Just a

Its meaning as a type constructor is that Maybe accommodates cases where there might be no value. Indeed, in many cases we may have a value or our value may be null. In other languages we may have to have two different types for our value, in Haskell we only need Maybe. Maybe can be Nothing or Just our value. The words “Nothing” and “Just” have no meaning in Haskell. “Nothing” does not mean “null” in Haskell. Again, “Nothing” and “Just” have no meaning in Haskell. They are just words that define different values for the Maybe type constructor. It is how we assign these values and how we handle them in our code that gives them “meaning”.

So, we could have as easily created the following type:

data Maybe a = Nothing1 | Just1 a

or the following type:

data Maybe a = Invalid | Precisely a

or the following type:

data Maybe a = Nonexistent | Ditto a

and Maybe would have exactly the same functionality.

It is worth noting that Nothing precedes Just, because the creators of Maybe wanted Nothing to always be smaller when compared to Just with any value. Of course, this works by also adding the deriving (Show, Ord, Eq) expression at the end of Maybe’s declaration. We will see examples of this issue when I will provide a program that proves Maybe’s behavior.

Maybe is a type constructor, but Haskell has built-in code that elevates it to a Functor, an Applicative, and a Monad. I will now present you with the built-in code for Maybe, in order to understand how Maybe has been made to behave as a Functor, an Applicative, and a Monad. It is really easy to see:


data Maybe a = Nothing
             | Just a

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

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

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

instance Applicative Maybe where
   pure = Just
   (Just f) <*> (Just x) = Just (f x)
   _        <*> _        = Nothing

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

instance Monad Maybe where
   return x = Just x
   Just x >>= f  = f x
   Nothing >>= f = Nothing
   x >> y = x >>= \_ -> y
   fail _ = Nothing

But the following code is general for Functors, Applicatives and Monads:

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

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

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

Thus, the code that only applies to Maybe is:


data Maybe a = Nothing
             | Just a

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

instance Applicative Maybe where
   pure = Just
   (Just f) <*> (Just x) = Just (f x)
   _        <*> _        = Nothing

instance Monad Maybe where
   return x = Just x
   Just x >>= f  = f x
   Nothing >>= f = Nothing
   x >> y = x >>= \_ -> y
   fail _ = Nothing

The last two lines in the previous program define the >> and fail functions that are optional to define. Thus the only code that is needed to elevate Maybe to a Monad is:


instance Monad Maybe where
   return x = Just x
   Just x >>= f  = f x
   Nothing >>= f = Nothing

The following program proves that Maybe behaves as a type constructor, a Functor, an Applicative and a Monad:


module Main where

import Control.Applicative

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that Maybe behaves as a type constructor."

      print (Just 10)
      print (Just 35 > Just 12)
      print (Nothing < Just (-12))
      print (Nothing < Just "test")

      putStrLn "Tests that prove that Maybe behaves as a Functor."

      print (fmap length (Just [1,2,3,4]))
      print (fmap length Nothing)

      putStrLn "Tests that prove that Maybe behaves as an Applicative."

      print ((Just length) <*> (Just [1,2,3,4,5]))
      print ((Just length) <*> Nothing)

      putStrLn "Tests that prove that Maybe behaves as a Monad."

      print (Just [1,2,3,4,5,6] >>= (\xs -> Just (length xs)))
      print (Nothing >>= (\xs -> Just (length xs)))

      putStrLn "Program ends."

The output of the previous program is:


Program begins.
Tests that prove that Maybe behaves as a type constructor.
Just 10
True
True
True
Tests that prove that Maybe behaves as a Functor.
Just 4
Nothing
Tests that prove that Maybe behaves as an Applicative.
Just 5
Nothing
Tests that prove that Maybe behaves as a Monad.
Just 6
Nothing
Program ends.

In the previous program we did not need to include the built-in code that makes Maybe behave as a type constructor, a Functor, an Applicative and a Monad, exactly because this code is already built-in.

Since Maybe is already predefined, we do not need to create it. But in order to demonstrate Haskell’s built-in code in a program, let the following program define our own Maybe type constructor: let us call it Maybe1. Here we go:


module Main where

import Control.Applicative

data Maybe1 a = Nothing1
              | Just1 a
              deriving (Show, Ord, Eq)

instance Functor Maybe1 where
   fmap f (Just1 x) = Just1 (f x)
   fmap _ Nothing1  = Nothing1

instance Applicative Maybe1 where
   pure = Just1
   (Just1 f) <*> (Just1 x) = Just1 (f x)
   _        <*> _        = Nothing1

instance Monad Maybe1 where
   return x = Just1 x
   Just1 x >>= f  = f x
   Nothing1 >>= f = Nothing1
   x >> y = x >>= \_ -> y
   fail _ = Nothing1

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that Maybe1 behaves as a type constructor."

      print (Just1 10)
      print (Just1 35 > Just1 12)
      print (Nothing1 < Just1 (-12))
      print (Nothing1 < Just1 "test")

      putStrLn "Tests that prove that Maybe1 behaves as a Functor."

      print (fmap length (Just1 [1,2,3,4]))
      print (fmap length Nothing1)

      putStrLn "Tests that prove that Maybe1 behaves as an Applicative."

      print ((Just1 length) <*> (Just1 [1,2,3,4,5]))
      print ((Just1 length) <*> Nothing1)

      putStrLn "Tests that prove that Maybe1 behaves as a Monad."

      print (Just1 [1,2,3,4,5,6] >>= (\xs -> Just1 (length xs)))
      print (Nothing1 >>= (\xs -> Just1 (length xs)))

      putStrLn "Program ends."

The previous program produces the following output:


Program begins.
Tests that prove that Maybe1 behaves as a type constructor.
Just1 10
True
True
True
Tests that prove that Maybe1 behaves as a Functor.
Just1 4
Nothing1
Tests that prove that Maybe1 behaves as an Applicative.
Just1 5
Nothing1
Tests that prove that Maybe1 behaves as a Monad.
Just1 6
Nothing1
Program ends.

Update – Monday, March 10, 2014:

A great question was posed to me: Haskell implements the Maybe Monad as

Just x >>= f  = f x

But shouldn’t Haskell have implemented it as

Just x >>= f  = Just (f x)

instead? This way, the output of >>= will be of type m b, as is supposed to be according to the type signature of >>=, which is

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

Great question.

The answer is that Haskell is correct. This is because f represents a function with type signature a -> m b, thus the output of >>= will certainly be of the elevated type m b. So, when we see the symbol f in the definition (implementation) of >>=

Just x >>= f  = f x

we must realize that f is not of type a -> b but of type a -> m b, just as the declaration of >>= demands:

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

The function f in the definition

Just x >>= f  = f x

is the function (a -> m b) in the declaration

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

So x is of type a and the application of function f on x, denoted as f x, will produce output of type m b.

You see, it easy to get confused. This is because of the fact that when we provide the definition for fmap, f denotes a function with type a -> b. But when we provide the definition for >>=, f denotes a function with type a -> m b. So, please be careful as to what each argument means in each case.

Posted in Development