Efficient way to code "(symbol,multiplicity)-counting" - how?
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
This looked like a fun problem. Here's a solution and some comments on how I went about solving it. -- Alastair Reid Reid Consulting (UK) Ltd
import List( nub ) import Maybe( fromMaybe, fromJust )
It seems like your enumerations have two constraints: 1) They have to obey the multiplicity constraint. 2) They have to obey the ordering constraint. Let's tackle them one at a time: [Metanote: a common way to write Haskell programs is sort of bottom up: identify the core concepts, build up a library of useful code for representing and manipulating those concepts and try to explore a little of the algebraic properties of the concepts, then look to see if this makes the problem easy yet.] An alternative representation would be [a] where counts are represented by repetition. Not clear which is better.
type Multiplicity a = [(a,Int)]
For the sake of testing, here's a sample multiplicity:
m1 :: Multiplicity Char m1 = [('x',1),('y',2),('z',1)]
Extract a multiplicity from a list with duplicates
counts :: Eq a => [a] -> Multiplicity a counts as = [ (a, length (filter (==a) as)) | a <- List.nub as ]
Extract count from a multiplicity Use 0 if not present rather than raising error because it saves having to litter callers with guard code.
count :: Eq a => Multiplicity a -> a -> Int count m a = fromMaybe 0 (lookup a m)
Ordering on two multiplicities: when is one <= another?
le :: Eq a => Multiplicity a -> Multiplicity a -> Bool m1 `le` m2 = and [ n <= count m2 a | (a,n) <- m1 ]
and, of course, equality:
eq :: Eq a => Multiplicity a -> Multiplicity a -> Bool eq m1 m2 = m1 `le` m2 && m2 `le` m1
Finally, we can check that a list satisfies the multiplicity constraint.
countok :: Eq a => Multiplicity a -> [a] -> Bool countok m as = counts as `le` m
Now onto the ordering constraint. If I replace your symbols with digits and ignore the multiplicity constraint, the enumerations would look something like this. 0, 1, 2, 10, 11, 12, 20, 21, 22, ... In other words, I can find the next element in a list just by incrementing the list elements. Let's consider that first (since it is easier). A number is a list of digits _in reverse order_
type Digit = Int type Number = [Digit]
Debugging/checking is easier if the numbers look like numbers so let's define some printing functions:
showNumber :: Number -> String showNumber = concat . map show . reverse
showNumbers :: [Number] -> String showNumbers = concat . map (++"\n") . map showNumber
Counting to infinity:
incN :: Number -> Number incN (9:ds) = 0 : incN ds incN (d:ds) = d+1 : ds incN [] = incN [0]
We can enumerate all numbers by iterating:
numbers :: [Number] numbers = iterate incN [0]
Printing this on the screen, we can easily see that we got it right.
testN = putStr $ showNumbers (take 110 numbers)
Now let's tackle the real problem. Lists of symbols are called figures. As before, we use reversed lists
type Figure a = [a]
showFigure :: Show a => Figure a -> String showFigure = concat . map show . reverse
showFigures :: Show a => [Figure a] -> String showFigures = concat . map (++"\n") . map showFigure
Symbols are elements of a methematical structure that have a first element, a final element and an increment function. [I'm making this a 1st class structure because I want to be able to share the symbols structure between multiple invocations of next. I will use this structure a lot like the way I would a typeclass - except that I will explicitly create my own instance.]
data Symbols a = Symbols{ first :: a, final :: a, inc :: a -> a }
We can turn a multiplicity into a Symbols structure quite easily
mkSymbols :: Eq a => Multiplicity a -> Symbols a mkSymbols m = Symbols{ first = fst (head m), final = fst (last m), inc = nxt m }
The nxt function is a bit inefficient. We're hampered here by polymorphism: if all you can do is an equality test, you can't do better than a linear time lookup. A binary tree could be used instead of the zip if we had an Ord instance; an array if we had an Ix instance.
nxt :: Eq a => Multiplicity a -> a -> a nxt m a = fromJust (lookup a (zip m' (tail m'))) where m' = map fst m
And now we copy the incN function and tweak it to use the Symbols structure:
incF :: Eq a => Symbols a -> Figure a -> Figure a incF s (d:ds) | d == final s = first s : incF s ds incF s (d:ds) = (inc s) d : ds incF s [] = [first s] -- slight difference here
We make one slight change in the process. With numbers, we treat the white space at the left of a number as an infinite sequence of 0's. That's why we wrote: incN [] = incN [0] We don't do that here. We can enumerate all figures by iterating:
figures :: Eq a => Symbols a -> [Figure a] figures s = iterate (incF s) []
Printing this on the screen, we can easily see that we got it right.
testF f = putStr $ showFigures (take 110 f)
Now let's pop up a level and see if we have enough bits to solve the whole problem. So far I've ignored the importance of going back to the start when you reach the maximum multiplicity. For this we need the maximum figure of a given multiplicity:
maxF :: Multiplicity a -> Figure a maxF [] = [] maxF ((a,n):m) = replicate n a ++ maxF m
[This takes both a multiplicity and a symbols structure as argument because we want efficient access to both.]
incF2 :: Eq a => Multiplicity a -> Symbols a -> Figure a -> Figure a incF2 m s f | f == maxF m = [] incF2 m s f | otherwise = incF s f
testF2 m = testF (iterate (incF2 m (mkSymbols m)) [])
We've also ignored the importance of the multiplicity constraint. We can enforce this by discarding any result of incF2 which fails the constraint.
incF3 :: Eq a => Multiplicity a -> Symbols a -> Figure a -> Figure a incF3 m s f = head (filter (countok m) (tail (iterate (incF2 m s) f)))
testF3 m = testF (iterate (incF3 m (mkSymbols m)) [])
This works but it seems a bit inefficient to do a linear search for the next valid successor. I have an inkling of how to do that but I'll leave it for someone else. Mark Phillips <mark@austrics.com.au> writes: | 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?
Hi Alastair, Thanks for your email! Sorry about the slowness of my reply, but it's taken me quite some time to work through your email because many of the syntax and concepts are new to me. Yours has been a most informative email. I think I now understand most of your email, but it has raised in my mind a number of questions which I will now ask.
An alternative representation would be [a] where counts are represented by repetition. Not clear which is better.
Yes, I had wondered. In any case, it's not too hard to convert between the two forms: (rep stands for repetitions) multToRep :: [(a,Int)] -> [a] multToRep [] = [] multToRep ((aa,1):as) = aa : multToRep as multToRep ((aa,ab):as) = aa : multToRep ((aa,ab-1):as) repToMult :: Eq a => [a] -> [(a,Int)] repToMult [] = [] repToMult (a:as) = (a,b+1) : repToMult cs where (b,cs) = peel a as peel :: Eq a => a -> [a] -> (Int,[a]) peel a [] = (0,[]) peel a (b:bs) = if (a==b) then (c+1,ds) else (0,b:bs) where (c,ds) = peel a bs Anyway, probably the [(a,Int)] is the best. It is the shortest representation (except where multiplicities are mostly 1), and the multToRep function is simpler (I think) than repToMult.
type Multiplicity a = [(a,Int)]
Can we say "Multiplicity a" *is* "[(a,Int)]", or do we say "Multiplicity a" *is_a_distinct_yet_identical_copy_of* "[(a,Int)]"?
counts :: Eq a => [a] -> Multiplicity a counts as = [ (a, length (filter (==a) as)) | a <- List.nub as ]
Does it make a difference whether you write "filter (==a) as" or "filter (a==) as"? What do you think of the following as an alternative definition of counts? counts [] = [] counts (a:as) = (a,b+1) : counts cs where (b,cs)=strip a as strip :: Eq a => a -> [a] -> (Int,[a]) strip a [] = (0,[]) strip a (b:bs) = if (a==b) then (c+1,ds) else (c,b:ds) where (c,ds) = strip a bs I am trying to work out how to code fast and memory efficient haskell. Is the above a good approach?
Symbols are elements of a methematical structure that have a first element, a final element and an increment function.
[I'm making this a 1st class structure because I want to be able to share the symbols structure between multiple invocations of next. I will use this structure a lot like the way I would a typeclass - except that I will explicitly create my own instance.]
I'm a little unsure about what you are saying here. Am I right in thinking a 1st class structure is one that may be thought of as data? What is the alternative here? Are you saying that by defining such a structure, you can calculate the concepts once, and then pass them around, rather than calculating them at each step of the process?
data Symbols a = Symbols{ first :: a, final :: a, inc :: a -> a }
The nxt function is a bit inefficient. We're hampered here by polymorphism: if all you can do is an equality test, you can't do better than a linear time lookup. A binary tree could be used instead of the zip if we had an Ord instance; an array if we had an Ix instance.
But we can assume that the "digits" are ordered, this ordering given by the order in which they occur in the multiplicity. Is there a way of using this to make the digits an Ord instance? And if so, how do you do the binary tree?
testF f = putStr $ showFigures (take 110 f)
What does the "$" do in the above?
We've also ignored the importance of the multiplicity constraint. We can enforce this by discarding any result of incF2 which fails the constraint.
incF3 :: Eq a => Multiplicity a -> Symbols a -> Figure a -> Figure a incF3 m s f = head (filter (countok m) (tail (iterate (incF2 m s) f)))
The filter combined with a check that the multiplicity constraint is satisfied will work, but how efficient is it? I am guessing that it will depend how many are rejected. If most are rejected then it's probably inefficient, but if only a few are, then it's the best way. Are there any other pros and cons with this approach? I am thinking that maybe a more efficient algorithm, in the case where lots are expected to be rejected in the above, would be one involving a dynamically changing multiplicity. Ie, when a symbol is chosen, the multiplicity is modified to reduce the corresponding multiplicity by 1. Of course, maybe I'm just thinking too much in the imperative framework still --- where the multiplicity would be represented as an array of values that could be reassigned. The problem seems to be that lazy lists are not good when you want to do "random access updates", which is roughly what we want to do with a multiplicity list. Are there well known Haskell solutions to this kind of issue? By the way, the reason I wanted my counting to wrap back to "[]" after getting to the maximum figure, is so the function "next" would always work. But your email suggested to me an alternative solution. I could just use the "Maybe" data type! Ie, trying to do a next on the maximum figure just gives you the Maybe "Nothing". Thanks again for your very informative email! 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
type Multiplicity a = [(a,Int)]
Can we say "Multiplicity a" *is* "[(a,Int)]", or do we say "Multiplicity a" *is_a_distinct_yet_identical_copy_of* "[(a,Int)]"?
Type synonyms are like typedef or #define in C: they create a fresh name for an already existing type. Use newtype if you want to create fresh types.
Does it make a difference whether you write "filter (==a) as" or "filter (a==) as"?
The two versions of the predicate translate to: (== a) ~~~> flip (==) a == \ x -> (x == a) (a ==) ~~~> (==) a == \ x -> (a == x) These are equivalent since any sensible instance of == is reflexive. There's probably a marginal gain in efficiency from using (a ==) when the compiler doesn't inline the definition of filter and no gain at all when it does.
counts :: Eq a => [a] -> Multiplicity a counts as = [ (a, length (filter (==a) as)) | a <- List.nub as ]
What do you think of the following as an alternative definition of counts?
counts [] = [] counts (a:as) = (a,b+1) : counts cs where (b,cs)=strip a as
strip :: Eq a => a -> [a] -> (Int,[a]) strip a [] = (0,[]) strip a (b:bs) = if (a==b) then (c+1,ds) else (c,b:ds) where (c,ds) = strip a bs
I am trying to work out how to code fast and memory efficient haskell. Is the above a good approach?
Note that you're writing a slightly different function - the functions give different results for: counts ['a','b','a','a'] but that difference probably won't affect your code. As for coding style, if you care about performance this much, you should use GHC. GHC should do a pretty good job at optimizing code like this (which is a slightly more concise version of yours). counts [] = [] counts (a:as) = (a, length xs):counts ys where (xs,ys) = takeWhile (a==) as
Symbols are elements of a methematical structure that have a first element, a final element and an increment function.
[I'm making this a 1st class structure because I want to be able to share the symbols structure between multiple invocations of next. I will use this structure a lot like the way I would a typeclass - except that I will explicitly create my own instance.]
I'm a little unsure about what you are saying here. Am I right in thinking a 1st class structure is one that may be thought of as data?
Yes, that's what I meant.
What is the alternative here? Are you saying that by defining such a structure, you can calculate the concepts once, and then pass them around, rather than calculating them at each step of the process?
Yes. I could have searched for the last element in the list each time round the loop (erm, I mean 'on each recursive call to incF') but that would have been horribly inefficient. Or I could have searched for the last element in the list once for each time incF was non-recursively invoked: incF ms x = incF' x where first = ... last = ... incF' x = ... incF'... but that would be a bit inefficient too.
The nxt function is a bit inefficient. We're hampered here by polymorphism: if all you can do is an equality test, you can't do better than a linear time lookup. A binary tree could be used instead of the zip if we had an Ord instance; an array if we had an Ix instance.
But we can assume that the "digits" are ordered, this ordering given by the order in which they occur in the multiplicity. Is there a way of using this to make the digits an Ord instance? And if so, how do you do the binary tree?
-- http://www.haskell.org/ghc/docs/latest/set/finitemap.html import FiniteMap mkTree :: Ord a => [(a,b)] -> FiniteMap a b mkTree abs = listToFM abs getTree :: Ord a => a -> FiniteMap a b -> -> Maybe b getTree a t = lookupFM t a Arrays (http://www.haskell.org/onlinelibrary/array.html) would work if you can _efficiently_ turn your index values into Ints but if you can do that, you probably have an Enum instance http://www.haskell.org/onlinereport/basic.html http://www.haskell.org/onlinereport/standard-prelude.html#$tEnum
testF f = putStr $ showFigures (take 110 f)
What does the "$" do in the above?
In http://www.haskell.org/onlinereport/standard-prelude.html#$v$D you'll se it has this pointless-looking definition: f $ x = f x Inlining this in testF gives:
testF f = putStr (showFigures (take 110 f))
which shows that I'm using it to avoid having too many parentheses.
We've also ignored the importance of the multiplicity constraint. We can enforce this by discarding any result of incF2 which fails the constraint.
incF3 :: Eq a => Multiplicity a -> Symbols a -> Figure a -> Figure a incF3 m s f = head (filter (countok m) (tail (iterate (incF2 m s) f)))
The filter combined with a check that the multiplicity constraint is satisfied will work, but how efficient is it? I am guessing that it will depend how many are rejected. If most are rejected then it's probably inefficient, but if only a few are, then it's the best way. Are there any other pros and cons with this approach?
I think that's the only con. The pro is that it's easy to write.
I am thinking that maybe a more efficient algorithm, in the case where lots are expected to be rejected in the above, would be one involving a dynamically changing multiplicity. Ie, when a symbol is chosen, the multiplicity is modified to reduce the corresponding multiplicity by 1. Of course, maybe I'm just thinking too much in the imperative framework still --- where the multiplicity would be represented as an array of values that could be reassigned. The problem seems to be that lazy lists are not good when you want to do "random access updates", which is roughly what we want to do with a multiplicity list. Are there well known Haskell solutions to this kind of issue?
Yup, that's the algorithm I was thinking of. The structure of the recursion would be something like: incF3 m s f = ... incF3 m' s f' where m' = remove x m If the multiplicity is small an association list [(a,b)] or binary tree will do - update it by copying. For medium sized multiplicities, an array is probably a good bet - again, update by copying. I think there's an implementation of arrays with efficient update kicking around in hslibs If the multiplicity is large, you can use mutable arrays http://www.haskell.org/ghc/docs/latest/set/sec-marray.html at the cost of having to learn what monads are. It should also be possible to provide immutable arrays with constant time update and lookup (so you would not have to learn about monads) but I don't see such a beast in the HS libraries (http://www.haskell.org/haddock/libraries/index.html)
By the way, the reason I wanted my counting to wrap back to "[]" after getting to the maximum figure, is so the function "next" would always work. But your email suggested to me an alternative solution. I could just use the "Maybe" data type! Ie, trying to do a next on the maximum figure just gives you the Maybe "Nothing".
I was wondering why you did the wraparound... In fact, I was wondering why [] was in the list - it didn't seem to belong either. -- Alastair Reid reid@cs.utah.edu http://www.cs.utah.edu/~reid/
On Thu, May 23, 2002 at 04:44:25PM +0930, Mark Phillips wrote: ...
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]
Is there a reason you frame the problem this way? Would it be OK to give a function
count :: [(a,Int)] -> [[a]]
which would return, e.g., the list you gave above? That would probably be more natural to code. --Dylan Thurston
Dylan Thurston wrote:
On Thu, May 23, 2002 at 04:44:25PM +0930, Mark Phillips wrote: ...
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]
Is there a reason you frame the problem this way? Would it be OK to give a function
count :: [(a,Int)] -> [[a]]
which would return, e.g., the list you gave above? That would probably be more natural to code.
I'm not sure this is enough. However what might be enough, an alternative way to frame the problem, would be to have a function which returns a partial list, given some starting point. Ie count :: [(a,Int)] -> [a] -> [[a]] What I am using this counting for is to solve the following problem: Suppose you have 3 boxes (more generally n boxes) in a line, and you have symbols with certain multiplicities as before. I wish to put a list of symbols into each box such that * the total number of occurrences of any given symbol, across all boxes, should equal its multiplicity (ie all symbols should be used the right number of times) * the lists, going from left to right along the boxes, should be increasing (using the above "counting" definition to define the ordering) (so the next box along should contain a sequence that is greater than or equal to the previous one) For a given (symbol,multiplicity) list and a fixed number of boxes, n say, I wish to generate all such choices of symbol lists (ie all choices of lists which satisfy the above conditions). My idea for solving the problem is to choose the first box, starting from [] and incrementing using the above counting method. Then at each step, consider objects for the second box, starting from whatever was in the firxt box and incrementing from there,... and so on. That is what my "next" function is for. To do the incrementing from where the previous box left off. So as you can see, I do need to be able to start part way through the list. Of course, maybe I am not approaching the problem in the best manner. 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
participants (3)
-
Alastair Reid -
Dylan Thurston -
Mark Phillips