10

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?


Related questions


Relevant quotations

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.

5

There could be other efficient immutable data structures that fit your particular task, but are not as general as a doubly-linked list (which is unfortunately prone to concurrent modification bugs due to its mutability). If you specify your problem more narrowly, such a structure can probably be found.

The general answer for (relatively) economic traversing of immutable structures is lenses. The idea is that you can keep just enough information to reconstruct a modified immutable structure from its unmodified parts and the currently modified piece, and navigate over it to a neighboring node.

Another useful structure is a zipper. (The funny part is that the type signature for a lens zipper is a school-math derivative of a type signature of the structure.)

Here are a few links.

  • 1
    depending on what is needed a zipper might also be useful – jk. Dec 16 '15 at 17:06
  • To specify my problem more narrowly, suppose i want to program a graph rewriting system, for example a lambda calculus evaluator based on graph rewriting. – Alexey Dec 16 '15 at 21:47
  • 1
    @Alexey: Are you familiar with the work of the Clean people on graph rewriting? wiki.clean.cs.ru.nl/… – Giorgio Dec 16 '15 at 22:46
  • 1
    @Alexey: Not that I know: Clean is a cousin of Haskell that was developed on its own. It also has a different mechanism for dealing with side-effects (AFAIK it is called unique types). On the other hand, the developers have worked a lot with graph rewriting. So they could be among the best people who know both about graph rewriting and functional programming. – Giorgio Dec 17 '15 at 10:51
  • 1
    I agree that a zipper seems to solve the problem with a doubly linked list or a tree if i want to navigate it and modify at the spot i am currently at, but it is not clear what to do if i want to focus on several spots simultaneously and, for example, swap two element in two places far apart. It is even less clear if is can be used with "circular" structures. – Alexey Dec 18 '15 at 21:23
2

Haskell does not prevent the use of mutable data structures. They are heavily discouraged and made harder to use because of the fact that the parts of code that use them must eventually return an IO action (which must eventually be bound into the IO action that is returned by the main function), but that does not make it impossible to use such structures if you really need them.

I would suggest investigating the use of software transactional memory as a way forward. As well as providing an efficient way to implement mutable structures, it also provides very useful guarantees for thread-safety. See the module description at https://hackage.haskell.org/package/stm and the wiki overview at https://wiki.haskell.org/Software_transactional_memory .

  • Thanks, i will try to learn about STM. It looks like there are more methods in Haskell to have mutability and state (i've stumbles upon MVar, State, ST), so i'll need to figure out their differences and intended uses. – Alexey Dec 19 '15 at 13:36
  • @Alexey: Good point regarding ST, IMO it should be mentioned in the answer because it allows to run a stateful computation, then throw away the state and extract the result as a pure value. – Giorgio Dec 19 '15 at 13:38
  • @Giorgio, is it possible to use Haskell's ST with STM to have both concurrency and disposable state? – Alexey Dec 24 '15 at 11:17
  • Just one more terminology suggestion: the composed main IO action is not "returned by the main function" but is assigned to main variable. :) (main does not even hold a function.) – Alexey Dec 24 '15 at 21:31
  • I see your point, but still "variable" has a connotation in most people's minds as a simple value, rather than a process that produces a value, and main is clearly better thought of as the latter rather than the former. The change you suggest, while clearly technically correct, has the potential to confuse those unfamiliar with the subject. – Jules Dec 24 '15 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.