User loginNavigation |
Can referential transparency be bad? (puzzle included)After reading the thread about PL puzzles I decided for a change to design my own puzzle instead of my own PL. How about this - "mirror an immutable binary tree preserving existing sharing"? So in Haskell, I would take this data type: Or I may use StableName, but then I will end up inside IO kitchen sink. To be constructive, I decided to redesign the puzzle so it is a fair game. The full tree of depth n (having 2n-1 nodes) will therefore be compressed to a DAG of n nodes - impressive ratio! Additional points if your code does not create intermediate structures (this is unfair towards PLs without implicit stack, BTW), if it traverses the original tree only once, if it can be reused for other data types, and if you can state it's computational complexity and/or maximum size of the stack (sure, some of these tasks are much harder than others). By Andris Birkmanis at 2007-01-04 08:56 | LtU Forum | previous forum topic | next forum topic | other blogs | 8603 reads
|
Browse archivesActive forum topics |
Recent comments
2 weeks 7 hours ago
4 weeks 1 day ago
13 weeks 3 days ago
13 weeks 5 days ago
14 weeks 2 hours ago
21 weeks 52 min ago
26 weeks 4 days ago
26 weeks 5 days ago
27 weeks 4 days ago
30 weeks 3 days ago