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

Ответ 1

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

$ghc-7.8.2 -ddump-simple wtmpf-file13495.hs

Соответствующее различие заключается в том, что первая версия (без [email protected](...)) имеет

                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)

где повторное использование node с этим as-pattern делает только

                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 vs all.

... без оптимизаций, то есть. Версии расширяются, когда я включаю -O2. Но я не могу понять, как будет отличаться производительность.

Ответ 2

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

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, которая предоставляет глубину базового дерева, поддерживающего набор, то вы не можете гарантировать, что значения глубины равны, даже если сборы сравниваются равными.

Вот видео великого Филиппа Вадлера, реализующего жизнь и на сцене, что многие полезные отношения не сохраняют равенство (начиная с 42 минут).

Изменить: пример из 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.

Ответ 3

Мои два цента... возможно, даже не об исходном вопросе:

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

treeInsert x [email protected](Node a left right) =
  case compare x a of
    EQ -> ...
    LT -> ...
    GT -> ...

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

Ответ 4

Ответ кажется неправильным. Я просто оставлю это здесь, для справки...

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

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

Ответ 5

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

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

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

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

Прямая реализация идиомы 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, но на языке оригинала не выражается.

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

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