web developer & system programmer

coder . cl

ramblings and thoughts on programming...

monoids in haskell

published: 06-09-2012 / updated: 06-09-2012
posted in: development, haskell, programming, tips
by Daniel Molina Wegener

A Monoid is a well known abstraction where you have an operation or function, a neutral element and a set that can be operated with that operation or function. Given that description, on Haskell you have an already defined Monoid class which is implemented on common types like Strings. The main monoidal String operation is the concatenation, using the (++) operation, so can have a clear example of the given description in the code that follows.

module Main (main) where

import Data.Monoid

main :: IO ()
main = let n = "x" `mappend` "y" `mappend` "z"
       in putStrLn n

The code above will produce the output xyz, because the default monidal form of the String is defined as \langle String, [], (++) \rangle, which has its formal definition as Monoid as \langle \cdot, \varepsilon, A \rangle, where \cdot is the operation — using (++) for the default string Monoid — \varepsilon is the neutral element — using [] or “” for the default string Monoid — and A is the set to operate — using the String type as set.

With this string description, we can clearly define, for example, a audio streaming IO Monad that appends stream buffers using a monoidal form. The default Monoid class definition in Haskell defines three main monoidal operations called mempty, mappend and mconcat, using a single class variable or type binding as set and allowing a non strict monoidal implementation of the class, but clear enough to be used without too much documentation, due to its natural description.

class Monoid a where
    mempty :: a
    mappend :: a -> a -> a
    mconcat :: [a] -> a

Where mempty is the neutral element, mappend is the applied operation between two members of the set — in this case a class variable — and mconcat which applies mappend on the given subset of a class variable list using the mappend definition acting as folding function. On a previous post, we have defined the Monoid class on Python, and due to its dynamic type system, that class seems to be untyped, and due to the strong-static type system in Haskell each Monoid class should be defined with a type binding. On the “re: monoids in python” post, we have seen a challenge, as follows.

  1. Using only listm, how would you concatenate a list of lists. That is, how would you transform [[a, b, c], [d, e], [f], []] into [a, b, c, d, e, f]?
  2. The reverse of a monoid is a monoid where the operator take its arguments in reverse order. Create a method, reverse, that creates a reverse monoid. What is listm.reverse()?
  3. Are there monoids that are fixed-points of the star method? That is, is there a monoid m such that m and m.star() are indistinguishable? (Side challenge: formalize the notion of “indistinguishable”.)
  4. Do monoids have a dual concept? Monoids, as defined here, are roughly an embodiment of “map/reduce”, which is used to process and analyze data, potentially taking a large body of data and reducing it. Is there a similar concept, a “comonoid”, that generates data, instead of reducing it?
  5. Let lift = int, and let op return an int. Can we enumerate all possible monoids? If not, what can we enumerate?

For the first challenge (No. 1), the listm Monoid is the list monoid. As Haskell does have a previously defined listm with the the proper Monoid class instance, beating this challenge in Haskell is almost clear, without using too much code.

module Main (main) where

import Data.Monoid

main :: IO ()
main = let n = mconcat [['a', 'b', 'c'], ['d', 'e'], ['f'], []]
       in putStrLn $ show n

The second challenge is easy to solve too. At least for listm, you can use the reverse function to revert the evaluation order of list arguments.

module Main (main) where

import Data.Monoid

main :: IO ()
main = let n = (reverse [1, 2, 3]) `mappend` (reverse [4, 5, 6])
       in putStrLn $ show n

As Python does, the \langle str, str(), + \rangle Monoid is a fixed-point Monoid and Haskell has the same fixed-point Monoid as it was described as \langle String, [], (++) \rangle, and you can appreciate the results as follows.

module Main (main) where

import Data.Foldable
import Data.Monoid

main :: IO ()
main = let n = ['a', 'b', 'c'] `mappend` "123"
           m = "abc" `mappend` ['1', '2', '3']
       in (putStrLn $ show n)
          >> (putStrLn $ show m)

If you implement a streaming IO Monad that appends stream buffers using a Monoid instance, you will have a Co-Monoid generating data, mainly if it has a separate audio and video processing, so you will have a separate channels for both streams with different data types, using one input stream. For example if you have a transmission from a radio station, where you have streaming audio for the radio signal and live show from Internet, so you can process both streams from one single stream which is being processed using the mappend over retrieved buffers.

No coments yet.

post a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>