juan_gandhi | наука и жизнь

рано радуетесь. :)

http://ivan-gandhi.livejournal.com/2019207.html?thread=24711559#t24711559 - такой пример не существует? разве только по умолчанию в хаскеле это SortedSet.

Prelude Data.HashSet> toList (fromList [1, 2]) == toList (fromList [2,1])
Loading package deepseq-1.1.0.2 ... linking ... done.
Loading package bytestring-0.9.1.10 ... linking ... done.
Loading package text-0.11.2.0 ... linking ... done.
Loading package hashable-1.1.2.3 ... linking ... done.
Loading package unordered-containers-0.2.1.0 ... linking ... done.
True

И даже

Prelude Data.HashSet Test.QuickCheck> quickCheck $ \a b -> (toList $ fromList [a, b]) == (toList $ fromList [b, a])
+++ OK, passed 100 tests.

Edited 2012-07-03 08:44 (UTC)

how do you prove equality by comparing ~~two~~ 100 points?

А можно одновременно выдать значение хэша, используемого этими сетами? И можно найти две значения, которые дают одинаковый хэш, а потом попытаться создать сеты из этих значений?

По умолчаниюв Хаскеле это множество на сбалансированном дереве. HashSet это отображение из целых в множества на сбалансированном дереве.

http://hackage.haskell.org/packages/archive/hashmap/1.0.0.2/doc/html/Data-HashSet.html

Интересно, а зачем там Ord? Значения с тем же хешем упорядочиваются, что ли?

Да. И поддерживаются, как множество (то есть, нет повторных элементов и нет зависимости от порядка добавления).

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

занятная конструкция IntMap, нужно ещё почитать.

да, полистал insert - вот так оно и должно быть :) а не то, что джавы всякие - linked list значений, понимаешь!..

C помощью святаго духа, смекалки и квикчека, нашел что

hash 4 == hash 4 + 2 ^ 39

Prelude Data.HashSet Data.Hashable Test.QuickCheck> toList (fromList [4, 4 + 2 ^ 39]) == toList (fromList [4 + 2 ^
39, 4])
False

Но для Data.Set (который требует порядка) всё как положено.

a prosvetite ubogogo, please...

chem Data.HashSet luchshe chem Data.Set?

v kakih takih cluchajah pol'zujut? nabor funcij vrode odin i tot zhe

===========================

P.S.

ksta, otkompilit' vash primer ne daet:



--  sets1.hs

import qualified Data.Set as S
import qualified Data.HashSet as H

z =
  S.toList (S.fromList [4, 4 + 2 ^ 39]) ==
  S.toList (S.fromList [4 + 2 ^ 39, 4])

z' =
  H.toList (H.fromList [4, 4 + 2 ^ 39]) ==
  H.toList (H.fromList [4 + 2 ^ 39, 4])

i vot, v ghci:

*Main> :r
[1 of 1] Compiling Main ( sets1.hs, interpreted )

sets1.hs:54:15:
Ambiguous type variable `a0' in the constraints:
(Data.Hashable.Hashable a0) arising from a use of `H.fromList'
at sets1.hs:54:15-24
(Num a0) arising from the literal `4' at sets1.hs:54:39
(Eq a0) arising from a use of `H.fromList' at sets1.hs:54:15-24
Probable fix: add a type signature that fixes these type variable(s)
In the second argument of `($)', namely
`H.fromList [4 + 2 ^ 39, 4]'
In the second argument of `(==)', namely
`(H.toList $ H.fromList [4 + 2 ^ 39, 4])'
In the expression:
(H.toList $ H.fromList [4, 4 + 2 ^ 39])
==
(H.toList $ H.fromList [4 + 2 ^ 39, 4])
Failed, modules loaded: none.

===================================

P.P.S.

a vot esli tak, to compilitsa, no rezul'tat : true



z' =
  (H.toList $ H.fromList [4::Int, 4 + 2 ^ 39]) ==
  (H.toList $ H.fromList [4 + 2 ^ 39, 4::Int])

*Main> :r
Ok, modules loaded: Main.
*Main> z'
True
*Main>

Edited 2012-07-03 14:39 (UTC)

См. http://www.haskell.org/ghc/docs/latest/html/users_guide/interactive-evaluation.html раздел 2.4.7. Type defaulting in GHCi.

В GHCi действуют другие правила для тайпчекера, поэтому если я набираю в промпте

toList (fromList [4, 4 + 2 ^ 39]) == toList (fromList [4 + 2 ^ 39, 4])

- оно работает, а при переносе в исходник требуется указать, какие именно целые числа имеются ввиду. Например, так

zz = S.toList (S.fromList [4::Integer, 4 + 2 ^ 39]) == S.toList (S.fromList [4 + 2 ^ 39, 4])

> a vot esli tak, to compilitsa, no rezul'tat : true

Конечно будет true, т.к. 4::Int + 2 ^ 39 == 4 на архитектурах с 32-битными интами:

Prelude> [4 + 2 ^ 39, 4::Int]
[4,4]
Prelude> [4 + 2 ^ 39, 4::Integer]
[549755813892,4]

da, s typecheck ja teper' ponjal, spasibo

a zachem ispol'zovat' Data.HashSet

v chem bonus?

(deleted comment)

> ne, zachem ispol'zujut Data.HashSet ?

Я не знаю, я не использую.

Реализации и интерфейсы существенно различные.

HashSet требует от элементов реализации Hashable.

Set требует реализации Ord.

Думаю, что проще в реализации и быстрее исполняется в конкретном случае - то и надо использовать.

>> Я не знаю, я не использую.

hurraaa!!! a to ja dumal, chto ja odin takoj :)

spasibo za raz'jasnenija

дык, вроде ясно зачем.

Set имеет логарифмическую (от размера сета) стоимость для insert / delete / lookup. HashSet амортизирует эту стоимость за счёт O(1) операции хеширования (дальше логарифмическая стоимость поиска по меньшему субсету).

Непонятно, насколько он амортизирует и амортизирует ли, т.к. IntMap - это не хеш-таблица, а bit trie, как я понял.

ха, я не посмотрел.

ну, тогда вычислить хеш один раз и сравнивать хеши просто, а сравнивать сложный объект каждый раз - не просто.

мммм... дык, HashSet тоже требует Ord.

А можно разложить по полочкам, почему пример с HashSet выдал False? Я сегодня с утра когда глядел, мне показалось, что весь сет бьётся на субсеты с помощью хеша, а субсет-то всё равно Set. Т.е. значения с одинаковым хешем всё равно должны оказаться упорядоченными в каждом субсете. Вот и не понятно, в чём прикол тогда.

Это не ко мне. Меня всего лишь попросили найти коллизию и проверить с ней.

ну да, но теперь же это самое интересное :)

import qualified Data.IntMap as I
import qualified Data.Set as S
...
insert :: (Hashable a, Ord a) => a -> HashSet a -> HashSet a
insert a (HashSet s) = HashSet $
  I.insertWith (\_ -> S.insert a) (hash a) (S.singleton a) s

по ключу (hash a) нашли существующее значение и скомбинировали его с новым: (S.insert a). Поскольку S.insert==Set.insert, то должно быть отсортировано. quickcheck что, к разным типам привёл два списка?

> quickcheck что, к разным типам привёл два списка?

Это исключено, т.к. (==) :: Eq a => a -> a -> Bool, а не (Eq a, Eq b) => a -> b -> Bool, т.е. сравнению требуется 2 одинаковых типа.

Вы на toList и fromList посмотрите. Как происходит вставка одного элемента - иррелевантно, т.к. пример её не использует.

ну, посмотрю. я думал, дложно было быть consistent с поэлементной вставкой.

(no subject)

nponeccop.livejournal.com - 2012-07-04 07:38 (UTC) - Expand

говорят, используется:

fromList :: (Hashable a, Ord a) => [a] -> HashSet a
fromList xs = foldl' (flip insert) empty xs

да, я понимаю насчёт Eq, но как ещё объяснить разницу. Если бы объекты были одинаковы, то insert выполнился бы одинаково.

Мне доустановить ещё чё-то там надо. А то бы просто глянуть на fromList одного и другого.