CODEWITHSUNDEEP
haskellrandommonads
Oli
Oli

Reputation: 919

Nested list resulting from do statement

As part of the following code, I have two 'populations' (genetic algorithm). Each population is comprised of many partial solutions. Combining a partial solution from each population produces a whole solution, for which I am attempting to calculate a fitness. The fitness assigned to each individual is initially calculated by matching it with a random partial solution in the opposite population:

generateInitial :: (MonadRandom m)
                => EvolutionParameters
                -> Domain
                -> (Domain -> X -> Y -> Float)
                -> m ([(X, Float)], [(Y, Float)])
generateInitial ep@(EvolutionParameters popSize _ _ _) d fitnessFunction = do
  (xs, ys) <- genPopulations popSize
  (
      initialFitnessXs ep d fitnessFunction (xs, ys)
    , initialFitnessYs ep d fitnessFunction (xs, ys)
  )

-- Returns: m [(X, Float)]
initialFitnessXs ep d@(Domain cs ts _) fnf (xs, ys) = do
  yPicks <- replicateM (length ys) (pick ys)
  return $ map (\(x, y) -> (x, fnf d x y)) $ zip xs yPicks

-- Returns: m [(Y, Float)]
initialFitnessYs ep d@(Domain cs ts _) fnf (xs, ys) = do
  xPicks <- replicateM (length xs) (pick xs)
  return $ map (\(x, y) -> (p, fnf d x y)) $ zip xPicks ys

However, the type this returns from generateInitial is not m ([(Xs, Float)], [(Ys, Float)]) as I would have thought, but nests the lists deeper, resulting in:

• Couldn't match type ‘[(X, Float)]’
                 with ‘(X, Float)’
  Expected type: m ([(X, Float)], [(Y, Float)])
    Actual type: m ([[(X, Float)]], [[(Y, Float)]])

What causes this further nesting, and how could I avoid it?

Upvotes: 1

Views: 80

Answers (2)

trevor cook
trevor cook

Reputation: 1600

  • TL;DR; --- Supply type signatures to solve this type of question. Use type-holes if you are unsure of the signature. Use type signatures on individual terms to help narrow down the problem.

I am going to walk through a technique for using the type system and compiler to help direct debugging. So, although you already have a concise answer that solves your problem, I hope you find this useful as well.

This method relies on using type holes _ (in GHC since version ???) in the type signatures. When GHC encounters such a hole, it will tell what kind of type is expected, allowing you to use the type system to sort out this type (ahem) of problem.

Getting to the error

In order to help, it would be nice to have a minimum (almost) working example. As it stands, a lot is needed to begin compiling the posted code. However, since this is a question about not understanding what type is returned, the technique to getting to that almost working state is similar, so I include it here.

I open my editor (I use Leksah btw) start a new module and paste the given code. First, compilation complaint I address is imports.

import Control.Monad.Random
import Control.Monad(replicateM)

Next, I get an error about mismatched brackets, no doubt by including a return for the last line of generateInitial. Then I see many unrecognized types, so I make some stubs for them, knowing that I may have to refine their definitions as I go. 

data EvolutionParameters = EvolutionParameters PopSize EP2 EP3 EP4
data Domain = Domain Cs Ts D3
data X = X
data Y = Y

I see that EvolutionParameters and Domain constructors take arguments, so I give them some arguments, using the bound variable names when those are specified in a function and just random names otherwise

data PopSize = PopSize
data EP2 = EP2
data EP3 = EP3
data EP4 = EP4
data Cs = Cs
data Ts = Ts
data D3 = D3

Next, we need some missing functions. I define these, using the types GHC tells me.

genPopulations :: PopSize -> m ([X],[Y])
genPopulations = undefined

pick :: t a -> m b
pick = undefined

Addressing the error

The top error now:

 Couldn't match type ‘[(X, Float)]’ with ‘(X, Float)’
      Expected type: m ([(X, Float)], [(Y, Float)])
        Actual type: m ([[(X, Float)]], [[(t0, Float)]])

Awsome! Now to the actual question.

First, I want to see what's going on with the missing signatures, maybe they are not returning what was expected. I specify their types using type holes:

initialFitnessXs :: _ 

initialFitnessYs :: _

Also, there is an unspecified variable p, which I'm assuming is a typo for y. The compiler helps us out. It tells me what was expected in those holes, and allows me to fill in the signatures a bit.

initialFitnessXs :: t -> Domain -> (Domain -> t2 -> t3 -> t1)
                 -> ([t2],[a]) -> [[(t2,t1)]]

initialFitnessYs :: t -> Domain -> (Domain -> t2 -> t3 -> t1)
                 -> ([a],[t3]) -> [[(t3,t1)]]

Hmm, From the comment it seems we were expecting a return of m [(X,Float)], lets force that. Along the way, the compiler directs me to exchange t2 with X, and t3 with a. This leads to the following signatures.

initialFitnessXs :: (MonadRandom m)
                 => t -> Domain -> (Domain -> X -> a -> Float)
                 -> ([X],[a]) -> m [(X,Float)]

initialFitnessYs :: (MonadRandom m)
                 => t -> Domain -> (Domain -> a -> Y -> Float)
                 -> ([a],[Y]) -> m [(Y,Float)]

Next, I return to the source of the actual error, the line which now reads:

return ( initialFitnessXs ep d fitnessFunction (xs, ys)
       , initialFitnessYs ep d fitnessFunction (xs, ys)
       )

I look back at the error and this line. We gave specific signatures for initialFitnessX and initialFitnessY, so although it changed nothing, we can be sure that the problem does not lie in the return of those functions.

Since we already have Chi's answer, what to do should be clear. Pretending I don't know, I use holes again:

return ( initialFitnessXs ep d fitnessFunction (xs, ys) :: _
       , initialFitnessYs ep d fitnessFunction (xs, ys) :: _
       )

And the corresponding error:

• Found type wildcard ‘_’ standing for ‘m1 [(X, Float)]’
  Where: ‘m1’ is a rigid type variable bound by
           the inferred type of
           <expression> :: MonadRandom m1 => m1 [(X, Float)]
           at src/GeneticAlg.hs:41:14

If those terms have those types, then rewriting the generateInitial signature should be. 

generateInitial :: (MonadRandom m)
                => EvolutionParameters
                -> Domain
                -> (Domain -> X -> Y -> Float)
                -> m (m [(X, Float)], m [(Y, Float)])

Success! Well, compilation at least. Hopefully by going through these steps it becomes obvious where the problem is. Resolving the problem is still required, but hopefully you now see one way to use the compiler to your benefit. It helps you compare what you expect with what you wrote. And by asking for signatures of individual terms you can narrow down where that mismatch lies.

If you didn't know what to do from here, you can also use Hoogle.com. For instance, while hoogling m (m a,m a) -> m (a,a) returns nothing, a search for

m (m a) -> m a

returns join from Control.Monad, which might lead you on the track of needing some kind of Monad operation. Of course, that would be not obvious.

Typed Holes Wiki

Upvotes: 1

chi
chi

Reputation: 116139

Let's start here:

-- Returns: m [(X, Float)]
initialFitnessXs ep d@(Domain cs ts _) fnf (xs, ys) = do

(this should really have its own type annotation)

Since m is universally quantified, we can pick m = [] and make initialFitnessXs return [[(X, Float)]].

Then,

  (
      initialFitnessXs ep d fitnessFunction (xs, ys)
    , initialFitnessYs ep d fitnessFunction (xs, ys)
  )

will make a pair of lists-of-lists.

You probably want instead

      x <- initialFitnessXs ep d fitnessFunction (xs, ys)
      y <- initialFitnessYs ep d fitnessFunction (xs, ys)
      return (x,y)

or, using applicative notation,

      (,) <$> initialFitnessXs ep d fitnessFunction (xs, ys)
          <*> initialFitnessYs ep d fitnessFunction (xs, ys)

This will produce all the (x,y) combinations. Maybe you want to zip those list instead, but it's hard to tell for me.

Upvotes: 1

Related Questions