Pemrograman fungsional dan algoritma stateful

Saya belajar pemrograman fungsional dengan Haskell . Sementara itu saya sedang belajar teori Automata dan karena keduanya tampaknya cocok bersama saya sedang menulis perpustakaan kecil untuk bermain dengan automata.

Inilah masalah yang membuat saya mengajukan pertanyaan. Saat mempelajari cara untuk mengevaluasi jangkauan suatu negara saya mendapat ide bahwa algoritma rekursif sederhana akan sangat tidak efisien, karena beberapa jalur mungkin berbagi beberapa keadaan dan saya mungkin akhirnya mengevaluasinya lebih dari sekali.

Sebagai contoh, di sini, mengevaluasi reachability dari g dari sebuah , aku harus mengecualikan f baik saat memeriksa jalur melalui d dan c :

Jadi ide saya adalah suatu algoritma yang bekerja secara paralel pada banyak jalur dan memperbarui catatan bersama dari negara yang dikecualikan mungkin bagus, tapi itu terlalu banyak bagi saya.

Saya telah melihat bahwa dalam beberapa kasus rekursi sederhana seseorang dapat menyatakan status sebagai argumen, dan itulah yang harus saya lakukan di sini, karena saya meneruskan daftar status yang telah saya lalui untuk menghindari loop. Tetapi apakah ada cara untuk melewati daftar itu juga mundur, seperti mengembalikannya dalam tuple bersama dengan hasil boolean dari canReachfungsi saya ? (Meskipun ini terasa agak dipaksakan)

Selain keabsahan contoh kasus saya , teknik apa yang tersedia untuk menyelesaikan masalah semacam ini? Saya merasa ini harus cukup umum sehingga harus ada solusi seperti apa yang terjadi dengan fold*atau map.

Sejauh ini, membaca learnyouahaskell.com saya belum menemukannya, tetapi anggap saya belum menyentuh monad.

( jika tertarik, saya memposting kode saya di codereview )

Pemrograman fungsional tidak menghilangkan status. Itu hanya membuatnya eksplisit! Meskipun benar bahwa fungsi seperti peta akan sering "mengurai" struktur data "bersama", jika semua yang ingin Anda lakukan adalah menulis algoritma reachability maka itu hanya masalah melacak node apa yang sudah Anda kunjungi:

import qualified Data.Set as S
data Node = Node Int [Node] deriving (Show)

-- Receives a root node, returns a list of the node keyss visited in a depth-first search
dfs :: Node -> [Int]
dfs x = fst (dfs' (x, S.empty))

-- This worker function keeps track of a set of already-visited nodes to ignore.
dfs' :: (Node, S.Set Int) -> ([Int], S.Set Int)
dfs' (node@(Node k ns), s )
  | k  `S.member` s = ([], s)
  | otherwise =
    let (childtrees, s') = loopChildren ns (S.insert k s) in
    (k:(concat childtrees), s')

--This function could probably be implemented as just a fold but Im lazy today...
loopChildren :: [Node] -> S.Set Int -> ([[Int]], S.Set Int)
loopChildren []  s = ([], s)
loopChildren (n:ns) s =
  let (xs, s') = dfs' (n, s) in
  let (xss, s'') = loopChildren ns s' in
  (xs:xss, s'')

na = Node 1 [nb, nc, nd]
nb = Node 2 [ne]
nc = Node 3 [ne, nf]
nd = Node 4 [nf]
ne = Node 5 [ng]
nf = Node 6 []
ng = Node 7 []

main = print $ dfs na -- [1,2,5,7,3,6,4]

Sekarang, saya harus mengakui bahwa melacak semua keadaan ini dengan tangan cukup menjengkelkan dan rawan kesalahan (mudah digunakan s 'bukan s' ', mudah untuk melewati yang sama' ke lebih dari satu perhitungan ...) . Di sinilah monad masuk: mereka tidak menambahkan apa pun yang belum bisa Anda lakukan sebelumnya tetapi mereka membiarkan Anda melewati variabel keadaan sekitar secara implisit dan antarmuka menjamin bahwa hal itu terjadi dalam cara single-threaded.

Sunting: Saya akan berusaha memberikan alasan lebih banyak tentang apa yang saya lakukan sekarang: pertama-tama, alih-alih hanya menguji tingkat pencapaian, saya mengode pencarian mendalam-pertama. Implementasinya akan terlihat hampir sama tetapi debugging terlihat sedikit lebih baik.

Dalam bahasa yang stateful, DFS akan terlihat seperti ini:

visited = set()  #mutable state
visitlist = []   #mutable state
def dfs(node):
   if isMember(node, visited):
       //do nothing
   else:
       visited[node.key] = true           
       visitlist.append(node.key)
       for child in node.children:
         dfs(child)

Sekarang kita perlu menemukan cara untuk menyingkirkan keadaan yang bisa berubah. Pertama-tama kita menyingkirkan variabel "daftar kunjungan" dengan membuat df mengembalikannya sebagai ganti batal:

visited = set()  #mutable state
def dfs(node):
   if isMember(node, visited):
       return []
   else:
       visited[node.key] = true
       return [node.key] + concat(map(dfs, node.children))

Dan sekarang sampai pada bagian yang sulit: menyingkirkan variabel "yang dikunjungi". Trik dasarnya adalah dengan menggunakan konvensi di mana kita melewati negara sebagai parameter tambahan untuk fungsi yang membutuhkannya dan meminta fungsi-fungsi mengembalikan versi baru negara sebagai nilai pengembalian tambahan jika mereka ingin memodifikasinya.

let increment_state s = s+1 in
let extract_state s = (s, 0) in

let s0 = 0 in
let s1 = increment_state s0 in
let s2 = increment_state s1 in
let (x, s3) = extract_state s2 in
-- and so on...

Untuk menerapkan pola ini ke dfs, kita perlu mengubahnya untuk menerima set "dikunjungi" sebagai parameter tambahan dan untuk mengembalikan versi terbaru dari "dikunjungi" sebagai nilai pengembalian ekstra. Selain itu, kita perlu menulis ulang kode sehingga kita selalu meneruskan versi "terbaru" dari array yang "dikunjungi":

def dfs(node, visited1):
   if isMember(node, visited1):
       return ([], visited1) #return the old state because we dont want to  change it
   else:
       curr_visited = insert(node.key, visited1) #immutable update, with a new variable for the new value
       childtrees = []
       for child in node.children:
          (ct, curr_visited) = dfs(child, curr_visited)
          child_trees.append(ct)
       return ([node.key] + concat(childTrees), curr_visited)

Versi Haskell cukup banyak melakukan apa yang saya lakukan di sini, kecuali bahwa itu berjalan sepanjang jalan dan menggunakan fungsi rekursif dalam bukannya variabel "curr_visited" dan "childtrees" yang bisa diubah.

Sedangkan untuk monad, apa yang mereka capai pada dasarnya adalah secara implisit mengedarkan "curr_visited", bukannya memaksa Anda melakukannya dengan tangan. Ini tidak hanya menghapus kekacauan dari kode, tetapi juga mencegah Anda melakukan kesalahan, seperti keadaan forking (meneruskan "kunjungan" yang sama ke dua panggilan berikutnya alih-alih mengubah status).

Inilah jawaban sederhana yang diandalkan mapConcat.

 mapConcat :: (a -> [b]) -> [a] -> [b]
 -- mapConcat is in the std libs, mapConcat = concat . map
 type Path = []

 isReachable :: a -> Auto a -> a -> [Path a]
 isReachable to auto from | to == from = [[]]
 isReachable to auto from | otherwise = 
    map (from:) . mapConcat (isReachable to auto) $ neighbors auto from

Di mana neighborsmengembalikan negara yang segera terhubung ke suatu negara. Ini mengembalikan serangkaian jalur.