Hacker News new | past | comments | ask | show | jobs | submit login

Entertainingly, you can't create a cyclic data structure with 100% pure code.



You can in a lazy language, like Haskell.


That's interesting, how do you achieve that?


Well, 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...


    repeat :: 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.


The defintion of 'something' uses it twice.


Laziness 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.


There's even a purely functional graph library, allowing cycles: http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl01...


It'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




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: