5 ms·
If I am not mistaken you will always need a GC for cyclic data structures, which you can't type linearly.
by chombier 10y ago
If I am not mistaken you will always need a GC for cyclic data structures, which you can't type linearly.
- moomin 10y agoEntertainingly, you can't create a cyclic data structure with 100% pure code.
- taejo 10y agoYou can in a lazy language, like Haskell.
- moomin 10y agoThat's interesting, how do you achieve that?
- merijnv 10y agoWell, one of the usual examples would be: let ones = 1 : ones in ones Here ':' is the cons operator, prepending something to a list, so here you defines 'ones' to be '1' followed by 'ones', which in (GHC) Haskell, compiles down to a datatype that has a pointer to the list element ('1') and the tail ('ones', i.e. itself). EDIT: I realised I forgot to say what it actually does, in case that's not obvious. It's an infinite list of, well, ones...
- unhammer 10y agoThere's even a purely functional graph library, allowing cycles: http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl0103.pdf http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl01...
- pdexter 10y agoIt's not a 'cyclic data structure' though. It allows cycles in that every node has an ID and you can freely point to nodes to create cycles. For a cyclic graph with true cycles see https://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf https://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf
- runeks 10y agorepeat :: a -> [a] repeat something = [something] ++ repeat something print (head (repeat "hello")) For performance reasons, you wouldn't implement it exactly like this, but the principle is the same. The list can contain an infinite number of elements, but not unless some function tries to consume all elements does it become a problem.
- chalst 10y agoThe defintion of 'something' uses it twice.
- tel 10y agoLaziness gives pure semantics to a certain form of mutation. Technically you don't represent cycles but instead the infinite unfolding of that cycling structure... but you do so in a way where the compiler just makes the cycle. In pure code these two situations are indistinguishable.
- tel 10y agoI imagine that given linear arrows you could write something like Rust's Rc/Arc?