Стабильное имя меняется без указания причины c - PullRequest
Новая
       22

Стабильное имя меняется без указания причины c

2 голосов
/ 03 февраля 2020

Я пытаюсь реализовать алгоритм HashLife в Haskell. Я черпаю вдохновение из http://dotat.at/prog/life/hslife.hs. Тони Финч использует стабильные имена, как это предлагается в разделе «Растяжение менеджера хранилища».

Импорт, типы псевдонимов и определений, экземпляры: функция Ha sh использует стабильное имя дочерних узлов 

import qualified Data.HashTable.IO             as HT
import           System.IO.Unsafe
import           System.Mem.StableName
import           Data.Hashable
import           System.Mem.Weak
import           Control.Monad

type Table val = HT.CuckooHashTable Key (Weak val)
type Level = Int
type Key = Int
type Cons = QuadCell -> IO QuadCell

newtype NodeInfo = NodeInfo { level :: Level }
  deriving (Show, Eq)

data QuadCell = Dead | Alive | Node !NodeInfo !QuadCell !QuadCell !QuadCell !QuadCell
  deriving Eq

instance Hashable QuadCell where
  hashWithSalt _ (Node (NodeInfo i) a b c d) = unsafePerformIO $ do
    a' <- hashStableName <$> makeStableName a
    b' <- hashStableName <$> makeStableName b
    c' <- hashStableName <$> makeStableName c
    d' <- hashStableName <$> makeStableName d
    return $ i + a' * 3 + b' * 5 + c' * 7 + d' * 9
  hashWithSalt _ _ = error "Received Leaf in hashWithSalt"

instance Show QuadCell where
  show n@(Node (NodeInfo i) a b c d)
         | n == alive = "Alive:" ++ show (hash n)
         | n == dead = "Dead:" ++ show (hash n)
         | otherwise = "Node"
                          ++ "("
                          ++ show a
                          ++ ", "
                          ++ show b
                          ++ ", "
                          ++ show c
                          ++ ", "
                          ++ show d
                          ++ ")"

Теперь я генерирую все возможные ноды уровня 0/1/2 для дерева квадрантов, чтобы сэкономить память и ускорить процесс в долгосрочной перспективе. 

dead, alive :: QuadCell
dead = Node (NodeInfo 0) Dead Dead Dead Dead
alive = Node (NodeInfo 0) Alive Alive Alive Alive

sq0, sq1, sq2 :: [QuadCell]
sq0 = [alive, dead]
sq1 = [ Node (NodeInfo 1) a b c d | a <- sq0, b <- sq0, c <- sq0, d <- sq0 ]
sq2 = [ Node (NodeInfo 2) a b c d | a <- sq1, b <- sq1, c <- sq1, d <- sq1 ]

Затем я вставляю все в HashTable и для отладки. цель, я буду регистрировать вставки 

logging = appendFile "./logs" . (++ "\n")

memoInsert
  :: (Hashable n, Hashable v, Show n, Show v)
  => Table v
  -> n
  -> v
  -> IO ()
memoInsert tbl key val = logging ("Inserting " ++ show key ++ " -> " ++ show val) >> mkWeak key val Nothing >>= HT.insert tbl (hash key)

memoize = error "Not implemented"

consTable :: IO Cons
consTable = do
  table <- HT.new
  let add q = memoInsert table q q
  mapM_ add (sq0 ++ sq1 ++ sq2)
  return memoize

main :: IO ()
main = void consTable

пример журналов: 

Inserting Alive:24 -> Alive:24
Inserting Dead:48 -> Dead:48
Inserting Node1-73(Alive:24, Alive:24, Alive:24, Alive:24) -> Node1-73(Alive:24, Alive:24, Alive:24, Alive:24)
Inserting Node1-82(Alive:24, Alive:24, Alive:24, Dead:48) -> Node1-82(Alive:24, Alive:24, Alive:24, Dead:48)
Inserting Node1-80(Alive:24, Alive:24, Dead:48, Alive:24) -> Node1-80(Alive:24, Alive:24, Dead:48, Alive:24)
Inserting Node1-89(Alive:24, Alive:24, Dead:48, Dead:48) -> Node1-89(Alive:24, Alive:24, Dead:48, Dead:48)
Inserting Node1-78(Alive:24, Dead:48, Alive:24, Alive:24) -> Node1-78(Alive:24, Dead:48, Alive:24, Alive:24)
Inserting Node1-87(Alive:24, Dead:48, Alive:24, Dead:48) -> Node1-87(Alive:24, Dead:48, Alive:24, Dead:48)
Inserting Node1-85(Alive:24, Dead:48, Dead:48, Alive:24) -> Node1-85(Alive:24, Dead:48, Dead:48, Alive:24)
Inserting Node1-94(Alive:24, Dead:48, Dead:48, Dead:48) -> Node1-94(Alive:24, Dead:48, Dead:48, Dead:48)
Inserting Node1-76(Dead:48, Alive:24, Alive:24, Alive:24) -> Node1-76(Dead:48, Alive:24, Alive:24, Alive:24)
Inserting Node1-85(Dead:48, Alive:24, Alive:24, Dead:48) -> Node1-85(Dead:48, Alive:24, Alive:24, Dead:48)
Inserting Node1-83(Dead:48, Alive:24, Dead:48, Alive:24) -> Node1-83(Dead:48, Alive:24, Dead:48, Alive:24)
Inserting Node1-92(Dead:48, Alive:24, Dead:48, Dead:48) -> Node1-92(Dead:48, Alive:24, Dead:48, Dead:48)
Inserting Node1-81(Dead:48, Dead:48, Alive:24, Alive:24) -> Node1-81(Dead:48, Dead:48, Alive:24, Alive:24)
Inserting Node1-90(Dead:48, Dead:48, Alive:24, Dead:48) -> Node1-90(Dead:48, Dead:48, Alive:24, Dead:48)
Inserting Node1-88(Dead:48, Dead:48, Dead:48, Alive:24) -> Node1-88(Dead:48, Dead:48, Dead:48, Alive:24)
Inserting Node1-97(Dead:48, Dead:48, Dead:48, Dead:48) -> Node1-97(Dead:48, Dead:48, Dead:48, Dead:48)
Inserting Node2-122(Node1-73(Alive:24, Alive:24, Alive:24, Alive:24), Node1-73(Alive:24, Alive:24, Alive:24, Alive:24), Node1-73(Alive:24, Alive:24, Alive:24, Alive:24), Node1-73(Alive:24, Alive:24, Alive:24, Alive:24)) -> Node2-122(Node1-73(Alive:24, Alive:24, Alive:24, Alive:24), Node1-73(Alive:24, Alive:24, Alive:24, Alive:24), Node1-73(Alive:24, Alive:24, Alive:24, Alive:24), Node1-73(Alive:24, Alive:24, Alive:24, Alive:24))
Inserting Node2-131(Node1-73(Alive:24, Alive:24, Alive:24, Alive:24), Node1-73(Alive:24, Alive:24, Alive:24, Alive:24), Node1-73(Alive:24, Alive:144, Alive:144, Alive:144), Node1-112(Alive:144, Alive:144, Alive:144, Dead:72)) -> Node2-41(Node1-121(Alive:144, Alive:144, Alive:144, Alive:144), Node1-121(Alive:144, Alive:144, Alive:144, Alive:144), Node1-121(Alive:144, Alive:144, Alive:144, Alive:144), Node1-112(Alive:144, Alive:144, Alive:144, Dead:72))
Inserting Node2-95(Node1-121(Alive:144, Alive:144, Alive:144, Alive:144), Node1-121(Alive:144, Alive:144, Alive:144, Alive:144), Node1-121(Alive:144, Alive:144, Alive:144, Alive:144), Node1-114(Alive:144, Alive:144, Dead:72, Alive:144)) -> Node2-95(Node1-121(Alive:144, Alive:144, Alive:144, Alive:144), Node1-121(Alive:144, Alive:144, Alive:144, Alive:144), Node1-121(Alive:144, Alive:144, Alive:144, Alive:144), Node1-114(Alive:144, Alive:144, Dead:72, Alive:144))

На этом этапе все вставлено правильно. Проблема в том, что хэши не согласованы (например, Alive идет от ha sh 24 до 144 в журналах). Я подозреваю, что начальный sq * пострадает от ранних оценок. Раздел не хранится с оцененными данными, поэтому имена стабильных пользователей меняются. Я могу справиться с этой проблемой?

...