наука и жизнь

[juan_gandhi]

Scala:

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

Бля.

Comments

[sassa-nf.livejournal.com]

да, прикольно. каноничного порядка в сете нет.

[lomeo.livejournal.com]

Зависит от Set:

import scala.collection.immutable._

scala> List(HashSet(1, 2)).flatten == List(HashSet(2,1)).flatten
res0: Boolean = true

[sassa-nf.livejournal.com]

ну в HashSet есть каноничный порядок

[huzhepidarasa.livejournal.com]

Это, боюсь, пока на коллизию не напоролись.

scala> (563,983).hashCode
res1: Int = 8056365
scala> (961,751).hashCode
res2: Int = 8056365
scala> List(HashSet((563,983),(961,751))).flatten == List(HashSet((961,751),(563,983))).flatten
res3: Boolean = false

[ivan-gandhi.livejournal.com]

А блин...

Спасибо за пример.

[huzhepidarasa.livejournal.com]

Надо SortedSet, там все правильно получается.

[ivan-gandhi.livejournal.com]

Вот правильный сет! Спасибо за идейку!

Sorry, could not resist

[spamsink.livejournal.com]

И так будет с каждым, кто не пользуется C++ STL.

[sorhed.livejournal.com]

STL, конечно, неплохая библиотека. Её портит только вот это вот недоразумение, по ошибке считающееся языком программирования...

[spamsink.livejournal.com]

Да, С++ как будто синтаксические диабетики (no offense) придумывали - очень мало в нем было сахара до последнего времени.

[sorhed.livejournal.com]

Да тут не в сахаре дело, хрен с ним с сахаром. У людей просто нет вообще вкуса.

Вот как правильно надо было, с самого начала.

[spamsink.livejournal.com]

Кто-то должен был решить, что будет начало, а его и не было. Уж не единственный ли С++ современный массовый язык, который вырос из препроцессорной надстройки? Загадка: про что еще, кроме С++, можно сказать, что это is renowned for its size and utter lack of any master building plan?

[sorhed.livejournal.com]

Про Perl, например. Но Перл — хороший язык, там это возведено в искусство. А в C++ никакого искусства. :)

[spamsink.livejournal.com]

Я имел в виду http://en.wikipedia.org/wiki/Winchester_Mystery_House
It is reported to be haunted.

[a-jelly.livejournal.com]

Вроде бы Objective C тоже изначально было на препроцессоре.

[ivan-gandhi.livejournal.com]

Бьярне же, по-моему, что-то вроде шизофреника (ноу офенс). Вот матрички бы поумножать одним выражением... а про моноидальные категории это ему сложно.

[lomeo.livejournal.com]

См. реализацию вот этого класса и всё станет ясно:
https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/Set.scala#L92

[migmit.livejournal.com]

Никакая реализация не оправдывает косяк интерфейса.

[sassa-nf.livejournal.com]

а чё интерфейса?

обязан ли set перебирать одинаковые элементы в одинаковом порядке?

[glocka.livejournal.com]

Не обязан, в общем случае сравнение элементов вообще может быть не определено.

[ivan-gandhi.livejournal.com]

Перебирать не обязан, но equational axiom должна бы поддерживаться для "нормальных" случаев.

[migmit.livejournal.com]

Множества {1,2} и {2,1} совпадают. Аксиома экстенсиональности.

[huzhepidarasa.livejournal.com]

Кто-нибудь гарантирует, что List(Set(1,2))==List(Set(1,2)) (говоря по-простому, referential transparency)?

[lomeo.livejournal.com]

Множества-то как раз равны:

scala> Set(1,2) == Set(2,1)
res0: Boolean = true

Хотя принципиально, конечно, согласен.

[ivan-gandhi.livejournal.com]

Реализация - это или следствие не вполне адекватного понимания, или признание грустной (гнусной) реальности.

ага

[zhengxi.livejournal.com]

scala> Set(1,2).toString == Set(2,1).toString
res11: Boolean = false

scala> Set(1,2).toList == Set(2,1).toList
res12: Boolean = false

Re: ага

[ivan-gandhi.livejournal.com]

Да, вот именно.
Проблема.

[ralitza.livejournal.com]

для меня первые строки - медитация

последнее слово - сигнал к ее окончанию.

[cema.livejournal.com]

Плохая, негодная Scala!

[akalenuk.livejournal.com]

Хм. Вот не знаю скалы, но кажется правильней было бы как-то так:
List(Set(1,2), order_fun)

Просто так привести множество в список нельзя же. Нужен антирефлексивный порядок, а откуда его взять?

Кстати. "List(Set(1,2,2)).flatten == List(Set(2,1,1)).flatten" ?

[ivan-gandhi.livejournal.com]

false

[dvig-al.livejournal.com]

блин, читая переписку в рассылке, очень напомнило http://www.scala-lang.org/node/9021.

[ivan-gandhi.livejournal.com]

О как роскошно. Сидел ржал.

[dvig-al.livejournal.com]

Ну, позже баг пофиксили конечно, но тож скрежет был :)

[aamonster.livejournal.com]

Какая прелесть =)
И ведь ни один э... хороший человек не посоветовал написать x.compare(y)

[aamonster.livejournal.com]

... хотя всё ещё прелестней, ага.

[dvig-al.livejournal.com]

Да какой там. Если интересно - посмотрите тикет 4405 баг трекере скаловском.

[aamonster.livejournal.com]

Да, я потом продолжение прочитал - жуть.

[nponeccop.livejournal.com]

Prelude Data.Set> toList (fromList [1, 2]) == toList (fromList [2,1])
Loading package array-0.3.0.2 ... linking ... done.
Loading package containers-0.4.0.0 ... linking ... done.
True

хехе

[huzhepidarasa.livejournal.com]

Ну дык. Профессура со своими когомологиями. Не хотят как все нормальные люди, кувалдой ;-)

[sassa-nf.livejournal.com]

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

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

[nponeccop.livejournal.com]

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.

[sassa-nf.livejournal.com]

how do you prove equality by comparing two 100 points?

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

[thesz.livejournal.com]

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

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

[sassa-nf.livejournal.com]

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

[thesz.livejournal.com]

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

[sassa-nf.livejournal.com]

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

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

[sassa-nf.livejournal.com]

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

[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 одного и другого.

[eacher.livejournal.com]

$> ghci
GHCi, version 7.0.4: 
...
... done.
Prelude> :m Data.Set
Prelude Data.Set> let s1 = Data.Set.empty
...
... done.
Prelude Data.Set> let s2  = Data.Set.empty
Prelude Data.Set> let s11 = Data.Set.insert 1 s1
Prelude Data.Set> let s12 = Data.Set.insert 2 s11
Prelude Data.Set> let s21 = Data.Set.insert 2 s2
Prelude Data.Set> let s22 = Data.Set.insert 1 s21
Prelude Data.Set> s12 == s22
True

[sorhed.livejournal.com]

Анноит? Пиши камплейн репорть баг. :) Ведь баг же?

[sorhed.livejournal.com]

Впрочем, действительно, не баг. Нужен SortedSet. Ещё в джаве был LinkedHashSet для таких целей.

[eacher.livejournal.com]

>> Анноит?
ni razu

vidimo nado prodolzhit'...

fp : "odin i tot zhe argument - odin i tot zhe rezultat"

vyshe pokazano ravenstvo listov, nu dlya chistoty :

Prelude Data.Set> Data.Set.toList s12 == Data.Set.toList s22
True

point v tom, chto scala - javno ne "tort"

[sassa-nf.livejournal.com]

how do you prove equality by using two points?

[eacher.livejournal.com]

sorry, but...

>> Prelude Data.Set> s12 == s22
>> True

>> Prelude Data.Set> Data.Set.toList s12 == Data.Set.toList s22
>> True

or am i wrong? btw - i don't have any degree, sorry agn

[eacher.livejournal.com]

aah!

you say, that i took two concrete sets and proclaim that ALL sets will be with same behavour. and that IT is not true: kvantor vseobwnosti nuzhen

i give up.

[thesz.livejournal.com]

Там по построению так. Посмотрите на внутренности Data.Set.Set.

[sassa-nf.livejournal.com]

да, замечательно!

[eacher.livejournal.com]

da, spasibo!

a to ja uzh hotel u uvazhaemogo sassa_nf sprosit' skol'ko i kakih testov nuznho progonjat', chtob ne sil'no volnovat'sja za rezul'tat

a tut i ego komment kak raz k stati. spasibo i emu - za nauku :)