Where to find programming exercises for applicative functors?
-
01-06-2021 - |
Question
I've been reading about applicative functors, notably in the Functional Pearl by McBride and Paterson. But I'd like to solidify my understanding by doing some exercises. I'd prefer programming exercises but proof exercises are OK too. What exercises will help me learn to program effectively with applicative functors?
Individual exercises are OK as are pointers to exercises listed elsewhere.
Solution
It seems amusing to post some questions as an answer. This is a fun one, on the interplay between Applicative
and Traversable
, based on sudoku.
(1) Consider
data Triple a = Tr a a a
Construct
instance Applicative Triple
instance Traversable Triple
so that the Applicative
instance does "vectorization" and the Traversable
instance works left-to-right. Don't forget to construct a suitable Functor
instance: check that you can extract this from either of the Applicative
or the Traversable
instance. You may find
newtype I x = I {unI :: x}
useful for the latter.
(2) Consider
newtype (:.) f g x = Comp {comp :: f (g x)}
Show that
instance (Applicative f, Applicative g) => Applicative (f :. g)
instance (Traversable f, Traversable g) => Traversable (f :. g)
Now define
type Zone = Triple :. Triple
Suppose we represent a Board
as a vertical zone of horizontal zones
type Board = Zone :. Zone
Show how to rearrange it as a horizontal zone of vertical zones, and as a square of squares, using the functionality of traverse
.
(3) Consider
newtype Parse x = Parser {parse :: String -> [(x, String)]} deriving Monoid
or some other suitable construction (noting that the library Monoid
behaviour for |Maybe| is inappropriate). Construct
instance Applicative Parse
instance Alternative Parse -- just follow the `Monoid`
and implement
ch :: (Char -> Bool) -> Parse Char
which consumes and delivers a character if it is accepted by a given predicate.
(4) Implement a parser which consumes any amount of whitespace, followed by a single digit (0 represents blanks)
square :: Parse Int
Use pure
and traverse
to construct
board :: Parse (Board Int)
(5) Consider the constant functors
newtype K a x = K {unK :: a}
and construct
instance Monoid a => Applicative (K a)
then use traverse
to implement
crush :: (Traversable f, Monoid b) => (a -> b) -> f a -> b
Construct newtype
wrappers for Bool
expressing its conjunctive and disjunctive monoid structures. Use crush
to implement versions of any
and all
which work for any Traversable
functor.
(6) Implement
duplicates :: (Traversable f, Eq a) => f a -> [a]
computing the list of values which occur more than once. (Not completely trivial.) (There's a lovely way to do this using differential calculus, but that's another story.)
(7) Implement
complete :: Board Int -> Bool
ok :: Board Int -> Bool
which check if a board is (1) full only of digits in [1..9] and (2) devoid of duplicates in any row, column or box.
OTHER TIPS
A great way to practice is to use Parsec
in an applicative rather than a monadic style. Most parsers are purely applicative, so you shouldn't need to use do
notation ever.
Eg. for expressions:
import qualified Text.Parsec as P
import qualified Text.Parsec.Token as P
import Control.Applicative
data Expr = Number Int | Plus Expr Expr
lex = P.makeTokenParser ... -- language config
expr = number <|> plus
where
number = Number <$> P.integer lex
plus = Plus <$> number <* P.symbol lex "+" <*> expr
Check out the Typeclassopedia. It comes with a good explanation from the ground up and some exercises along the way.
For example: Applicative Functors