Ambiguous type variables

17 Mar 2014

      I need help with an "ambiguous type variables" error.

My problem domain is backtracking search to construct musical phrases by
choosing notes that fulfill as many simultaneous criteria as possible. At
the beginning, I always know that I need to choose N notes, and they will
be chosen in a particular order, one at a time. I don't need to worry about
cycles, therefore. There is a way of calculating a "goodness" score, given
a series of the first M notes (where M ranges from 2 to N). I'm looking for
the solution with the best score. Because my problem may be too large to do
a complete search, I think it would be great to be able to do a combination
of breadth and depth searching... sort of like a chess program that
searches X moves ahead but not all the way to the end of the game. So I
start with 1 note and do a complete search on all partial solutions with X
notes looking for the best score (dealing with ties somehow, not sure yet
how), then take the first note from the best solution, then do a complete
search on all partial solutions with 2 to X+1 notes, and so forth until
X=N.

I have in mind many possible ways of representing phrases and "moves," so I
wanted to implement my basic algorithm in a class. I need three data types:

- "the data" : a representation of a solution with from 1 to N choices
applied
- "a choice" : a representation of a choice of note at a particular point
in the phrase
- "memo" : a way of tracking the best partial solution(s) found during this
phase of the search

Here's my code so far

In the following the type variable "d" is "the data", "c" is "a choice" and
"memo" is a memo.

The error is

Ambiguous type variables 'd0', 'c0' in the constraint:
  (Bt d0 c0 memo) arising from a use of 'newMemo'

class Bt d c memo | d -> c, d -> memo where

  -- a solution state is checked against the best solutions stored in
  -- the memo, and possibly replaces or augments the list of best
  -- solutions.
  updateMemo :: memo -> d -> memo
  newMemo :: memo
  pickBest :: Int -> memo -> d
  isSolution :: d -> Bool
  isSolution x = stateSize x == solutionSize x
  -- number of choices applied so far
  stateSize :: d -> Int
  -- note that data of type 'd' includes an indication of what the
  -- final solution size is, something put there when d is initialized
  solutionSize :: d -> Int
  enumerateChoices :: d -> [c]  -- choices available at this point in the
                                -- construction of the state
  -- compute a goodness score
  scoreState :: d -> Double
  applyChoice :: d -> c -> d
  -- note that this is only partially implemented. Never mind that
  -- it's not complete or correct, I'm still trying to understand
  -- where my error arises.
  --
  -- What is will eventually do: completely searches N levels deep
  -- before picking best score, then takes best partial solution,
  -- backs up N-1 levels and does another complete search,
  -- etc. finally displays solution with best score.
  limBacktrack :: Int -> d -> memo
  limBacktrack n d = limBacktrack' n newMemo d

  limBacktrack' :: Int -> memo -> d -> memo
  limBacktrack' nGoal memo d
    | stateSize d == nGoal = updateMemo memo d
    | otherwise = foldl g memo (enumerateChoices d)
    where
      --  g :: memo -> choice -> memo
      g memo choice = limBacktrack' nGoal memo (applyChoice d choice)

The error is

Ambiguous type variables 'd0', 'c0' in the constraint:
  (Bt d0 c0 memo) arising from a use of 'newMemo'

Dennis Raddle

Brent Yorgey

Kim-Ee Yeoh

Dennis Raddle

Dennis Raddle

Kim-Ee Yeoh

David McBride

tags

participants (4)