На основе англоязычной статьи Gabriel Gonzalez.

Предположим, что мы написали простейшую компьютерную программу, делающую некий ввод-вывод (т.е. имеющую сайд-эффекты):

module Main where
import           Data.Char          (toUpper)
import           System.Exit        (exitSuccess)

main = do x <- getLine
          putStrLn (map toUpper x)
          putStrLn "Finished"
          exitSuccess

Всё бы ничего, но данный код смешивает “чистую” логику (не имеющую сторонних эффектов чистую трансформацию строки в верхний регистр: строка -> СТРОКА) и “грязный” ввод-вывод с терминала (имеющий сторонние эффекты вроде ожидания клавиатурного ввода, разрыв терминальной линии и т.п.). Можем ли мы изолировать и сконцентрировать весь нечистый код в одном месте, оставив всю остальную логику программы чистой, не имеющей сайд-эффектов, а значит легко осмысляемой?

Один из интересных способов сделать это состоит в использовании свободной монады (free monad) функтора – монады, которая однозначно (уникально) определяется данным функтором (с точностью до изоморфизма). В некотором смысле, свободная монада – это монада с наименьшими ограничениями (на монадическую структуру), которую мы можем получить для данного функтора. Для понимания можно также использовать интуицию дерева, вершины которого помечены конструкторами функториального типа.

Свободные монады позволяют нам легко декомпозить нашу программу в её чистую репрезентацию и нечистый интерпретатор. Функториальный тип, таким образом, описывает F-алгебру, а интерпретатор знает как её вычислять в нечистом Мире сайд-эффектов (например, в IO-монаде). Логика программы пишется этой функториальной алгеброй, а затем исследуется, тестируется, хранится, передаётся по сети, доказывается и, наконец, выполняется интерпретатором.

Перепишем нашу программку.

Функториальная алгебра⌗

Представим все нужные нам операции ввода-вывода типом TeletypeF с тривиальной реализацией тайпкласса Functor:

module Main where
import           Control.Monad.Free
import           Data.Char          (toUpper)
import           System.Exit        (exitSuccess)

data TeletypeF x
  = PutStrLn String x
  | GetLine (String -> x)
  | ExitSuccess

instance Functor TeletypeF where
  fmap f (PutStrLn str x) = PutStrLn str (f x)
  fmap f (GetLine k)      = GetLine (f . k)
  fmap f ExitSuccess      = ExitSuccess

type Teletype = Free TeletypeF


putStrLn' :: String -> Teletype ()
putStrLn' str = liftF $ PutStrLn str ()

getLine' :: Teletype String
getLine' = liftF (GetLine id)

exitSuccess' :: Teletype ()
exitSuccess' = liftF ExitSuccess

Мы искусственно “поддерживаем” в алгебре тип последнего вычисления (параметр x). Для унифицированного интерфейса к свободным монадам используем пакет free и тип Free f a (“The Free Monad for a Functor f”):

data Free f a = Pure a | Free (f (Free f a))

В монадических синонимах операций ввода-вывода используем функцию liftF для лифтинга, т.е. “повышения” значений нашего функториального типа TeletypeF до значений нового монадического типа Teletype. Чисто механический код.

Интерпретатор⌗

А вот наш “нечистый” интерпретатор, рекурсивно вычисляющий (разрушающий) значения нашей свободной монады Teletype в значение в контексте IO:

run :: Teletype r -> IO r
run (Pure r)                = return r
run (Free (PutStrLn str x)) = putStrLn str >> run x
run (Free (GetLine k))      = getLine >>= run . k
run (Free ExitSuccess)      = exitSuccess

Чистая логика программы⌗

Наконец, теперь мы можем выразить логику нашей программы в “чистом” виде. Все сторонние эффекты (I/O) полностью изолированы в “грязном” коде интерпретатора run!

echo :: Teletype ()
echo = do
  str <- getLine'
  putStrLn' (map toUpper str)
  putStrLn' "Finished"
  exitSuccess'

Запустить программу - значит произвести вычисления в функториальной алгебре:

main :: IO ()
main =
  run echo