Блог

Я хочу создать в Haskell кучу на основе изменяемого массива (базовый тип, встречающийся везде). Однако есть некоторые вещи, которые мне не нравятся в моем первоначальном подходе:

• Я использую кортежи для представления моих куч вместо правильного типа данных
• Я не знаю, как объявлять типы, которые я использую (слишком много переменных типа вокруг), полагаясь на вывод типа (и копирование примеров из Haskell Wiki)
• Моя куча не является полиморфной
• При использовании моей кучи в f функции example мне приходится перемещать n s по кругу.

Каков был бы наилучший способ абстрагировать мою кучу в приятный тип данных?Я чувствую, что это решило бы большинство моих проблем.

 buildHeap max_n =
  do
    arr <- newArray (1, max_n) 0 :: ST s (STArray s Int Int)
    return (0, arr)
  -- My heap needs to know the array where the elements are stored
  -- and how many elements it has

f n =  --example use
  do
    (n1, arr) <- buildHeap n
    (n2, _) <- addHeap (n1, arr) 1
    (n3, _) <- addHeap (n2, arr) 2
    getElems arr
main = print $ runST (f 3)
  

Вам определенно следует обернуть базовое представление в абстрактный тип данных и предоставлять только интеллектуальные конструкторы для построения и разборки вашей структуры данных кучи.

Изменяемые структуры, как правило, имеют более простые API, чем неизменяемые (поскольку они поддерживают меньше хороших поведений). Чтобы получить представление о том, как выглядит разумный API для изменяемого типа контейнера, в том числе о том, как абстрагировать представление, возможно, посмотрите на пакет Judy.

В частности,

• Абстрактный тип данных, который полиморфен в элементах

И API:

 new :: JE a => IO (JudyL a)  
  -- Allocate a new empty JudyL array.

null :: JudyL a -> IO Bool   
  -- O(1), null. Is the map empty?

size :: JudyL a -> IO Int       
  -- O(1), size. The number of elements in the map.

lookup :: JE a => Key -> JudyL a -> IO (Maybe a) 
  -- Lookup a value associated with a key in the JudyL array.

insert :: JE a => Key -> a -> JudyL a -> IO () 
  -- Insert a key and value pair into the JudyL array. Any existing key will be overwritten.

delete :: Key -> JudyL a -> IO ()  
  -- Delete the Index/Value pair from the JudyL array.
  

Вам нужно будет поддерживать многие из тех же операций с подписями аналогичного типа.

Фактическое базовое представление JudyL задается:

 newtype JudyL a =
            JudyL { unJudyL :: MVar (ForeignPtr JudyL_) }

type JudyL_ = Ptr JudyLArray

data JudyLArray
  

Обратите внимание, как мы обеспечиваем потокобезопасность, блокируя базовый ресурс (в данном случае указатель C на структуру данных). Отдельно представление является абстрактным и не видимым для пользователя, что упрощает API.

Общий совет для новичка — начните с IOArrays, а не с STArrays, чтобы вам не приходилось беспокоиться о типах более высокого уровня и других хитростях, которые поставляются с ST. Затем, после того, как вы получили что-то, чем вы довольны, вы можете подумать о том, как переместить это, если хотите, в ST.

Наряду с этим, вы должны создать свой собственный ADT вместо кортежей.

 data MutHeap a = MutHeap Int (IOArray Int a)

buildHeap max_n = do
  arr <- newArray_ (1, max_n) 
  return (MutHeap 0 arr)
  

и т.д.