Блог

Главная - Вопросы по программированию - Python-«is»-подобный оператор равенства для Haskell / GHC

Python-«is»-подобный оператор равенства для Haskell / GHC

#haskell #reference #ghc

#haskell #ссылка #ghc

Вопрос:

Существует ли «небезопасное» расширение, специфичное для GHC, для запроса, указывают ли две ссылки Haskell на одно и то же местоположение?

Я знаю, что это может нарушить ссылочную прозрачность, если не используется должным образом. Но вреда должно быть немного (если только я чего-то не упустил), если он используется очень осторожно, как средство оптимизации путем кратковременного рекурсивного (или дорогостоящего) обхода данных, например, для реализации оптимизированного Eq экземпляра, например:

 instance Eq ComplexTree where
   a == b  = (a `unsafeSameRef` b) || (a `deepCompare` b)

предоставление deepCompare гарантированно будет истинным, если unsafeSameRef будет принято значение true (но не обязательно наоборот).

РЕДАКТИРОВАТЬ / PS: Благодаря ответу, указывающему на System.Mem.StableName , я смог также найти документ, расширяющий менеджер хранилища: слабые указатели и стабильные имена в Haskell, в котором, как оказалось, эта самая проблема решалась уже более 10 лет назад…

Комментарии:

1. Я часто хотел именно эту функцию, именно для этой цели: более быстрой проверки равенства.

2. @FUZxxl: если он спрашивает об этом (а вопрос совершенно ясно указывает на то, что он знает, о чем говорит), то, очевидно, ему это нужно. Обвинять OP в выполнении преждевременной оптимизации, не зная о его проблеме, немного … преждевременно.

3. @Роман Чепляка: Извините. Я не хотел, чтобы комментарий был грубым, поэтому я удалил его.

4. 1 за идеально заданный вопрос. Однако я бы доверил компилятору автоматически выполнить эту оптимизацию за меня. Не так ли?

5. @Tarrasch: нет, есть много причин не делать этого. В частности, равенство не совсем рефлексивно, как указал Леннарт Аугустссон в своем ответе.

Ответ №1:

System.Mem.StableName от GHC решает именно эту проблему.

Ответ №2:

Есть одна ловушка, о которой нужно знать:

Равенство указателей может изменить строгость. Т.Е. вы можете получить равенство указателей, говорящее True, когда на самом деле реальный тест на равенство был бы зациклен, например, из-за круговой структуры. Таким образом, равенство указателей разрушает семантику (но вы это знали).

Ответ №3:

Я думаю, что здесь могут помочь стабильные указателиhttp://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Foreign-StablePtr.html Возможно, это то решение, которое вы ищете:

 import Foreign.StablePtr (newStablePtr, freeStablePtr)
import System.IO.Unsafe (unsafePerformIO)

unsafeSameRef :: a -> a -> Bool
unsafeSameRef x y = unsafePerformIO $ do
    a <- newStablePtr x
    b <- newStablePtr y
    let z = a == b
    freeStablePtr a
    freeStablePtr b
    return z;

Комментарии:

1. StableName будет вести себя так, как вы предлагаете. StablePtr не выполняет никакой дедупликации / совместного использования. Он вообще не проходит через хэш-таблицу или что-то подобное.

2. Ах, спасибо за обновление. Я вижу недостатки StablePtr в этом использовании.

Ответ №4:

В GHC есть unpackClosure# .Простой, со следующим типом:

 unpackClosure# :: a -> (# Addr#,Array# b,ByteArray# #)

Используя это, вы могли бы создать что-то вроде:

 {-# LANGUAGE MagicHash, UnboxedTuples #-} 
import GHC.Prim

eq a b = case unpackClosure# a of 
    (# a1,a2,a3 #) -> case unpackClosure# b of 
        (# b1,b2,b3 #) -> eqAddr# a1 b1

И в том же пакете есть интересно названный reallyUnsafePtrEquality# тип

 reallyUnsafePtrEquality#  :: a -> a -> Int#

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

Комментарии:

1. @yatima2975: Я задал вопрос о том, что reallyUnsafePtrEquality# делает в канале #ghc. Ответ был таким: FUZxxl: (…) но он принимает два объекта и сообщает вам, совпадают ли их адреса в памяти (=> это один и тот же объект) . Вы даже можете попробовать в ghci! Но тогда, вы видите, в чем проблема: это работает только в некоторых случаях.

2. Он возвращает 0 # для неравенства и 1 # для равенства. Но обратите внимание, что могут быть как ложноотрицательные, так и ложноположительные результаты.

3. @FYZxxl ложные отрицания и false positives…in другими словами… это бесполезно?

4. @FUZxxl — Спасибо, что выяснили это! Ложноотрицательные результаты не так уж плохи (для задающего вопрос), поскольку ему просто нужно будет выполнить «обычное» сравнение, но возможность ложных срабатываний делает reallyUnsafePtrEquality совершенно бесполезным для этой проблемы. Предположительно, положительные результаты возникают из-за того, что объекты перемещаются с помощью GC?

5. @Dan Тогда они должны переименовать его reallyUselessPtrEquality# 🙂