Notes on Free monads

综合编程 2013-09-23

The following article is just a few notes on the nature of the Free monad.

> {-# LANGUAGE DeriveFunctor #-}
> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
> {-# LANGUAGE UndecidableInstances #-}
> module FreeMaybe where
> import Control.Monad (join)
> import Control.Monad.Writer.Class

There can be just two values of type Maybe a
: Nothing
and Just a
. Now let’s look at the free monad of Maybe a
, Free Maybe a

> data Free f a = Pure a | Free (f (Free f a))
> instance Functor f => Functor (Free f) where
>     fmap f (Pure a)   = Pure (f a)
>     fmap f (Free ffa) = Free $ fmap (fmap f) ffa
> instance Functor f => Monad (Free f) where
>     return = Pure
>     Pure a >>= f = f a
>     Free ffa >>= f = Free $ fmap (>>= f) ffa
> instance (Show a, Show (f (Free f a))) => Show (Free f a) where
>     showsPrec d (Pure a) = showParen (d > 10) $
>         showString "Pure " . showsPrec 11 a
>     showsPrec d (Free m) = showParen (d > 10) $
>         showString "Free " . showsPrec 11 m

There are four “shapes” that values of Free Maybe a
can take:

Pure a
Free Nothing
Free (Just (Free (Just (... (Free Nothing)))))
Free (Just (Free (Just (... (Free (Pure a))))))

In terms of whether a Free Maybe a
represents an a
or not, Free Maybe a
is equivalent to Maybe a
. However, Maybe a
is right adjoint
to Free Maybe a
, meaning that it forgets the structure of Free Maybe a
– namely, which of the four shapes above the value was, and how many occurences of Free (Just
there were.

Why would you ever use Free Maybe a
? Precisely if you cared about the number of Justs
. Now, say we had a functor that carried other information:

> data Info a = Info { infoExtra :: String, infoData :: a }
>     deriving (Show, Functor)

Then Free Info a
is isomorphic to if infoExtra
had been [String]

> main :: IO ()
> main = do
>     print $ Free (Info "Hello" (Free (Info "World" (Pure "!"))))

Which results in:

>>> main
Free (Info {infoExtra = "Hello",
            infoData = Free (Info {infoExtra = "World", infoData = Pure "!"})})
it :: ()

But now it’s also a Monad
, even though we never defined a Monad
instance for Info

> main :: IO ()
> main = do
>     print $ do
>         x          y          return $ x ++ y

This outputs:

>>> foo
Free (Info {infoExtra = "Hello",
            infoData = Free (Info {infoExtra = "World", infoData = Pure "!!"})})
it :: ()

This works because the Free monad simply accumulates the states of the various functor values, without “combining” them as a real monadic join would have done. Free Info a
has left it up to us to do that joining later.

责编内容by:Lost in Technopolis (源链)。感谢您的支持!


Hexagonal Architecture and Free Monad: Two related... Disclaimer : You do not need to understand Monads to follow this post. This is not a Monad tutorial either, but it might help you getting some...
Overview of free monad in cats Cats library, which helps to write purely functional code, is a quite young project in Scala. It brings many structures and functional constructs...
【函数式】Monads模式初探——Monoids 知乎里有关于 什么是Monad 的问题讨论,而在维基百科中也有关于 Monad的释义 )。作为初次接触到Monads概念,难免会有些晕头转向,也难免会有些畏惧(因为Monads和数学中的范畴论有密切关系),但是Monads又是如此的重要,因为它在函数式编程中实在是应用太广泛了,并且在Scala的标...
Monad_Haskell笔记10 一.从Functor到Monad 从类型来看, Functor 到 Applicative 再到 Monad 是从一般到特殊的递进过程( Monad 是特殊的 Applicative , Applicative 是特殊的 Functor ) ...
Functors, Applicatives, and Monads: You don’... Posted on August 23, 2017 Figuring out how to use the common functional programming typeclassess is not as hard as you would think. The key here is ...