Big-O wise laziness can NEVER be worse than greedy evaluation. In terms of those nasty constant multipliers, yes, laziness can be slower. But in terms of algorithm design laziness is the only way to create amortized structures that maintain their bounds under persistant use. Consider a normal batched queue (front stack, back stack, reverse when empty). Consider persitantly going back in time to just before a reverse and reversing it again. and Again. and again. Bad.
I disagree... they may be harder to learn if you were brought up on imperitive languages, but function code is certainly easier to read than imperitive code.
I'm inclined to agree... but hopefully I can help. This book is my bible, given as my primary interest is functional algorithms. The topics covered are, as you might expect, data structure based, and focused on 'concepts' rather than 'reference'. He doesn't give complete implementaitons of a lot of the structures, leaving it more as an excercise (there is no deletion in the red-black trees), and there is a lot of analysis. The first bit discusses basic imperitive data structures, and how to code them functionally, making it not too hard to start with if you're not familiar with the topic... not to say that you shouldn't already know functional programming and data structure design. The two 'big' (read new) things in the book are layaway ammortization, which can be used persistantly, and a discussion of math-inspired structures deriving from binomial heaps. If you want more information on it, feel free to email me.
Slashdot Mirror
You cannot have functional/persistent arrays, skip lists, splay trees, or anything that has multiple paths or requires side-effects on reading.
Big-O wise laziness can NEVER be worse than greedy evaluation. In terms of those nasty constant multipliers, yes, laziness can be slower. But in terms of algorithm design laziness is the only way to create amortized structures that maintain their bounds under persistant use. Consider a normal batched queue (front stack, back stack, reverse when empty). Consider persitantly going back in time to just before a reverse and reversing it again. and Again. and again. Bad.
I disagree... they may be harder to learn if you were brought up on imperitive languages, but function code is certainly easier to read than imperitive code.
Only where there are dependencies of value, especially if you use lazy lets and not just lazy function calls.
I'm inclined to agree... but hopefully I can help. This book is my bible, given as my primary interest is functional algorithms. The topics covered are, as you might expect, data structure based, and focused on 'concepts' rather than 'reference'. He doesn't give complete implementaitons of a lot of the structures, leaving it more as an excercise (there is no deletion in the red-black trees), and there is a lot of analysis. The first bit discusses basic imperitive data structures, and how to code them functionally, making it not too hard to start with if you're not familiar with the topic... not to say that you shouldn't already know functional programming and data structure design. The two 'big' (read new) things in the book are layaway ammortization, which can be used persistantly, and a discussion of math-inspired structures deriving from binomial heaps. If you want more information on it, feel free to email me.