Reputation
429
Next privilege 500 Rep.
Access review queues
Badges
4 13
Newest
 Yearling
Impact
~7k 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
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
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
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
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
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.
Jul
26
comment Haskell syntax for type definitions: why the equality sign?
I have realised that if instead of =, the type definition was using ::=, it would look like a rule of a grammar definition in Backus–Naur Form, where type constructors are like expression variables (nonterminal symbols), and value constructors are like literal characters (terminal symbols).
Feb
12
comment A pattern to “atomically” update a pair of objects
Probably instead of Account there should be Bank, as there are much fewer banks than accounts. Then each bank would have to manage its accounts.
Feb
12
comment A pattern to “atomically” update a pair of objects
This is just a general idea, this exact code would not be very efficient, i suppose.
Jan
27
comment A pattern to “atomically” update a pair of objects
@Kaerber, but the Updates defined in Transaction can only modify Accounts through their public methods, so what public methods would the Accounts have?
Jan
27
comment A pattern to “atomically” update a pair of objects
Which methods would be exposed as public? How a method sent to one Account can change another Account?
Jan
27
comment A pattern to “atomically” update a pair of objects
Could you tell please how and where UpdateSource and UpdateDestiantion are defined?
Jan
27
comment A pattern to “atomically” update a pair of objects
I am only playing with OOP in Racket. The question is not about data integrity, but about the class interface: it does not seem possible to me to expose somehow a single public method (or maybe this is not how it should be done?) to update both states without exposing public methods for updating just one state. I suspect the answer can be very language-specific, but if i see the keywords, maybe i'll be able to search for it myself. If this is not clear, maybe i'll add an example later.