29

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.

1
  • 3
    I can't suggest exercises, but you could look at applicative functors that aren't monads (a crucial question seems to be "why design an applicative functor when it is less powerful than a monad?"). The multi error applicative (in Paterson and McBride) is one, there are also Doaitse Swierstra's parsers, an animation one Active in Andy Gill and Kevin Matledge's Chalkboard plus I think Andy Gill and colleagues' Kansas Lava is based on an applicative functor. Commented Apr 20, 2012 at 6:47

4 Answers 4

22

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.

1
  • I agree that these are great exercises. They could be improved for contemporary Haskell with a few tweaks: * the use roll-your-own sum-of-product generics, which is part of the point of the exercise, but we now have GHC Generics. It would be ideal to re-render this exercise using that, errr, idiom. * The Triple / Zone abstraction is great for the exercise but makes it harder to model Sudoku rules where there are node interdependencies (such as noDups).
    – jrp
    Commented Jun 22, 2019 at 18:42
12

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
4
  • I'm curious--can you give some common or at least reasonable examples that you can't parse with an applicative functor but can with a monad? Commented Apr 20, 2012 at 4:54
  • 7
    @TikhonJelvis, formally they are equivalent in power, at least over a finite alphabet, but in kind of a pathological way (they both support infinite grammars). But a good example of where you would (reasonably) need a monad would be if you had a language which could define new grammatical constructs that should be taken into account later in the parse. Applicative can't change its structure based on its content, Monad can.
    – luqui
    Commented Apr 20, 2012 at 5:01
  • +1 When I saw the title, I also immediately thought of Parsec. It's a great way to practice solving interesting, nontrivial, yet simple problems.
    – Dan Burton
    Commented Apr 20, 2012 at 5:47
  • 3
    Imagine parsing a language spec followed by something written in that language. You can't easily to that with applicative, but with a monad it's trivial. Commented Apr 20, 2012 at 9:37
5

Check out the Typeclassopedia. It comes with a good explanation from the ground up and some exercises along the way.

4

For example: Applicative Functors

1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.