1) http://arclanguage.com/item?id=4146 . Might actually implement this in arc2c if I stop being lazy some time soon. And definitely after implementing arc2c macros.
What arc needs is a concept of "sequence", not separate array and list types. Yes, I know, I know, "lists are cons cells". Hahahaha. Well, 'map, 'some, 'all, 'keep, 'rem don't work on improper lists anyway. Improper lists are rarely used, and the implementation I propose can support them anyway, just not as efficiently. So some loss of efficiency in 'scdr is acceptable, at least you get O(n/m) index time, with O(1 + C) if m > n.
2) Sounds interesting. You could implement this using Arc lists as base, and use my lib/settable-fn.arc extension (or lib/settable-fn2.arc, which is fractionally more likely to get added into ArcN and which I intend to use for arc2c in lieu of my settable-fn) to support some of the mutation stuff. See also my "Create your own collection" series.
