Haskell function using Applicative and Functor

Question

I have a practice question, where I'm given a function:

sequence :: Applicative f => [f a] -> f[a]
sequence = foldr (_hole (:)) (pure [])

and the question says:

"What type is required for the function that needs to be placed at 
_hole in the following expression? Also give a definition for the 
expression using  and <$> and <*>".

I'm having issue understanding what the question is asking. So for what I've tried, i assume that I'm required to specify the operator since it's using foldr so i assume its something like sequence = foldr((+) (:)) (pure[]).

Then for the definition of the expression, i wrote something like:

sequence :: <*> f => [f a] -> f[a]
sequence = foldr <$> pure []

I'm pretty sure I'm not 100% correct so would appreciate some help on this on any corrections.

Answer 1

Let's do it step by step, gradually discovering the types of the entities involved in our definition. We are given

sequence :: Applicative f => [f a] -> f [a]               --  (1)
sequence = foldr (_hole (:)) (pure [])                    --  (2)

so that sequence = mksequence g for some g:

mksequence g xs = foldr (g (:)) (pure []) xs              --  (3)

mksequence g [a,b,...,n] = r where                        --  (4)
    r = g (:) a $ g (:) b $ ... $ g (:) n (pure [])       --  (5)

mksequence g [a] = g (:) a (pure [])                      --  (6)

mksequence g []  = pure []                                --  (7)

-- [a,b,...,n] :: [f a]                     <-(4,1)       --  (8)
--  a,b,...,n  ::  f a                      <-(8)         --  (9)
--  r          :: f [a]                     <-(4,1)       --  (10)
-- pure []     :: f [a]                     <-(7,1)       --  (11)
-- g (:)       :: f a -> f [a] -> f [a]     <-(6,8,11,1)

Finally, we've found the type of g (:)! Compare it with

(<*>)  :: f (a -> t) -> f a -> f t          , _A :: f (a -> t)
(_A <*> _C)                 :: f t          , _C :: f  a
(_B <*> _C)                 :: f (t -> s)   , _B :: f (a -> (t -> s))
((_B <*> _C) <*> _D)        :: f       s    , _D :: f        t

So that we have,

\ _B _C _D -> ((_B <*> _C) <*> _D)  
          :: f (a -> (t  ->  s)) -> f a -> f  t  -> f  s
   g ((:) ::    a -> [a] -> [a]) :: f a -> f [a] -> f [a]

The signatures nearly match! With just a little nudge we have

g (:) = (\ _B _C _D -> ((_B <*> _C) <*> _D)) (pure (:))

and so, generalizing,

g  f2  fa  ft  =  pure f2  <*>  fa  <*>  ft

because (<*>) associates to the left. Re-checking the types,

g  f2  fa  ft  =  pure f2  <*>  fa  <*>  ft
               =       f2  <$>  fa  <*>  ft

-- fa                 :: f a
-- f2                 ::   a -> t -> s
-- f2 <$> fa          :: f     (t -> s)
-- ft                 :: f      t
-- (f2 <$> fa) <*> ft :: f           s

In fact this definition already exists, and is named liftA2 -- for "lifting" a binary function (f2) into an applicative "context" (f):

           f2 ::   a ->   t ->   s
    liftA2 f2 :: f a -> f t -> f s

Answer 2

The exercise wants you to assume that some value _hole is defined somewhere, and that the code above type checks. Then, the goal is to determine what would be the type of that _hole. Then, it would ask a possible definition for _hole.

For instance, if we were given

foo :: Int
foo = 3 + _hole

the answer should be _hole :: Int, since that's what we need to make the code above to work. For the definition _hole = 2 is OK.

Instead, in

foo :: Int -> Bool
foo = const _hole "hello" True

then we need _hole :: Bool -> Int -> Bool and for instance _hole = \b i -> b.

Your own code is more complex, so it's better to write down all the steps:

sequence :: Applicative f => [f a] -> f[a]
sequence = foldr (_hole (:)) (pure [])

Here foldr is used, which (on lists) has type

foldr :: (b -> c -> c) -> c -> [b] -> c

To type check, the arguments must have type

_hole (:) :: b -> c -> c
pure [] :: c

the result of foldr, being called with only two arguments is

sequence :: [b] -> c

since this must match the type of sequence above, we get

[b] = [f a]
c = f [a]

Hence, b = f a and

_hole (:) :: f a -> f [a] -> f [a]
pure [] :: f [a]

The pure [] part type checks as it is. For the other, we need

_hole :: (type of (:)) -> f a -> f [a] -> f [a]

i.e. since (:) :: d -> [d] -> [d] for any d, we get

_hole :: (d -> [d] -> [d]) -> f a -> f [a] -> f [a]

where d can be picked arbitrarily. It is "natural", though, to pick d=a, so that we get

_hole :: (a -> [a] -> [a]) -> f a -> f [a] -> f [a]

Now, we need to write a definition _hole f x y = ?? in terms of <$> and <*>. Essentially, we need to re-implement liftA2 from the library. You should now be able to solve this last part.