Dear All, I have been wrestling with this for a while now. I have a list of data items, and want to be able to access them, in a Hash Map, via a short summary of their characteristics. In an imperative language this might look like: myMap = new map() I have been trying to do this in Haskell, but am stuck on how to hand the Map back to itself each time. I have a function :: elem -> [p,q] to make the key, but the Map.insert function has the following signature: insert :: (Hashable k, Ord k) => k -> a -> HashMap k a -> HashMap k a My thought was that I needed to go through the list of the elems, and at each point add them to the Hash Map, handing the updated Map onto the next step - but this is what I cannot write. Any help much appreciated. Thanks, _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
On Friday, June 19, 2015, Matt Williams <[hidden email]> wrote:
This is typically done with fromListWith or a combination of foldl' and insertWith or alter. -bob
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
I tried doing it as a fold (the pattern of accumulating a value, where the accumulated value was the resulting Map), but couldn't manage the syntax. Have now got it partially working with fromListWith. Thanks a lot, On Fri, 19 Jun 2015 07:18 Bob Ippolito <[hidden email]> wrote: On Friday, June 19, 2015, Matt Williams <[hidden email]> wrote: _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
To learn, I'd suggest you implement it first with the recursion (a
tip: use a "loop" function in where clause), and than with fold.
Those are important features to understand in Haskell. Try to use
the "higher-level" functions as little as possible until you grasp
the basics (like fold syntax).
If you just need any solution, fromListWith is fine. br, vlatko
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Dear All, Thanks for your help with this. I have got the simple version working but now need to use Map.fromListWith, and am having syntax problems. I found a related question on Stack overflow (here: http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key ). However, I'm having problems understanding the additional function. The signature should be : And so I assume I need to supply a function whose signature is: (a -> a -> a) Is that correct? Thanks, On Fri, 19 Jun 2015 09:04 Vlatko Basic <[hidden email]> wrote:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
An example of a function of (a -> a -> a) would be (+), which works if your values are numbers (which mirrors your Python-like pseudocode).
On Friday, June 19, 2015, Matt Williams <[hidden email]> wrote:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
In reply to this post by Matt Williams-2
On 06/19/2015 01:51 AM, Matt Williams wrote:
> > In an imperative language this might look like: > > myMap = new map() > for elem in myElems: > key = makeKey(elem) > myMap[key] = myMap[key] + elem > > ... > > My thought was that I needed to go through the list of the elems, and at > each point add them to the Hash Map, handing the updated Map onto the > next step - but this is what I cannot write. > Your thought was right. You want to go through the list of elems, building up a new value (the hash map) as you go. The pattern is called a fold, as others have mentioned. The only tricky part is gluing together the pieces. Your pseudocode above looks like it assumes that myMap[key] will return zero if `key` isn't present in `myMap`. I think I've managed to reproduce what you want. The "key from element" function I used is just the identity function, but you should be able to adapt it. module Main where import Data.Map (Map, empty, insert) import qualified Data.Map as M (lookup) key_from_elem :: Int -> Int key_from_elem = id loop :: [Int] -> (Map Int Int) -> (Map Int Int) loop elems initial_map = foldr update_map initial_map elems where update_map :: Int -> (Map Int Int) -> (Map Int Int) update_map x m = let k = key_from_elem x in case (M.lookup k m) of Nothing -> insert k x m Just v -> insert k (v + x) m main :: IO () main = do let elems = [1,2,3,4,5] let l1 = loop elems empty print l1 let l2 = loop elems l1 print l2 let l3 = loop elems l2 print l3 _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Le ven. 19 juin 2015 à 19:03, Michael Orlitzky <[hidden email]> a écrit : loop :: [Int] -> (Map Int Int) -> (Map Int Int) While this code will do the right thing, it won't do it efficiently, at all ! First (and huge) problem is using foldr : starting from the end of the list is the wrong move here if you want to consume your Int stream efficiently (which you probably do and which is vital if the stream is big). So you should be using foldl' and the strict version of Map (Data.Map.Strict). Also, though less important, looking up a key then updating the value with insert is wasteful : you will be doing the search twice, instead of using one of the nice combinators of Data.Map which find and update a value in one pass like "insertWith (+) k x m" In other words : import qualified Data.Map.Strict as M countingMap :: [(key, Int)] -> Map key Int countingMap kvs = foldl' update M.empty kvs where update (k,v) m = M.insertWith (+) k v m Since this is a very common need, there's even a combinator to do this : countingMap :: [(key, Int)] -> Map key Int countingMap kvs = M.fromListWith (+) kvsAt which point you may even use directly this code and forgo creating a function for it (except if you're using it several times or as a minor step in a big pipeline where you would like to label each step clearly). -- Jedaï _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Free forum by Nabble | Edit this page |