How can I implement Applicative on my list, modelling non-determinism?

Question

I was practicing Functor / Applicative Functors + Monads in Haskell when I came across this assignment:

4) You have seen how a Monad instance can be used to handle things that can fail. Another use case for a Monad is dealing with non-determinism. The simplest way to model non-deterministic computation is using a list. Think of the list as holding all possible results of some computation. When you use the well known map function, the function you are applying produces the outputs for all the possible inputs. [...]

Define your list type like so:
data MyList a = Cons a (MyList a) | Nil deriving Show
(a) Make your list an instance of Functor.
(b) Make your list an instance of Applicative.
(c) Make your list an instance of Monad.

I am having some trouble with it. This is my current solution:

instance Functor MyList where
    fmap f (Nil) = Nil
    fmap f (Cons item other) = (Cons (f item) (fmap f other))

instance Applicative MyList where
    pure item = (Cons item Nil)
    Nil <*> _ = Nil
    _ <*> Nil = Nil
    (Cons f item) <*> something = (fmap f something) ++ (item <*> something)

Problem is with (item <*> something). With a list the ++ operator would have made this possible but I even made a function that had a ++ operator but this method still does not work. How can I implement the Applicative for this type?

This is my ++ implementation:

(++) :: (MyList a) -> a -> (MyList a)
(++) Nil item = (Cons item Nil)
(++) (Cons val other) item = (Cons val (other ++ item))

This is the error I get:

Couldn't match expected type ‘a -> b’
            with actual type ‘MyList (a -> b)’
Relevant bindings include
  something :: MyList a (bound at Assignment_6.hs:13:23)
  item :: MyList (a -> b) (bound at Assignment_6.hs:13:13)
  f :: a -> b (bound at Assignment_6.hs:13:11)
  (<*>) :: MyList (a -> b) -> MyList a -> MyList b
    (bound at Assignment_6.hs:11:5)
In the second argument of ‘(++)’, namely ‘item’
In the first argument of ‘(<*>)’, namely
  ‘(fmap f something) ++ item’

It should actually work with a custom ++ operator (which BTW would best be realised as a Monoid instance). What error are you getting? — leftaroundabout
If you don't get a compiler error, what is your expected behaviour, and what behaviour do you observe? — Zeta
(++) :: (MyList a) -> a -> (MyList a) (++) Nil item = (Cons item Nil) (++) (Cons val other) item = (Cons val (other ++ item)) (This is my custom ++ operator) — S. Salman

Daniel Wagner Daniel Wagner · Accepted Answer · 2016-02-26T19:45:52

Compare the following two types:

(Prelude.++) :: []     a -> [] a -> []     a
(George.++)  :: MyList a ->    a -> MyList a

Can you spot the problem?

How can I implement Applicative on my list, modelling non-determinism?

1 Answers