List -> Map -> List, to add duplicates?
Hi All, This seems like an inefficient way to do what I'm trying to do. I'd really appreciate any suggestions or comments: import qualified Data.Map as Map data Currency = Dollar | Yen | XP | Health | Street_Cred | Peso deriving (Show, Eq, Ord) -- why ord? withDups = [(30, Dollar), (-20, Street_Cred), (-2, Dollar), (30, XP), (15, Peso), (30, XP)] flipAssoc (a, b) = (b, a) noDups = Map.fromListWith (+) (map flipAssoc withDups) final = map flipAssoc $ Map.toList noDups Thanks for your time! Tom
On Mon, 2011-06-06 at 21:43 -0400, Tom Murphy wrote:
Hi All, This seems like an inefficient way to do what I'm trying to do.
Intuition tells me it's inefficient, but on second thought: You're trying to accumulate (and add) values for a matching given index (in this case, the second argument of the tuple -- btw flipAssoc is available as Data.Tuple.swap). That necessarily means traversing the list, the whole time retaining quick random access to update the value associated with a particular index -- which is exactly what Maps are for, right? The code does exactly what you want with the least complexity, AFAICS, though of course it'd be nicer if there wasn't this List->Map->List. I'd argue this isn't inefficient to do what you're doing, but I'd look for a more general optimisation in the context this code comes from in order to avoid such an operation from the start entirely. :) That may involve keeping a single map, and updating it progressively as each pair comes in (which you can do for the initial creation too, with a fold). Cheers, Arlen
Tom Murphy
This seems like an inefficient way to do what I'm trying to do. I'd really appreciate any suggestions or comments:
[...]
I don't see why it would be inefficient, although you don't exactly need the map data structure. A set would totally suffice, and since tuples have an Ord instance, the following should work (untested!): import qualified Data.Set as S newtype Humanism a = Human { animal :: a } instance Eq (Humanism a) where _ == _ = True instance Ord (Humanism a) where compare _ _ = EQ swap :: (a,b) -> (b,a) swap (x,y) = (y,x) nubBySnd :: Ord b => [(a,b)] -> [(a,b)] nubBySnd = map (swap . first animal) . S.toList . S.fromList . map (first Human . swap) Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/
Is this what you want? (note that it does not preserve ordering, but neither
does Map):
import Data.List
import Data.Function
noDups :: (Ord b, Num a) => [(a,b)] -> [(a,b)]
noDups = map sumGroup . groupBy ((==) `on` snd) . sortBy (compare `on` snd)
where
sumGroup xs = (sum $ map fst xs, snd $ head xs)
If you use the fact that the list has at most one value per currency,
perhaps you should just keep the values in a map instead.
/J
On 7 June 2011 03:43, Tom Murphy
Hi All, This seems like an inefficient way to do what I'm trying to do. I'd really appreciate any suggestions or comments:
import qualified Data.Map as Map
data Currency = Dollar | Yen | XP | Health | Street_Cred | Peso deriving (Show, Eq, Ord) -- why ord?
withDups = [(30, Dollar), (-20, Street_Cred), (-2, Dollar), (30, XP), (15, Peso), (30, XP)]
flipAssoc (a, b) = (b, a)
noDups = Map.fromListWith (+) (map flipAssoc withDups)
final = map flipAssoc $ Map.toList noDups
Thanks for your time! Tom
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
participants (4)
-
Arlen Christian Mart Cuss -
Ertugrul Soeylemez -
Jonas Almström Duregård -
Tom Murphy