Friday, October 14, 2016

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.

No comments:

Post a Comment