[haskell][поругайте] Хэш-таблица

Ах да. Ещё такой вопрос.

Для добавления/обновления и удаления пары «ключ-значение» из списка у меня написаны функции chainWith и chainWithout.

Для добавления/обновления и удаления пары «ключ-значение» из таблицы - соответственно, with и without.

Я пытался сделать обобщенные with и without через тайпклассы, которые работали бы как для отдельных слотов, так и для всей таблицы. Но у меня не получилось.

Можно ли сделать это через тайпклассы, и если да, то как? Суть проблемы в том, что природа некоторых аргументов у перечисленных функций - разная.

atChain :: (Eq k) => k -> Chain k v -> Maybe v
atChain _ [] = Nothing
atChain lk ((k,v):cs) | lk == k = Just v
                      | otherwise = atChain lk cs

Ад.

Точняра, про Data.List.find я и забыл -__-

Нее, это я так, в целом. Еще хардкорее перла…

Точняра, про Data.List.find я и забыл -__-

А про Prelude.lookup?

Там нету никакого хардкора, всё просто и понятно, если немного узнать, как читать такую нотацию:) В C# и python такой связки (конструкция языка + паттерн матчинг встроенных типов), лично мне, оч. не хватает иногда.

А про Prelude.lookup?

OH SHI~, а про неё я и не знал. Но попой чуял, что в хаскеле уже есть что-то для работы с alist-ами

Немного не в тему, но думаю будет полезно. Функциональное программирование в Scheme: структуры данных Прочитай, в примеры кода можешь не всматриваться особо.

Собственно я это к чему. Реализовывать хэш-таблицу в функциональных языках не так уж и полезно.Хотя можешь я чего то не понимаю...

Собственно я это к чему. Реализовывать хэш-таблицу в функциональных языках не так уж и полезно.Хотя можешь я чего то не понимаю...

Вообще-то ffi никто не отменял, и, если я правильно понимаю, Array и сделан с помощью него. Хеш же можно написать (как и сделал тс) на функциональном уровне поверх Array. В чем проблема?

divHashForSize :: (Integer -> Integer -> Integer)

Влом разбираться... Но `hashPrepare' используется только в сабжевой функции. Нельзя просто использовать класс для newtype-обертки (integer-> a -> integer)?

тогда уж Okasaki Purely Functional Data Structures, там на примере ML и Haskell.

Собственно я это к чему. Реализовывать хэш-таблицу в функциональных языках не так уж и полезно.Хотя можешь я чего то не понимаю...

с чего бы вдруг реализовывать структуру с доступом к данным за O(1) было бы не так уж и полезно?

правда к реализованной структуре это не относится..

hlint-ом бы сначала код прогнал, там вроде ничего серьёзного, но код почище будет.

Кинул, что под рукой оказалось. Насчет доступа за O(1) - не будет сложно просмотреть ту статью? В кратце - фишка в организации памяти. Хотя я могу чего то не понимать...

Не, про ffi речь не шла даже.

А без этого - не компиляется. Чувствую, что здесь что-то не так.

Да. У глобальных объявлений принято (да и требуется тащемта) указывать тип. Поэтому:

intHash :: ChainedHash Integer v
intHash = createHash divHashForSize 10

А если где-нибудь в коде, то по ряду причин лучше указывать тип, который требуется от выражения целиком:

createHash divHashForSize 10 :: ChainedHash Integer v

В экспортах и импортах забыл указать типы (Chain, ChainedHash, HashFuncForSize). Это баг или оригинальный архитектурный ход?

Может стоит подумать об именованиях по мотивам Data.Map? Вместо with и without, например, insert и delete. Вместо at — lookup.

P.S. Местами есть лишние скобки. hlint поможет их убрать.

Например, можно так:

import Prelude hiding (lookup)
import qualified Prelude as P

newtype Chain k v = Chain { runChain :: [(k, v)] }

class Container m where
  insert :: Eq k => k -> v -> m k v -> m k v
  lookup :: Eq k => k -> m k v -> Maybe v
  delete :: Eq k => k -> m k v -> m k v

instance Container Chain where
  insert k v m = chainWith m (k, v)
  lookup k (Chain m) = P.lookup k m
  delete k m = chainWithout m k

instance Container ChainedHash where
  insert k v m = with m (k, v)
  lookup k m = at k m
  delete k m = without m k

доступ к данным там совсем не O(1).

где? в хэш-таблицах? в хэш таблицах в чистых языках? в конкретном варианте описанном тут?

правда к реализованной структуре это не относится..

А в чём косяки? Где-то надо было seq-ов добавить? Где и как правильно?

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

Спасибо, уяснил

Это баг или оригинальный архитектурный ход?

Второе. *[Cc]hain* - это вообще деталь реализации, нечего её экспортировать :)

HashFuncForSize экспортируется по-умолчанию, как и все из файла

cast nCdy

Так и я могу :)

Только вот фишечка в том, чтобы insert был от двух аргументов, чтобы можно было писать как у меня table `insert` (k, v). (Правда, для функции с названием insert такое не очень смотрится, но всё же). При этом для цепочки оно бы уже работало не с кортежем, а с просто одним значением. Как это выразить в тайпклассе, я так и не допёр

Okasaki Purely Functional Data Structures

Давно лежит в очереди на прочтение. Пока я просто всё 1-в-1 из Кормена&co перевожу. За ссылку на hlint спасибо :)

Только вот фишечка в том, чтобы insert был от двух аргументов,

чтобы можно было писать как у меня table `insert` (k, v).

newtype Chain_ k v = Chain [(k, v)]
  deriving ( Show )

class Insert h where
  insert :: Eq k => h k v -> (k, v) -> h k v

instance Insert Chain_ where
  insert (Chain m) = Chain . chainWith m

instance Insert ChainedHash where
  insert m = with m

-- > Chain [("a", 1), ("b", 2)] `insert` ("c", 3)
-- Chain [("c",3),("a",1),("b",2)]

-- > conf `insert` ("a", 5)
-- [("longitude",7),("x-axis",1),("y-axis",0),("a",5),("tension",2)]

instance Chain для синонима типов не написать, написать instance (Πa b. [(a, b)]) тем более нельзя, поэтому нужен newtype.

Где-то надо было seq-ов добавить?

Хэш-таблички со всякими убер-оптимизациями это Data.HashTable. Правда, там сложности функций не озвучены.

Теперь дошло, спасибо!

в целом лично меня пугает Array как внутренее хранилище, если я всё правильно понимаю, то в чистом коде придётся при каждом изменении делать копию массива, что не очень хорошо. Массив можно использовать если жить в IO или в ST или если типичное использование это создать таблицу каким-нибудь fromList и потом основная операция это поиск. Судя по Окасаки, которого я с трудом пытаюсь осиливать, для таблицы используются структуры типа BinaryList, когда двоичному представлению хэша сопоставляется точка в списке деревьев, но в этом случае worstcase будет log(N), хотя амортизированное время доступа может оставаться O(1) (могу сильно наврать).