наука и жизнь

[juan_gandhi]

Scala:

  scala> List(Set(1,2)).flatten == List(Set(2,1)).flatten
res3: Boolean = false

Бля.

Comments

[nponeccop.livejournal.com]

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 (который требует порядка) всё как положено.

[eacher.livejournal.com]

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>

[nponeccop.livejournal.com]

См. 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])

[nponeccop.livejournal.com]

> 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]

[eacher.livejournal.com]

da, s typecheck ja teper' ponjal, spasibo

a zachem ispol'zovat' Data.HashSet

v chem bonus?

[nponeccop.livejournal.com]

> ne, zachem ispol'zujut Data.HashSet ?

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

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

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

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

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

[eacher.livejournal.com]

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

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

spasibo za raz'jasnenija

[sassa-nf.livejournal.com]

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

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

[nponeccop.livejournal.com]

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

[sassa-nf.livejournal.com]

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

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

[sassa-nf.livejournal.com]

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

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

[nponeccop.livejournal.com]

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

[sassa-nf.livejournal.com]

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

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 что, к разным типам привёл два списка?

[nponeccop.livejournal.com]

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

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

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

[sassa-nf.livejournal.com]

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

[nponeccop.livejournal.com]

в документации порядок не гарантируется. Соответственно, и консистентность.

[sassa-nf.livejournal.com]

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

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


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

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