Тип подписи для изменяемой кучи Haskell - PullRequest
Новая
       14

Тип подписи для изменяемой кучи Haskell

4 голосов
/ 11 мая 2011

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

  • Я использую кортежи для представления своих куч, вместо правильного типа данных
  • Я не знаю, как объявить типы, которые я использую (слишком много переменных типов вокруг), полагаться на вывод типов (и копировать примеры из Haskell Wiki)
  • Моя куча не полиморфна
  • Когда я использую мою кучу в примере функции f, мне нужно связать 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)

Ответы [ 2 ]

5 голосов
/ 11 мая 2011

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

Изменчивые структуры, как правило, имеют более простые 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 простым.

4 голосов
/ 11 мая 2011

Общий совет для новичка - начните с 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)

и т.д.

...