Some Tests On Haskell Concurrent Programming

The tests are here https://massimo-zaniboni.github.io/threads-post/  and this is the repo containing the complete source code https://github.com/massimo-zaniboni/threads-post

Understanding Traversable

I’m a poor object-oriented programmer, not versed to category theory and advanced Haskell. I understand Functor, Applicative, Foldable, but what is the sense behind Traversable?

class (Functor t, Foldable t) => Traversable t where

   -- | Map each element of a structure to an action, evaluate these actions
   -- from left to right, and collect the results. For a version that ignores
   -- the results see 'Data.Foldable.traverse_'.
   traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
   traverse f = sequenceA . fmap f

   -- | Evaluate each action in the structure from left to right, and
   -- and collect the results. For a version that ignores the results
   -- see 'Data.Foldable.sequenceA_'.  
   sequenceA :: Applicative f => t (f a) -> f (t a)
   sequenceA = traverse id

In particular what is the meaning of traverse f = sequenceA . fmap f?

TL;DR

For beginner Haskell programmers specific class instances are more understandable and useful than abstract class definitions. It is better understanding and using the IO Monad, or the Maybe Monad, than knowing perfectly the theory behind the generic Monad class definition. For the same reasons, it is better understanding different instances of Traversable class, than the abstract theory behind it.

Traverse a List applying Maybe semantic

Traversable uses functions with two generic types: f that is an Applicative context, t that is a Foldable Functor.
We will start with an example using Maybe for the applicative part (the f), and List for the Functor part (the t).
Maybe has a simple and clear Applicative semantic: stop the computation and return Nothing when one of intermediate passages returns Nothing.
List has a simple Functor semantic: fmap applies a function to every element of the list.

sequenceA

The sequenceA function became

   sequenceA :: [Maybe a] -> Maybe [a]

Studying type definition, the semantic is clear: extract Just from the elements of the list, and if there is any Nothing element, return Nothing instead of the list.

{-# LANGUAGE ScopedTypeVariables #-}

module Main where

import Data.Traversable
import Control.Applicative
import Data.List as L

-- | All the tests of the code assertions.
main = putStrLn $ show $ L.all id [
           mtest1
        ,  mtest2
        ,  mtest1M
        ,  mtest2M
        ,  mtest3
        ,  mtest4
        ,  mtest3M
        ,  mtest4M
        ,  mtest4M'
        ,  stest1
        ,  stest2
        ,  stest3
        ,  ltest1
        ,  ltest2
        ]

We will remove Just from the list:

mf1 :: Maybe [Int]
mf1 = sequenceA [Just 1, Just 2]

mtest1 :: Bool
mtest1 = (mf1 == Just [1, 2])

If we pass a Nothing value, then the entire result became Nothing:

mf2 :: Maybe [Int]
mf2 = sequenceA [Just 1, Just 2, Nothing]

mtest2 :: Bool
mtest2 = (mf2 == Nothing)

We can rewrite these functions using the do-notation:

mf1M :: Maybe [Int]
mf1M = do
  x <- return 1
  y <- return 2
  return [x, y]

mtest1M = (mf1 == mf1M)

mf2M :: Maybe [Int]
mf2M = do
  x <- return 1
  y <- return 2
  z <- empty
  return [x, y, z]

mtest2M = (mf2 == mf2M)

So what is the semantic of sequenceA for this specific instance of Traversable? The semantic is self-explanatory studying its type sequenceA :: [Maybe a] -> Maybe [a]. But sadly for us, we can not generalize it, as we will see in next sections.

traverse

The traverse function became:

   traverse   :: (a -> Maybe b) -> [a] -> Maybe [b]

For playing with traverse, we need a function returning Maybe:

mf :: Int -> Maybe Int
mf x = if (even x) then Just x else Nothing

and then:

mf3 :: Maybe [Int]
mf3 = traverse mf [2,4]
mtest3 = (mf3 == Just [2,4])

All elements of the list are even, and so the same list without modifications is returned.
If we insert a not even element, then Nothing is returned:

mf4 :: Maybe [Int]
mf4 = traverse mf [2,4,5]
mtest4 = (mf4 == Nothing)

As usual we can rewrite using the do notation

mf3M :: Maybe [Int]
mf3M = do
  x <- mf 2
  y <- mf 4
  return [x, y]

mtest3M = (mf3M == mf3)

mf4M :: Maybe [Int]
mf4M = do
  x <- mf 2
  y <- mf 4
  z <- mf 5
  return [x, y, z]

mtest4M = (mf4M == mf4)


Traversable defines also mapM that is simply traverse. We can rewrite in this way:

mf4M' :: Maybe [Int]
mf4M' = do
  r <- mapM mf [2, 4, 5]
  return r

mtest4M' = (mf4M' == mf4M)

In this case, the traverse function captures the well known concept of mapM inside the Maybe Applicative.

Traverse a List applying List semantic

Now we will use an instance of Traversable with List both as container (for t), and as Applicative (for f).
The List applicative behavior is similar to Prolog: it combines all possible combinations of generators, filtering on constraints.
The List functor behavior is the usual map: it applies a function to every element of the list.

sequenceA

In this case, we have:

   sequenceA :: [[a]] -> [[a]]
   sequenceA = traverse id

where

   traverse  :: (a -> [b]) -> [a] -> [[b]]
   traverse f = List.foldr cons_f (pure [])
     where consF x ys = (:) <$> f x <*> ys

Due to specific implementation of traverse for List, sequenceA became a combinatoric function performing a “transpose-like” operation, combining columns with lines:

stest1 = sequenceA [[1,2,3], [4,5]] == [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]

The corresponding function defined using Prolog-like semantic is

transposeAndCombine :: [[a]] -> [[a]]
transposeAndCombine linesAndCols = tc [] linesAndCols
 where
  tc :: [a] -> [[a]] -> [[a]]
  tc r1 [] = return r1
  tc r1 (xs:rs) = do
    x <- xs
    tc (r1 ++ [x]) rs

stest3 = let l = [[1,2,3], [4,5]]
         in  transposeAndCombine l == sequenceA l

In case of Maybe the Nothing value invalidates all the computations. In case of List the value invalidating all computations is []:

stest2 = sequenceA [[1,2,3], [4,5], []] == []

In this case the sequenceA function has a rather useful and reusable behaviour: transpose and combine columns with lines. Knowing this behavior in advance, the sequenceA function can be called directly, without using the do-notation form that is less clear.
But this behavior is very different from the Traversable instance with Maybe and Applicative. So the Traversable class does not help us in predicting the sequenceA semantic. We had to study it case by case.

traverse

traverse became:

   traverse  :: (a -> [b]) -> [a] -> [[b]]
   traverse f = List.foldr cons_f (pure [])
     where consF x ys = (:) <$> f x <*> ys

If we play with traverse, we obtain:

lf :: Int -> [Int]
lf x = [x * 10, x * 100]

lxs :: [Int]
lxs = [1, 2]

lf1 :: [[Int]]
lf1 = traverse lf lxs

lfxs = [[10, 20], [10, 200], [100, 20], [100, 200]]

ltest1 = (lf1 == lfxs)

The semantic using Prolog-like rules is not immediate. A first but bad version is:

lf1M' :: [Int]
lf1M' = do
  x <- lxs
  y <- lf x
  return y

ltest1M' = (lf1M' == [10, 20, 100, 200])

It isn’t correct because it combines too few things.
The behavior of traverse is: transposeAndCombine the results of the function applications with the list of possible arguments. The corresponding code is:

lf1AsTransf :: [[Int]]
lf1AsTransf = transposeAndCombine (map lf lxs)

ltest2 = (lf1AsTransf == lfxs)

In this form the code is clear, so we don’t derive a Prolog-like version.
In this case traverse has not a basic and natural semantic. Probably there are not much cases in real-life code, where we want such strange and extreme combinatoric behavior. Probably we are more interested to the behavior of functions like lfm1M', expressed with the do-notation.

Conclusions

After these examples, we can return to our original question: what is the meaning of traverse f = sequenceA . fmap f? My lazy and arrogant answer is: I don’t bother! :-)
The motivations are:

• also if I can grasp the concepts behind Traversable, it will not help in understanding real-life code using Traversable, because every instance of traverse and sequenceA has a very different and specific semantic.
• so I must study each instance of Traversable in isolation, for understanding its behavior. This is similar to IO Monad, Maybe Monad, Either Monad: knowing the Monad concepts helps, but every instance has its proper semantic and usage case, and it must be mastered apart.
• maybe instance by instance, I can someday comprehend the concepts behind Traversable, but up to date this can be postponed, because it seems more complex to master respect Functor and other base class.
• in the end I’m a poor OO programmer, not a mathematician expert of category-theory.

In Haskell there are very few class, and they are usually very abstract and tied to category theory concepts: Monad, Functor, Applicative, etc.. The laws of these class allows for nice combinations of instances. This is a sign of the power and effectiveness of category-theory. But these class are mainly used for writing composable DSLs or nice libraries. End-user code uses instead specific instances. Each instance has a specific semantic that can not be predicted only from the knowledge of the reference class. This is in contrast with the OO world where a parent class describes exactly the behavior of a child class. For example Monad is a class describing nice properties for composable actions. But the semantic of a List Monad (Prolog-like rules) is very different from the semantic of an Either Monad (actions with exceptions).
So Traversable can represent many different things in Haskell. Also if I don’t understand completely its meaning, because it is too much abstract and tied to category-theory universe, this does not prevent me from studying and comprehending perfectly its specific instances, and using them in end-user code.

Combinatorial Problems in Haskell

A Simple Exercise

"Given three sets of characters, build all the possible words of 3 characters, with the first character from the first set, the second character from the second set, and the last character from the last set."

This is an exercise adapted from a similar one on the Haskell Programming from first principles book, and the results are part of the work done during the Haskell Day with my group of Haskellers!

{-# LANGUAGE OverloadedStrings #-}

module Combinatorial where


set1 :: [Char]
set1 = "ab"

set2 :: [Char]
set2 = "12"

set3 :: [Char]
set3 = set1

The Recursive Solution

In a classical imperative solution we would write three nested loops trying all combinations. In Haskell we can replace loops with recursion.

allWordsOf3Chars :: [Char] -> [Char] -> [Char] -> [String]
allWordsOf3Chars set1 set2 set3 = combine1 set1 set2 set3
 where

   combine1 [] _ _ = []
   combine1 (c1:cs) set2 set3 = combine2 c1 set2 set3 ++ combine1 cs set2 set3

   combine2 _ [] _ = []
   combine2 c1 (c2:cs) set3 = combine3 c1 c2 set3 ++ combine2 c1 cs set3

   combine3 _ _ [] = []
   combine3 c1 c2 (c3:cs) = [[c1, c2, c3]] ++ combine3 c1 c2 cs

We test it

test1 = allWordsOf3Chars set1 set2 set3

  > test1 
  ["a1a","a1b","a2a","a2b","b1a","b1b","b2a","b2b"]

The KISS Solution

In Haskell list comprehension has a combinatorial semantic, and so we can write simply

allWordsOf3Chars' set1 set2 set3
  = [ [c1, c2, c3] | c1 <- set1, c2 <- set2, c3 <- set3 ]

isOk1 = test1 == (allWordsOf3Chars' set1 set2 set3)

  > isOk1
  True

The KISS solution is very easy to read, and very fast to write. A good selling point for the Haskell language.

The Advanced Solution

In Haskell the Applicative instance of List, has a combinatorial semantic, so we can write

allWordsOf3Chars'' set1 set2 set3
  = (\c1 c2 c3 -> [c1, c2, c3] ) <$> set1 <*> set2 <*> set3

isOk2 = test1 == (allWordsOf3Chars'' set1 set2 set3)

  > isOk2
  True

The Extended Exercise

We can generalize the first problem, passing a list of sets of chars, instead of only 3 sets.

The Extended Recursive Solution

In an imperative language, generalizing the solution is not simple, because we have a number of loops that is not fixed.

Generalizing the Haskell recursive solution is apparently simpler, because we start already from a recursion, but in practice it is rather hard to figure out the right algorithm.

combineWords :: [String] -> [String]
combineWords sets = combine [] sets 

 where

   combine :: String -> [String] -> [String]
   combine decidedPart [] = [decidedPart]
   combine decidedPart (set1:sets) = choices decidedPart set1 sets 

   choices :: String -> String -> [String] -> [String]
   choices decidedPart currentSet otherSets =
     concatMap (\c -> combine (decidedPart ++ [c]) otherSets) currentSet

isOk3 = test1 == (combineWords [set1, set2, set3])

  > isOk3
  True

This algo works because:

• it has a main loop on each set
• the inner loop selecting one character from the set, calls again the main loop function for obtaining all the possible solutions with the remaining sets

It is a double recursion , and double recursion is often hard to understand.

Writing this algo required too much time respect the initial planned time, and I can not declare that writing it in Haskell is a very easy task.

The extended KISS Solution

Apparently the previous KISS solution based on list comprehension, can not be extended easily to the new version of the problem.

The Extended Advanced Solution

I were in a meetup, so I asked help to someone more knowledgeable than me, and his solution was shocking

combineWords''' :: [String] -> [String]
combineWords''' sets = sequence sets

isOk4 = test1 == (combineWords''' [set1, set2, set3])

  > isOk4
  True

I'm not completely sure of the reason this algo works. I need to study better Haskell, and the magic behind sequence.

  >:t sequence
  sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

In any case this solution shows the power of Haskell abstractions.

The Pragmatic Solution

At this point, I'm not completely satisfied from the Haskell language:

• the recursive solution is too time-consuming and difficult to obtain
• the advanced solution is very short, but too deep for my taste

Is there a better way for solving the problem?

We have a combinatorial problem. For sure an iconic language for expressing and solving combinatorial problems is Prolog. But Haskell supports very well Domain Specific Languages (DSL), and so I can use a Prolog-like DSL language also in Haskell. In this case the MonadPlus applied to lists, is the right instance to use. Note that in case of very complex combinatorial problems, the best solution is probably using high-performance packages like LogicGrowsOnTree, but in this case it is overkill.

combineWords'''' :: [String] -> [String]
combineWords'''' sets = combine [] sets
 where
   combine decidedPart [] = return decidedPart
   combine decidedPart (set1:sets) = do
     c <- set1
     combine (decidedPart ++ [c]) sets

isOk5 = test1 == combineWords'''' [set1, set2, set3]

  > isOk5
  True

Don't ask me why, but this version of the function was very fast and natural to write for me, and very readable. It is based on a simple constraint, and only one recursive call. Probably because a single recursion is easier to understand than the dual recursion version, and because I were accustomed to Prolog.

Also the MonadPlus version of the first version of the problem is very natural to write

allWordsOf3Chars'''' :: [Char] -> [Char] -> [Char] -> [String]
allWordsOf3Chars'''' set1 set2 set3 = do
  c1 <- set1
  c2 <- set2
  c3 <- set3
  return [c1, c2, c3]

isOk6 = test1 == allWordsOf3Chars'''' set1 set2 set3

  > isOk6
  True

Conclusions

If some problems are hard to solve in Haskell, probably there exists some DSL able to express and solve them in a more natural way. The advantage of studying a new DSL, it is that after the initial investment of time, all problems in the same domain can be solved faster.

Probably there is also a payoff in studying better Applicative, Traversable, and sequence function, but for this problem, the MonadPlus solution seems to me a good balance between simplicity and terseness of the code.

RAII Programming in Haskell

I'm using Haskell in production for processing data files, and Data.Text.Lazy is a nice data type, because you can have both simple code managing text, and efficient run-time text processing, because text is loaded chunk by chunk from data streams. It is like a BufferedReader in Java.
But in GHC 8.0.1 some file reading functions do not behave correctly.

import qualified Data.Text.Lazy.IO as LazyText
import qualified Data.Text.Lazy as LazyText

getFileContent1 :: FilePath -> IO String
getFileContent1 fileName = do
  fileContent <- LazyText.readFile fileName
  return $ LazyText.unpack fileContent

-- NOTE: print the file content, reading it chunk by chunk by `fileName`
-- and writing it on `stdout` chunk by chunk.
-- So this simple code, has a nice run-time behaviour.
printFileContent1 fileName = do
  c <- getFileContent1 fileName
  putStrLn c

-- NOTE: this seems a correct function, 
-- but when executed it returns always an empty file content
getFileContent2 :: FilePath -> IO String
getFileContent2 fileName = do
  LazyText.withFile fileName ReadMode $ \handle -> do
    fileContent <- hGetContents handle
    return $ LazyText.unpack fileContent
  
-- NOTE: this code print nothing, due to error on `getFileContent2`
printFileContent2 fileName = do
  c <- getFileContent2 fileName
  putStrLn c

Data.Text.Lazy.IO.readFile is implemented in this way:

readFile :: FilePath -> IO Text
readFile name = openFile name ReadMode >>= hGetContents

Data.Text.Lazy.IO.hGetContents is a function returning the content of the handle chunk by chunk, and closing the handle when all the content is read.
System.IO.withFile is implemented in this way:

 withFile :: FilePath -> IOMode -> (Handle -> IO r) -> IO r
 withFile name mode = bracket (openFile name mode) hClose

so the getFileContent2 code can be expanded to

 getFileContent3 fileName = do
    bracket (openFile fileName ReadMode) hClose $ \handle -> do
      fileContent <- hGetContents handle
      return $ LazyText.unpack fileContent

bracket is one of a series of resource managements functions and monads used for acquiring resources, and releasing them at the end of an action, in a predictable way, and not when the garbage collector arbitrarily decide it. bracket makes management of scarce resources like file handles, database connections, and so on more robust and predictable.
This code will run correctly

 printFileContent3 fileName = do
    bracket (openFile fileName ReadMode) hClose $ \handle -> do
      fileContent <- hGetContents handle
      putStrLn $ LazyText.unpack fileContent

because it will:

• open the file
• read it chunk by chunk, using hGetContents
• print it chunk by chunk, using putStrLn
• close the handle, thanks to bracket resource finalization action

The code printFileContent2 is not running correctly because:

• bracket open the file
• a lazy evaluation thunk LazyText.unpack <$> hGetContents handle is returned from the getFileContent2 function
• bracket close the file handle before the thunk is evaluated

So from this point:

• printFileContent2.putStrLn executed the thunk 
• hGetContents thunk tries to access a closed handle 
• hGetContents returns an empty content, instead of signaling with a run-time exception that the handle is closed

Then printFileContent2 assumes wrongly that the file is an empty file, without any compile time and run time error.
A test case for the bug is on https://github.com/massimo-zaniboni/ghc_lazy_file_content_error , and the bug was signaled to Ghc team.

RAII Programming in Haskell

Resource Acquisition is Initialization (RAII) is a tecnique for having predictable resource usages.
In Haskell, bracket should be RIIA compliant. This implies that bracket must always return the result in a strict way. In this way when the bracket action is called:

• the resources are allocated,
• the action is executed with maximum priority, and predictability,
• the resources are deallocated,
• the result is returned to the caller, completely evaluated, and no further processing involving the resources is required,

So the priority is always given to the called bracket action, and not to the caller action. The caller can be arbitrary complex, and long-running, so the called action had to complete its work with greater priority respect the caller, in order to release its allocated resources in a predictable way. In Haskel terms this signifies that when the caller decides it needs the result of the called code, it evaluates the called thunk completely, without intermediate unevaluated thunks. So called thunk evaluation is an atomic action, and it is not intervaled with the partial execution of the caller code.
This mechanism must be used also in case of nested bracket actions: the called actions must be executed in a strict way.

5 Whys

Why we have the hGetContents error? Because hGetContents is buggy. Why? Because bracket used inside withFile does not behave correctly with unevaluated thunks. Why? Because unevaluated thunks do not play nice with RIIA semantic. Because bracket should force a strict evaluation of the returned action, so the used resources are used completely and in a predictable way.
If bracket forces a strict evaluation of its result, then there will be no bug. This code run correctly

getFileContent4 :: FilePath -> IO String
getFileContent4 fileName = do
  fileContent <- LazyText.readFile fileName
  return $! LazyText.unpack fileContent
  -- NOTE: execute in a strict way, thanks to `$!`

-- NOTE: print the file content, reading it chunk by chunk by `fileName`
-- and writing it on `stdout` chunk by chunk.
-- So this simple code, has a nice run-time behaviour.
printFileContent4 fileName = do
  c <- getFileContent4 fileName
  putStrLn c

Idiomatic Haskell Applicative Code

Not Idiomatic Haskell Code

The many1 function code is the same of the Alternative.many function in the Haskell prelude. The scope of the function is applying zero, one or more times its applicative argument.

{-# LANGUAGE ApplicativeDo #-}

import Control.Applicative

class Alternative f => Alternative1 f where

   -- | Zero or more.
   many1 :: f a -> f [a]
   many1 v = many_v
     where
       many_v = some_v <|> pure []
       some_v = (fmap (:) v) <*> many_v

For me, the some_v inner function is hard to read/comprehend.

Idiomatic Haskell Code

We can rewrite some_v in this way

class Alternative f => Alternative2 f where

   -- | Zero or more.
   many2 :: f a -> f [a]
   many2 v = many_v
     where
       many_v = some_v <|> pure []
       some_v = (:) <$> v <*> many_v

some_v is rewritten using the Applicative idiomatic form:

• we evaluate v and many_v using the specific f Applicative instance rules, and inside the applicative running context
• we use the two results as arguments of the plain Haskell function (:)
• we put the final result of (:) function in the f Functor

The majority of Applicative usage patterns follow this syntactic pattern, or its variation pure f <*> argument1 <*> argument2 <*> ... and after some accustomization, it can be comprehended intuitively without thinking too much to the type definitions, and to the details of involved functional combinators. This is the same for the code like case1 <|> case2, where we recognize immediately that <|> is separating two choices, and we understand the meaning without thinking too much to the underling details.

So we have improved the readability of the first version of the code using the common syntactic form (:) <$> ... <*> ..., instead of the less used fmap (:) <*> ... <*> ... form.

ApplicativeDo

This is a variant of many, but with ApplicativeDo syntax.

class Alternative f => Alternative3 f where

   -- | Zero or more.
   many3 :: f a -> f [a]
   many3 v = some_v <|> pure []

     where

       some_v = do
         v' <- v
         v'' <- (some_v <|> pure [])
         return (v':v'')

The ApplicativeDo notation helps understanding the semantic of some_v because all function arguments are explicit. But the code is a little more verbose respect the idiomatic Applicative pattern usage.

Functional Code

We can rewrite many using explicit types, and adding comments. The resulting code is too much verbose, and not intuitively readable, because there are too much low level details about types and functional combinators, hiding its true meaning.

class Alternative f => Alternative4 f where

   -- | Zero or more.
   many4 :: f a -> f [a]
   many4 v = many_v
     where
       -- TYPE: many_v :: f [a]
       many_v = some_v <|> pure []
       -- if `some_v` fails, return empty list,
       -- terminating `some_v/many_v` mutual recursion.

       -- TYPE: some_v :: f [a]
       some_v 
         = let -- TYPE: fa :: a -> ([a] -> [a])
               fa a = \as -> a:as
               -- `a` is the current result,
               -- to concatenate with next results,
               -- supplied in the [2] part.  

               -- TYPE: fm :: f ([a] -> [a])
               fm = fmap fa v
               -- create something nice to combine using
               -- `<*>` `Applicative` combinator,
               -- having as specific types:
               -- `(<*>) :: f ([a] -> [a]) -> f [a] -> f [a]`  
               -- `fmap :: ([a] -> [a]) -> f [a] -> f [a]

            in fm <*> many_v
               -- [2] part:
               -- concatenate the current result with the next results in `many_v`.
               -- This is a mutual recursion between `many_v` and `some_v`.
               -- At some point `many_v` will fail returning the empty list,
               -- and the recursion loop will stop.

Personal Conclusions

Haskell gives a lot of freedom in the way we can express things, but this freedom can harm code readability. Haskell code using Monads and Applicative instances, should follow few known and accepted idiomatic forms, because otherwise understanding the meaning of complex function combinations is not easy.

All complex function combinations in the end are only function calls, but human mind (at least my mind) does not reason easily with second order functions combined toghether in fancy ways. Instead we are able to recognize common syntactic forms like f <$> arg1 <*> arg2, associating immediately to them a semantic meaning, independently from the more complex low level details.

Higher Harder Functions

Higher order functions combinators are at the base of Haskell power, but they can make the code harder to comprehend, so some counter measure should be adopted.

Do-Notation vs Applicative-Notation

This post is a literate Haskell document, so we must start with some boilerplate code.

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE ApplicativeDo #-}
{-# LANGUAGE Arrows             #-}
{-# LANGUAGE DeriveDataTypeable #-}

module Main where

import Control.Applicative
import qualified Data.Attoparsec.Text.Lazy as A
import Data.Char
import Hakyll

main = do putStrLn "A main is mandatory, but not used in practice."

Attoparsec implements a domain specific language (DSL) for describing parsers. This is an example of function using Attoparsec, and the Applicative idiom.

-- | Parse an hexadecimal number like "%A0", and convert to the
--   the corresponding decimal number 10.
--   This function is written using the Applicative class style.
attoHex :: A.Parser Int
attoHex
  = toInt <$> (A.char '%' *> hexDigit) <*> hexDigit
 where

  hexDigit :: A.Parser Int
  hexDigit = (((-) (ord '0')) . ord) <$> A.choice [A.digit, A.satisfy (A.inClass "A-F")]

  toInt x y = x * 16 + y

What is nice in this code? For sure that there are no low level details about the state of the parser, and the code is only a specification of what we want to parse.

What is not nice in this code? The fact that a novice user must learn some idiomatic use of the Applicative class: toInt <$> ... *> ... <*>. Is this really necessary?

The same function, written using an ApplicativeDo form is:

attoHex' :: A.Parser Int
attoHex' = do
  A.char '%'
  x <- hexDigit
  y <- hexDigit
  return $ x * 16 + y
 where

  hexDigit :: A.Parser Int
  hexDigit = do
    d <- A.choice [A.digit, A.satisfy (A.inClass "A-F")]
    return $ (ord d) - (ord '0')

In this form the arguments of functions are explicit, and the code work-flow is a standard top-down processing. Also the internal function hexDigit is a lot more readable, using explicit arguments, instead of the point-free form.

Higher Order Functions

filter :: (a -> Bool) -> [a] -> [a] is an higher order function accepting another function as argument. Until there are simple functions like filter, it is easy to figure out the final meaning of an expression. When we start combining more complex functions it can become difficult.

Applicative class introduce some non trivial higher order function combinators, generalizing a lot of computation patterns involving parallel computations inside a certain context, with a final composition described by a pure function.

We redefine Maybe, for studying how Applicative instance is supported.

data NMaybe a = NJust a | NNothing

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

This is the standard instance of Maybe, but defined for NMaybe.

instance  Functor NMaybe  where
  fmap _ NNothing       = NNothing
  fmap f (NJust a)      = NJust (f a)

Recap this:

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

In this case the instance definition for NMaybe became

instance Applicative NMaybe where
  pure = NJust

pure = NJust is a simple definition, but pure x = NJust x is a little more explicit, because its parameters are explicits.

  NJust f <*> m = fmap f m

This definition is not immediate to understand, because the types are implicit. Types are also a form of documentation, so we try to expand the type of each part of the expression, using an invented notation:

assuming Applicative f
  <*> ::: ... -> NMaybe b
  -- we are applying the <*> function, and its result is `NMaybe b`.

    NJust ::: ... -> NMaybe (a -> b)
    -- this is the first argument of `<*>` parent function,
    -- with its explicit type.

      f ::: a -> b
      -- the argument of `NJust` parent function
      -- This is a "terminal" argument because, it is not an application of a function,
      -- and there are no `...` on its type annotation.

    m ::: NMaybe a
    -- this is the second argument.
    -- Note that the type of the complete type of the parent
    -- is derivable substituting to `...` the resulting types of its arguments,
    -- so in this case `NMaybe (a -> b) -> NMaybe a -> NMaybe b`

  =

  fmap ::: ... -> NMaybe b
    f ::: NMaybe (a -> b)
    m ::: NMaybe a
  -- the type is `NMaybe (a -> b) -> NMaybe a -> NMaybe b`
  -- and it is the same of the left definition.

This form is too much verbose, but it contains all the types, and we can understand the meaning of the expression only studying the types.

Homomorphism Law

This is law must be respcted from every instance of Applicative:

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

The law expressed with explicit types is:

assuming Applicative f
  <*> ::: ... -> f b
    pure ::: ... -> f (a -> b)
      g ::: a -> b
    pure ::: ... -> f a
      x ::: a
  =
  pure ::: ... -> f b
    g ::: ... -> b
    x ::: a

Using a pseudo ApplicativeDo notation

do x' <- pure x
   return $ g x'
=
do g' <- pure $ g x
   return g'

Identity

This law says:

pure id <*> v = v

With explicit types:

assuming Applicative f
  (<*>) ::: ... -> f a
    pure id ::: f (a -> a)
    v ::: f a
  =
  v ::: f a

Using a pseudo ApplicativeDo:

do v' <- v
   return $ id v'
=
v

Composition

This law says:

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

Disambiguating the associativity (<*> is left associative) the law is

((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)

The function composition function (.) is the classical

> (.) :: (b -> c) -> (a -> b) -> (a -> c)
> (.) f g = \a -> f (g a)

The form with explicit types is:

assuming Applicative f
  (<*>) ::: ... -> f c
    (<*>) ::: ... -> f (a -> c)
      (<*>) ::: ... -> f ((a -> b) -> a -> c)
        pure (.) ::: f ((b -> c) -> ((a -> b) -> a -> c))
        u ::: f (b -> c)
      v ::: f (a -> b)
    w ::: f a
  =
  <*> ::: ... -> f c
    u ::: f (b -> c)
    <*> ::: ... -> f b
      v ::: f (a -> b)
      w ::: f a

The pseudo ApplicativeDo is:

do u' :: b -> c
   u' <- u

   v' :: a -> b
   v' <- v

   w' :: a
   w' <- w

   return $ (u' . v') w'

=
do
   vw' :: b
   vw' <- do w' :: a
             w' <- w

             v' :: a -> b
             v' <- v

             return $ v' w'

   u' :: b -> c
   u' <- u

   return $ u' vw'

Lesson Learned

A point-free/applicative expression like

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

is hard to understand. Showing the intermediate types helps. Expressing it using a do-notation, with explicit names and types for each part of the expression, and with a top-down semantic helps further.

Nested Domain Specific Languages

This is a example of Hakyll code, for generating a static web site.

hakyllDemo :: IO ()
hakyllDemo = hakyllWith defaultConfiguration $ do
  -- Dot images
  match "images/*.dot" $ do
    route   $ setExtension "png"
    compile $ getResourceLBS >>= traverse (unixFilterLBS "dot" ["-Tpng"])

hakyllWith execute a Rules Monad. Rules is a DSL for generating pages, so apparently it is all very neat and elegant.

match, route, and compile returns Rules, so we have apparently only a series of statements of the Rules monad.

Studying the code there is a little surprise: compile accepts as parameter a Monad of type Compiler, and then it returns a value of type Rules. So the part after compile $ is a DSL written not in the Rules DSL, but in the Compiler DSL. But without studying the type of compiler there are no hints of this.

It is the same for route that accepts a description of routes using Routes DSL, and then return a Rules value, that can be embeded in the main hosting Rules Monad.

Because every Monad is a different DSL with a different semantic, the Haskell syntax should indicate better when we are using a certain type of Monad. So the code can be rewritten in a pseudo Haskell notation like this:

hakyllDemo' :: IO ()
hakyllDemo' = hakyllWith defaultConfiguration (:Rules: do
  match "images/*.dot" $ do
    route   (:Route: setExtension "png"))
    compile (::Compile: getResourceLBS >>= traverse (unixFilterLBS "dot" ["-Tpng"]))
)

Code Golfing

Haskell permits many variants for the same expression:

applicativeCall :: NMaybe Int -> NMaybe Int -> NMaybe Int
applicativeCall x y = pure (+) <*> x <*> y

applicativeCall' :: NMaybe Int -> NMaybe Int -> NMaybe Int
applicativeCall' x y = (+) <$> x <*> y

applicativeCall'' :: NMaybe Int -> NMaybe Int -> NMaybe Int
applicativeCall'' x y = liftA2 (+) x y

applicativeCall''' :: NMaybe Int -> NMaybe Int -> NMaybe Int
applicativeCall''' x y = do
  x' <- x
  y' <- y
  return $ x' + y'

In case of very small code fragments, the do notation seems too much verbose respect a liftA2 variant. But in case of real code, with longer functions, maybe a more predictable do notation should be preferred.

Conclusion

Programs written in Java are usually easy to read and comprehend “in the small”, because Java has a simple and coherent semantic. Maybe in the large they use a lot of complex patterns, and the general architecture of the application is not easy to understand, but in the small every fragment of code is readable.

On the contrary Haskell code can be very hard to comprehend in the small, because every Haskell expression can perform a lot of different things, depending from the context and the implicit types, so it must be studied carefully before understanding its real meaning.

Haskell should use a more uniform syntax and semantic, favouring:

• more explicit types
• do notation with explitic named parts, and clear top-down semantic, instead of clever function compositions
• explicit indication of the Monad/Applicative in which the statements are executed

The ideal code should be readable from left to right, from top to bottom, without thinking too much at the low level details of the language semantic.