I-Structures: Data Structures for Parallel Computing

It is difficult to achieve elegance, efficiency and parallelism simultaneously in functional programs that manipulate large data structures. We demonstrate this through careful analysis of program examples using three common functional data-structuring approaches--- lists using Cons and arrays using Update (both fine-grained operators), and arrays using make array (a "bulk" operator). We then present I-structures as an alternative, and show elegant, efficient and parallel solutions for the program examples in Id, a language with I-structures. The parallelism in Id is made precise by means of an operational semantics for Id as a parallel reduction system. I-structures make the language nonfunctional, but do not lose determinacy. Finally,weshowthateven in the context of purely functional languages, I-structures are invaluable for implementing functional data abstractions