Должен ли я избегать строительства в Haskell?

Question

Хотя чтение пропущено из Haskell for Great Good я нашел следующую ситуацию:

treeInsert :: (Ord a) => a -> Tree a -> Tree a 
treeInsert x EmptyTree = singleton x 
treeInsert x (Node a left right) 
    | x == a = Node x left right 
    | x < a = Node a (treeInsert x left) right 
    | x > a = Node a left (treeInsert x right) 

Не было бы лучше для производительности, если мы просто повторно данное дерево когда x == a?

treeInsert :: (Ord a) => a -> Tree a -> Tree a 
treeInsert x EmptyTree = singleton x 
treeInsert x all@(Node a left right) 
    | x == a = all 
    | x < a = Node a (treeInsert x left) right 
    | otherwise = Node a left (treeInsert x right) 

В реальной кодировке, что мне делать? Существуют ли какие-либо недостатки при возврате того же?

Answer 1

Давайте посмотрим на ядро! (Без оптимизаций здесь)

$ GHC-7.8.2 -ddump-Симпл wtmpf-file13495.hs

Соответствующая разница в том, что первая версия (без all@(...)) имеет

   case GHC.Classes.> @ a_aUH $dOrd_aUV eta_B2 a1_aBQ 
       of _ [Occ=Dead] { 
        GHC.Types.False -> 
        Control.Exception.Base.patError 
         @ (TreeInsert.Tree a_aUH) 
         "wtmpf-file13495.hs:(9,1)-(13,45)|function treeInsert"#; 
        GHC.Types.True -> 
        TreeInsert.Node 
         @ a_aUH 
         a1_aBQ 
         left_aBR 
         (TreeInsert.treeInsert @ a_aUH $dOrd_aUV eta_B2 right_aBS) 

, где повторное использование узла с этим как-шаблон делает только

   TreeInsert.Node 
        @ a_aUI 
        a1_aBR 
        left_aBS 
        (TreeInsert.treeInsert @ a_aUI $dOrd_aUW eta_B2 right_aBT); 

Это предотвращенная проверка, которая может значительно повлиять на производительность.

Однако, эта разница фактически не имеет отношения к шаблону as-pattern. Просто потому, что ваш первый фрагмент использует защитник x > a, который не является тривиальным. Второй использует otherwise, который оптимизирован.

Если вы измените первый фрагмент на

treeInsert :: (Ord a) => a -> Tree a -> Tree a 
treeInsert x EmptyTree = singleton x 
treeInsert x (Node a left right) 
    | x == a  = Node x left right 
    | x < a  = Node a (treeInsert x left) right 
    | otherwise = Node a left (treeInsert x right) 

то разница сводится к

 GHC.Types.True -> TreeInsert.Node @ a_aUH a1_aBQ left_aBR right_aBS 

против

 GHC.Types.True -> wild_Xa 

которая действительно только разница Node x left right против all.

... без оптимизаций, то есть. The versions diverge further when I turn on -O2. Но я не могу понять, как будет отличаться производительность.

Answer 2

ответ похоже неправильный. Я просто оставить его здесь, для справки ...

---

С вашей второй функцией вы не создавать новый узел, потому что компилятор не может действительно понять равенство (== только некоторая функция.) Если вы измените первый вариант в

-- version C 
treeInsert :: (Ord a) => a -> Tree a -> Tree a 
treeInsert x EmptyTree = singleton x 
treeInsert x (Node a left right) 
    | x == a = Node a left right -- Difference here! Changed x to a. 
    | x < a = Node a (treeInsert x left) right 
    | x > a = Node a left (treeInsert x right) 

компилятор, вероятно, будет в состоянии сделать общую ликвидацию подвыражения, потому что оптимизатор будет в состоянии видеть, что Node a left right такое же, как Node a left right.

С другой стороны, я сомневаюсь, что компилятор может вывести из a == x, что Node a left right - это то же самое, что и Node x left right.

Итак, я уверен, что под -O2 версия B и версия C одинаковы, но версия A, вероятно, медленнее, потому что она создает дополнительную копию экземпляра a == x.

Answer 3

В реальной кодировке, что мне делать? Существуют ли какие-либо недостатки при возврате того же?

a == bделает не гарантии того, что f a == f b для всех функций f. Итак, вы, , могут должны возвращать новый объект, даже если они сравнивают одинаковые.

Другими словами, это может не быть возможным, чтобы изменить Node x left right к Node a left right или all когда a == x независимо от роста производительности.

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

newtype ValMeta a b = ValMeta (a, b) -- value, along with meta data 
    deriving (Show) 

instance Eq a => Eq (ValMeta a b) where 
    -- equality only compares values, ignores meta data 
    ValMeta (a, b) == ValMeta (a', b') = a == a' 

Дело Eq type-classтолько говорит, что вы можете сравнить значение равенства. Это ничего не гарантирует.

Реальный пример, где a == b не гарантирует, что f a == f b когда вы поддерживаете Set уникальных значений в пределах самобалансирующегося дерева. Самобалансирующееся дерево (например, дерево Red-Black) имеет некоторые гарантии относительно структуры дерева, но фактическая глубина и структура зависят от того, что данные были добавлены или удалены из набора.

Теперь, когда вы сравниваете 2 набора для равенства, вы хотите сравнить, что значения внутри набора равны, а не то, что базовые деревья имеют одинаковую точную структуру. Но если у вас есть функция, такая как depth, которая предоставляет глубину базового дерева, поддерживающего набор, то вы не можете гарантировать, что глубины равны, даже если сборы сравниваются равными.

Here is a video of great Philip Wadler realizing live and on-stage that many useful relations do not preserve equality (начиная с 42 минут).

Edit: Пример из GHC где a == b не означает f a == f b:

\> import Data.Set 
\> let a = fromList [1, 2, 3, 4, 5, 10, 9, 8, 7, 6] 
\> let b = fromList [1..10] 
\> let f = showTree 
\> a == b 
True 
\> f a == f b 
False 

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

Так что если у вас есть функция, которая возвращает емкость хэш-таблицы, она может возвращать разные значения для хэш-таблиц a и b, хотя a == b.

Answer 4

Мои два цента ... возможно, даже не про оригинальный вопрос:

Вместо того чтобы писать охранников с x < a и x == a, я бы соответствовать compare a b против LT, EQ и GT, например:

treeInsert x all@(Node a left right) = 
    case compare x a of 
    EQ -> ... 
    LT -> ... 
    GT -> ... 

Я бы это сделал, особенно если x и a могут быть сложными структурами данных, поскольку такой тест, как x < a, может быть дорогим.

Answer 5

Ну, если первый случай использовал a вместо x следующим образом, то есть, по крайней мере, вероятность того, что GHC устранит выделение нового узла посредством устранения общего подвыражения.

treeInsert x (Node a left right) 
    | x == a = Node a left right 

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

В мире ML, довольно идиоматический способ избежать этого - выбросить исключение KeyAlreadyExists, а затем поймать это исключение в функции вставки верхнего уровня и вернуть исходное дерево. Это приведет к тому, что стек будет размотан, вместо того, чтобы выделять любую из Node s в кучу.

Прямая реализация идиомы ML в принципе не имеет значения в Haskell по уважительным причинам. Если избегать этого дублирования, самое простое и, возможно, самое лучшее, что нужно сделать, это проверить, содержит ли дерево ключ, прежде чем вставлять его.

Недостаток этого подхода, по сравнению с прямой вставкой Haskell или идиомой ML, заключается в том, что он включает в себя два обхода пути вместо одного. Теперь, вот, не дублируя, однопроходные вставки можно реализовать в Haskell:

treeInsert :: Ord a => a -> Tree a -> Tree a 
treeInsert x original_tree = result_tree 
    where 
    (result_tree, new_tree) = loop x original_tree 

    loop x EmptyTree = (new_tree, singleton x) 
    loop x (Node a left right) = 
     case compare x a of 
     LT -> let (res, new_left) = loop x left 
       in (res, Node a new_left right) 
     EQ -> (original_tree, error "unreachable") 
     GT -> let (res, new_right) = loop x right 
       in (res, Node a left new_right) 

Однако старые версии GHC (примерно 7-10 лет назад) не справиться с таким родом рекурсии через ленивый пар результатов очень эффективно, и, по моему опыту, проверка перед вставкой, скорее всего, будет лучше. Я был бы немного удивлен, если бы это наблюдение действительно изменилось в контексте более поздних версий GHC.

Конечно, можно представить себе функцию, которая напрямую конструирует (но не возвращает) новый путь для дерева и решает вернуть новый путь или исходный путь, как только будет известно, существует ли этот элемент уже. (Новый путь немедленно станет мусором, если он не будет возвращен.) Это соответствует основным принципам среды выполнения GHC, но на самом языке не выражается.

Конечно, любая полностью не дублирующая функция вставки в ленивой структуре данных будет иметь разные свойства строгости, чем простая дублирующая вставка. Поэтому, независимо от техники реализации, они отличаются друг от друга, если речь идет о лени.

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