Reputation
424
Next privilege 500 Rep.
Access review queues
Badges
4 13
Newest
 Yearling
Impact
~6k people reached

  • 0 posts edited
  • 0 helpful flags
  • 22 votes cast
Jan
5
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
My current solution (in Haskell) is to use a dictionary (Map, IntMap, or HashMap) as a storage and to make nodes contain IDs of the linked nodes. "All problems in computer science can be solved by another level of indirection."
Dec
31
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
It looks like a similar problem with arrays is addressed by diffarray package that implements DiffArray type. Looking at the source of diffarray package, i see 91 occurrences of unsafePerformIO. It looks like the answer to my question is "yes, no, purely functional languages with immutable data are not appropriate for implementing algorithms that normally rely on in-place updates".
Dec
30
revised Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
add publication years for two quoted papers
Dec
30
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
This paper looks promising: Lazy depth-first search and linear graph algorithms in Haskell (1994), by David King and John Launchbury.
Dec
27
revised Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
add relevant quotations section
Dec
24
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
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.)
Dec
24
suggested rejected edit on Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
Dec
24
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
@Giorgio, is it possible to use Haskell's ST with STM to have both concurrency and disposable state?
Dec
19
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
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.
Dec
18
revised Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
add a link to a related question
Dec
18
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
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.
Dec
18
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
@9000, i have tried to learn about lenses, but i do not see how they answer my question. They seem to be functional "getters" and "setters", where "setters" make copies. For example, if you build a 1000-element list of integers, then modify its last element (through a lens or not -- i do not see why it should make a difference), and then calculate and print out the sum of the elements of the new list, wouldn't the whole list be copied first?
Dec
18
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
@Giorgio, i do not get very well the difference, but i think that in my case it can be viewed as both. In fact, my graphs are not really graphs, but more like interaction nets.
Dec
17
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
I have a very clear idea about the graph rewriting system i want to program, and i do not think i would have a major difficulty programming it in C or in other imperative language with mutable data, but i do not see yet how to do it in a functional language. I will try to learn about lenses.
Dec
17
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
@Giorgio, not yet, thanks for the link. Did they program Clean in Haskell, by any chance? ;)
Dec
16
revised Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
fix atypo
Dec
16
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
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.
Dec
16
comment Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
Thanks for the reference. I've found his thesis.
Dec
16
awarded  Yearling
Dec
16
asked Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data