I would like to learn how to make graphs and perform some local operations on them in Haskell, but the question is not specific to Haskell, and instead of graphs we may consider doubly linked lists.
Question: What would be an idiomatic or recommended way to implement a doubly linked list (or other doubly linked or circular data structure) and operations on it in a language that mainly supports and advocates for immutable data structures (Haskell, Clojure, etc.)? In particular, how to use in-place updates, which are formally forbidden by the language?
I can easily imagine that if some local operation is performed on a doubly linked list (if an item is inserted, for example), there may be no need to copy the entire list immediately due to the laziness of the language. However, since the list is doubly linked, if it is modified in one place, none of the old nodes can be used in the new version of the list, and they would need to be somehow marked, copied, garbage-collected sooner or later. Obviously these are redundant operations if only the updated copy of the list shall be used, but they would add an "overhead" proportional to the size of the list.
Does this mean that for such tasks immutable data is simply inappropriate, and functional declarative languages without "native" support for mutable data are not as good as imperative ones? Or, is there some tricky workaround?
P.S. I have found some articles and presentations on this subject in the Internet but had hard time following them, while i think that the answer to this question should not take more than one paragraph and maybe a diagram... I mean, if there is no "functional" solution to this problem, the answer probably is "use C". If there is one, then how complicated can it be?
"Data structures in functional programming". My specific question about using in-place updates instead of inefficient alternatives is not discussed there.
"Internal Mutation of Persistent Data Structures". There the emphasis seems to be on low-level implementation in an unspecified language, while my question is about the right choice of a language (functional or otherwise) and about possible idiomatic solutions in functional languages.
Purely functional programming languages allow many algorithms to be expressed very concisely, but there are a few algorithms in which in-place updatable state seems to play a crucial role. For these algorithms, purely-functional languages, which lack updatable state, appear to be inherently inefficient ([Ponder, McGeer and Ng, 1988]).
-- John Launchbury and Simon Peyton Jones, Lazy functional state threads (1994), also John Launchbury and Simon Peyton Jones, State in Haskell (1995). These papers introduce
ST monadic type constructor in Haskell.