Можно ли выполнить поиск на графике, построенном по стратегии связывания узлов?

Question

Стратегия привязки к узлу может быть использована для построения графиков, например, используя простой двусторонний граф в качестве примера:

data Node = Node Node Node

-- a - b
-- |   |
-- c - d
square = a where
    a = Node b c
    b = Node a d
    c = Node a d
    d = Node b c

Эта стратегия довольно элегантна, но я не смог найти способ использовать ее без меток Int. Например, как я могу написать функцию, которая подсчитывает количество узлов на square значение?

countNodes :: Node -> Int
countNodes = ... ??? ...

main = print $ countNodes square
-- output: 4

Answer 1

Вам действительно нужна какая-то маркировка, потому что внутри Haskell нет способа отличить узлы как написанные. Действительно, когда компилятор Haskell видит

square = a where
    a = Node b c
    b = Node a d
    c = Node a d
    d = Node b c

совершенно законно отметить, что a а также d, так же как b а также c, определены равными выражениями, и реализовать каждую пару как один базовый объект. (Это называется устранением общего выражения выражений.)

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

Answer 2

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

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

a - b
|   |
c - d

от

a - b
| /
c

или же

a - b - c
|       |
d - e - f

или даже

a - b                 a -
|   |   or heck even  |  |
- - -                  --

Каждое локальное наблюдение - это узел с двумя ребрами неотличимых объектов.

Если вы добавите идентификатор, такой как int, к краям или узлам, или вы обманываете и крадете идентификатор (например, адрес, но в Haskell это не является детерминированным из-за GC), вы можете использовать эта информация выводит равенство или неравенство.

Answer 3

Вы можете наблюдать участие в IO используя, например, data-reify:

{-# LANGUAGE TypeFamilies #-}
import Data.Reify

data Node = Node Node Node
data NodeId s = NodeId s s

instance MuRef Node where
    type DeRef Node = NodeId
    mapDeRef f (Node n1 n2) = NodeId <$> f n1 <*> f n2

Реализация countNodes сейчас тривиально (но учтите, что в IO!)

countNodes :: Node -> IO Int
countNodes n = do
    Graph nodes root <- reifyGraph n
    return $ length nodes

Ваш пример:

square :: Node
square = a where
    a = Node b c
    b = Node a d
    c = Node a d
    d = Node b c

*Main> print =<< countNodes square
4