Pertanyaan Apakah mungkin untuk melakukan pencarian pada grafik yang dibangun dengan strategi mengikat-simpul?


Strategi mengikat-simpul dapat digunakan untuk membuat grafik seperti, menggunakan grafik dua-jari sederhana sebagai contoh:

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

Strategi itu agak elegan, tetapi saya tidak dapat menemukan cara untuk menggunakannya tanpa label Int. Sebagai contoh, bagaimana saya bisa menulis fungsi yang menghitung jumlah node di square nilai?

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

main = print $ countNodes square
-- output: 4

5
2017-10-15 22:47


asal


Jawaban:


Anda memang membutuhkan semacam pelabelan, karena dari dalam Haskell tidak ada cara untuk membedakan simpul yang tertulis. Memang, ketika kompilator Haskell melihat

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

ini sepenuhnya legal untuk itu untuk dicatat itu a dan d, sebaik b dan c, ditentukan oleh persamaan yang sama, dan untuk menerapkan setiap pasangan sebagai satu objek yang mendasarinya. (Ini disebut Eliminasi Subkunci Umum.)

Bahkan, itu bahkan legal untuk mengidentifikasi keempatnya, meskipun saya meragukan kompiler benar-benar melakukan itu karena perlu menyadari bahwa mereka memiliki "denotasi" semantik yang sama, menjadi semua cara yang berbeda untuk menulis pohon yang tak terbatas. t = Node t t = Node (Node ... ...) (Node ... ...) - Dari sudut pandang semantik denotasi itulah hanya nilai datatype Anda yang tidak mengandung pantat.


4
2017-10-15 23:21



Secara umum Anda harus dapat membandingkan sebuah simpul untuk persamaan dengan nodus yang diamati sebelumnya untuk menentukan Anda infact mengunjungi kembali sebagian dari grafik daripada telah mendeklarasikan ke dalam subgraph struktur yang sama. Ini terlepas dari bagaimana Anda secara sintaksis mengekspresikan node Anda atau dalam bahasa apa.

Misalnya, menggunakan representasi yang disediakan, tidak mungkin membedakan grafik

a - b
|   |
c - d

dari

a - b
| /
c

atau

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

atau bahkan

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

Setiap pengamatan lokal adalah sebuah simpul dengan dua sisi untuk entitas yang tidak dapat dibedakan.

Jika Anda menambahkan pengenal, seperti int, ke tepi atau simpul, atau Anda menipu dan mencuri pengenal (seperti alamat, tetapi di Haskell ini tidak deterministik karena GC), maka Anda mungkin dapat menggunakan informasi ini untuk menyimpulkan persamaan atau ketidaksetaraan.


4
2017-10-15 23:19



Anda dapat mengamati berbagi dalam IO, menggunakan misalnya 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

Implementasi dari countNodes sekarang sepele (tetapi perhatikan bahwa itu ada di dalamnya IO!)

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

Contoh Anda:

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

1
2017-10-26 02:30