Efficient way to code "(symbol,multiplicity)-counting" - how?

[Mark Phillips]

Hi,

I am new to Haskell and am having some difficulty with the following
problem.

Suppose I have a list of "symbols", except that each symbol is
paired with a "multiplicity".  Ie, we have a list of type [(a,Int)].

I want to use these symbols to "count".  Let me explain what I mean
by count with the following example.

Suppose we have symbol list [(x,1),(y,2),(z,1)].  This tells us that
* we have three symbols, namely x, y and z
* the symbols are ordered, namely x < y < z
* with any "counting figure" the symbol x may appear at most once, the
   symbol y at most twice and the symbol z at most once (a "counting
   figure" is just a list of symbols, these symbols forming the "digits")
* any "counting figure" will have between 0 and 1+2+1=4 "digits"
   (symbols)
* the "counting figures" are ordered; the fewer the number of "digits"
   the "smaller" the figure; for figures with the same number of digits
   ordering is based on the symbol ordering, the left-most digit being
   "most significant", second-left being "second-most significant" and
   so on.

We "count" as follows:
[] [x] [y] [z] [x,y] [x,z] [y,x] [y,y] [y,z] [z,x] [z,y] [x,y,y] [x,y,z]
[x,z,y] [y,x,y] [y,x,z] [y,y,x] [y,y,z] [y,z,x] [y,z,y] [z,x,y] [z,y,x]
[z,y,y] [x,y,y,z] [x,y,z,y] [x,z,y,y] [y,x,y,z] [y,x,z,y] [y,y,x,z]
[y,y,z,x] [y,z,x,y] [y,z,y,x] [z,x,y,y] [z,y,x,y] [z,y,y,x]
and then start back at the beginning again (with []).

I want to define a function
next :: [(a,Int)] -> [a] -> [a]

which finds the next list in the the "counting sequence".  So
for example we should get

next [(x,1),(y,2),(z,1)] [] == [x]
next [(x,1),(y,2),(z,1)] [z,y] == [x,y,y]
next [(x,1),(y,2),(z,1)] [x,y,y,z] == [x,y,z,y]
next [(x,1),(y,2),(z,1)] [z,y,y,x] == []
etc

My question is, what is the best way to code this in Haskell?  Can
it be done efficiently?

Also, is my representation of symbols and multiplicities the best
method?  Would I be better to represent them as two lists say,
and in reverse order say: ie [z,y,x] and [1,2,1].  Or is there
another better way to frame the whole problem?

Cheers,

Mark.

-- 
Dr Mark H Phillips
Research Analyst (Mathematician)

AUSTRICS - Smarter Scheduling Solutions - www.austrics.com

Level 2, 50 Pirie Street, Adelaide SA 5000, Australia
Phone +61 8 8226 9850
Fax   +61 8 8231 4821
Email mark@austrics.com.au