Почему HashMap не в нормальном виде после ряда вставок?

Я пытался обеспечить строгость встроенной модели программы на Haskell, используя пакет ghc-heap-view и предоставляемые им утилиты, когда заметил, что мой HashMapПохоже, что они не в NF после серии на вставках. Я попытался распечатать дерево кучи, и действительно, он показывает некоторые гирлянды. Затем я попробовал другой способ вставки элементов (используя union а также singleton) и на этот раз это выходит строго.

Может ли кто-нибудь объяснить, почему это так, и посоветовать, что я могу сделать, чтобы сделать это? insert вести себя так же, как другой метод?

Вот мой тестовый код:

module Main where

import           Control.Exception           (evaluate)
import           Data.Foldable
import           Data.HashMap.Strict         (HashMap)
import qualified Data.HashMap.Strict         as HM
import           GHC.HeapView

test1 :: HashMap Int Int
test1 = foldl' (\m v -> HM.insert v v m) HM.empty [0..5]

test2 :: HashMap Int Int
test2 = foldl' (\m v -> HM.union (HM.singleton v v) m) HM.empty [0..5]

main :: IO ()
main = do
  putStrLn "HeapTree for test1"
  t1 <- evaluate test1
  buildHeapTree 10 (asBox t1) >>= print . ppHeapTree

  putStrLn "HeapTree for test2"
  t2 <- evaluate test2
  buildHeapTree 10 (asBox t2) >>= print . ppHeapTree

И вот вывод:

HeapTree for test1
"BitmapIndexed ([ (_thunk (I# 0) (I# 0) 0), (_thunk (I# 1) (I# 1) 1), (Leaf (I# 2) (I# 2) 2), (Leaf (I# 3) (I# 3) 3), (Leaf (I# 4) (I# 4) 4), (Leaf (I# 5) (I# 5) 5) ]) 63"
HeapTree for test2
"BitmapIndexed ([ (Leaf (I# 0) (I# 0) 0), (Leaf (I# 1) (I# 1) 1), (Leaf (I# 2) (I# 2) 2), (Leaf (I# 3) (I# 3) 3), (Leaf (I# 4) (I# 4) 4), (Leaf (I# 5) (I# 5) 5) ]) 63"
(0.02 secs, 1,067,672 bytes)
Источник

1 ответ

Решение

При вставке нового, не сталкивающегося ключа в Leaf узел, insert использует вспомогательную функцию под названием two создать двухэлементную карту. two Функция ленива в значениях клавиш, что приводит к тому, что GHC создает thunks для создания двух новых Leaf узлы. Все это довольно глупо, потому что ключи уже наверняка будут в WHNF. Но (предположительно из-за рекурсивного go функция) GHC не осознает этого. Проблема должна быть исправлена ​​в следующей версии unordered-containers,

Источник
Другие вопросы по тегам