第35回　キーを使って値を参照するMap型

-- > fromList [] == empty
-- > fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
-- > fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
fromList :: Ord k => [(k,a)] -> Map k a 
fromList xs       
  = foldlStrict ins empty xs
  where
    ins t (k,x) = insert k x t

～ 略 ～

foldlStrict :: (a -> b -> a) -> a -> [b] -> a
foldlStrict f z xs
  = case xs of
      []     -> z
      (x:xx) -> let z' = f z x in seq z' (foldlStrict f z' xx)

-- > toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- > toList empty == []
toList :: Map k a -> [(k,a)]
toList t      = toAscList t
-- | /O(n)/. Convert to an ascending list.
--
-- > toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
toAscList :: Map k a -> [(k,a)]
toAscList t   = foldr (\k x xs -> (k,x):xs) [] t

-- | /O(n)/. Post-order fold.
foldr :: (k -> a -> b -> b) -> b -> Map k a -> b
foldr _ z Tip              = z
foldr f z (Bin _ kx x l r) = foldr f (f kx x (foldr f z r)) l

instance Foldable (Map k) where
  foldMap _f Tip = mempty
  foldMap f (Bin _s _k v l r)
    = foldMap f l `mappend` f v `mappend` foldMap f r

Prelude Data.Map> fromList [("foo",10),("bar",24)]
fromList [("bar",24),("foo",10)]
Prelude Data.Map> Data.Foldable.toList $ fromList [("foo",10),("bar",24)]
[24,10]