[Haskell-cafe] Re: Doubly-linked zipper list w/ insert implementation
Justin Bailey wrote: The other day I decided to implement a ring buffer with a current element (i.e. a doubly-linked zipper list). [...] p.s. The original motivation for writing this was to model cellular automata. The CA world is circular, so that got me thinking about a structure that made connecting the ends easy to do. Note that depending on your concrete setting, you may not need a fancy ring structure for cellular automata. And with simple automata like c'_i = c_(i-1) `xor` c_i `xor` c_(i+1) it may even be easier to generate fresh rings for each step in the automaton: data Context a = Context [a] a [a] -- rotate left rotL (Context ls x (r:rs)) = Context (x:ls) r rs -- description of a cellular automaton type Rule a= Context a - a example :: Rule Bool example (Context (cm:_) c (cp:_)) = cm `xor` c `xor` cp -- run a cellular automaton on an initial band of cells -- which is considered to be cyclic, i.e. a cylinder automate :: Rule a - [a] - [[a]] automate f xs = iterate (take n . map f . mkContexts) xs where -- length of the cell band n = length xs mkContexts (x:xs)= iterate rotL $ Context (cycle $ reverse xs) (head xs) (tail $ cycle xs) Here, mkContexts xs initializes a new infinite cyclic ring for xs and rotates it left ad infinitum. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Doubly-linked zipper list w/ insert implementation
On Nov 10, 2007 12:24 PM, apfelmus [EMAIL PROTECTED] wrote: Note that depending on your concrete setting, you may not need a fancy ring structure for cellular automata. And with simple automata like I realized that I never updated my automata once a row was created, and ended up using an unboxed array with an index to represent the ring. I just do some math when I want to rotate left or right and the index falls off the edge. The rules are much more complex though. I am using a genetic algorithm technique to evolve 7 bit rules which can classify if an initial row was mostly black or mostly white. This is loosely related to a class assignment. I'm finding that taking 100 initial rules, determining their fitness on 100 initial automatas, and doing that for 100 generations is taking a lng time. Our teacher's implementation, in C, does it in about a minute. Mine takes hours :( . I think its becuase the C algorithm does a lot of bit-twiddling to iterate the automata, while I'm using lists of integers (1, 0). Anyways, thanks for your thoughts! Justin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Doubly-linked zipper list w/ insert implementation
Justin Bailey wrote: The other day I decided to implement a ring buffer with a current element (i.e. a doubly-linked zipper list). In order to allow inserts (and, in the future, deletes and updates), I have a special sentinel element called Join in the structure. When inserting, I find the join first, insert and then rebuild the buffer using circular programming techniques. This also allows the buffer to be converted back to a list. The current element can be changed by rotating right or left, which never fails. Rotating n positions takes n steps. I'm posting it here for comments and feedback. How could the structure be smarter? Would storing a unique ID with each element make more sense? Any comments on the space behavior under insert and rotates? I wanted to maximize sharing. Thanks in advance. Do you really need to realize the cycle by sharing? I mean, sharing doesn't go well with insertion / updates / deletion since each of these operations breaks it and needs to restore it everywhere. In other words, your insert takes O(n) time. I'd simply drop the sharing and use two double ended queues (or something like that) instead data Ring a = Ring (DeQueue a) a (DeQueue a) -- pseudo-code missing lots of cases. I want views! left (Ring (l' : ls : l) x (r : rs : r')) = Ring (ls : l : x) r (rs : r' : l') This way, you can implement update operations in O(1) time instead of O(n). With a fancy random access queue like Data.Sequence , you can even have rotations like rotL xs n in O(log n) time. (I keep mixing up the meaning of rotL and rotR , does L push the current element to the left or does it rotate the ring clockwise?) Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Doubly-linked zipper list w/ insert implementation
On Nov 7, 2007 10:16 AM, apfelmus [EMAIL PROTECTED] wrote: Do you really need to realize the cycle by sharing? I mean, sharing doesn't go well with insertion / updates / deletion since each of these operations breaks it and needs to restore it everywhere. In other words, your insert takes O(n) time. I'd simply drop the sharing and use two double ended queues (or something like that) instead Very good point, and much easier to implement with Data.Sequence to boot. All that circular programming made my brain hurt. Thanks for your feedback. Justin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
