[Haskell-cafe] Order of Map.fromListWith

[Sergey Vinokurov]

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 at 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe