Order of Map.fromListWith
Does anybody know why for fromListWith, the arguments to the combining function seem flipped?
import Data.Map fromListWith (++) [('a',[1]),('a',[2])]
fromList [('a',[2,1])] I often use it to group things by some key, e.g. postsByUserId :: Map Int [Int] postsByUserId = fromListWith (++) [ (userId, [postId]) | (userId, postId) <- posts ] and regularly get tricked by the postIds being reversed in the result. This is especially unintuitive to me since:
foldl (++) [] [[1],[2]] [1,2] foldr (++) [] [[1],[2]] [1,2]
Any ideas?
It looks like fromListWith is indeed implemented with a left fold over insertWithKey, with the Map as the accumulator. However, in insertWithKey the value-combiner function has type 'k -> a -> k -> a' which means it can combine in either order (it doesn't have to do with the fold or iteration order at all). The docs say: If the key does exist, the function will insert the pair @(key,f key new_value old_value)@. This doesn't really answer the "why" part of your question, but explains why you get [2, 1] instead of the reverse. On Thursday, March 3, 2016, Niklas Hambüchen <mail@nh2.me> wrote:
Does anybody know why for fromListWith, the arguments to the combining function seem flipped?
import Data.Map fromListWith (++) [('a',[1]),('a',[2])]
fromList [('a',[2,1])]
I often use it to group things by some key, e.g.
postsByUserId :: Map Int [Int] postsByUserId = fromListWith (++) [ (userId, [postId]) | (userId, postId) <- posts ]
and regularly get tricked by the postIds being reversed in the result.
This is especially unintuitive to me since:
foldl (++) [] [[1],[2]] [1,2] foldr (++) [] [[1],[2]] [1,2]
Any ideas? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org <javascript:;> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Correction: "the combiner has type 'k -> a -> a -> a'" On Thursday, March 3, 2016, Patrick Redmond <plredmond@gmail.com> wrote:
It looks like fromListWith is indeed implemented with a left fold over insertWithKey, with the Map as the accumulator. However, in insertWithKey the value-combiner function has type 'k -> a -> k -> a' which means it can combine in either order (it doesn't have to do with the fold or iteration order at all). The docs say:
If the key does exist, the function will insert the pair @(key,f key new_value old_value)@.
This doesn't really answer the "why" part of your question, but explains why you get [2, 1] instead of the reverse.
On Thursday, March 3, 2016, Niklas Hambüchen <mail@nh2.me <javascript:_e(%7B%7D,'cvml','mail@nh2.me');>> wrote:
Does anybody know why for fromListWith, the arguments to the combining function seem flipped?
import Data.Map fromListWith (++) [('a',[1]),('a',[2])]
fromList [('a',[2,1])]
I often use it to group things by some key, e.g.
postsByUserId :: Map Int [Int] postsByUserId = fromListWith (++) [ (userId, [postId]) | (userId, postId) <- posts ]
and regularly get tricked by the postIds being reversed in the result.
This is especially unintuitive to me since:
foldl (++) [] [[1],[2]] [1,2] foldr (++) [] [[1],[2]] [1,2]
Any ideas? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
I am not 100% sure, but it seems to be the right optimization for the case where combining function is (++): prepending singleton lists is a lot cheaper than appending them to the end, in which case you'd get quadratic complexity. Sergey On Thu, Mar 3, 2016 at 7:23 PM, Niklas Hambüchen <mail@nh2.me> wrote:
Does anybody know why for fromListWith, the arguments to the combining function seem flipped?
import Data.Map fromListWith (++) [('a',[1]),('a',[2])]
fromList [('a',[2,1])]
I often use it to group things by some key, e.g.
postsByUserId :: Map Int [Int] postsByUserId = fromListWith (++) [ (userId, [postId]) | (userId, postId) <- posts ]
and regularly get tricked by the postIds being reversed in the result.
This is especially unintuitive to me since:
foldl (++) [] [[1],[2]] [1,2] foldr (++) [] [[1],[2]] [1,2]
Any ideas? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
participants (3)
-
Niklas Hambüchen -
Patrick Redmond -
Sergey Vinokurov