[jbapple]

> How do these differ and what advantage do they offer over Chris Okasaki's Random Access Lists?

These are inferior, as Okasaki's structure offers O(1) worst-case cons, even when used in a functional setting. As far as I can tell from the Wikipedia page on Exponential-Golumb coding, trellises require Omega(lg n) for cons.

[daniel-cussen]

I get the feeling these can do things Random Access Lists can't (I haven't experimented yet, but I think trellises can support both data and code).

[jbapple]

> I get the feeling these can do things Random Access Lists can't

It seems like you came to this topic without knowing a lot about purely functional data structures already. It's good to learn and explore new things, but from this comment ("support both data and code"?) as well as other comments of yours on this thread and in your code ("I can't really explain it yet, but it works", "I didn't want to weird people out", the assumption that building a data structure out of cons cells makes it different from most data types, supporting your asymptotic analysis by claiming that "it works, at least on my computer", or noting that the reason it works is "mathematical" (yes, mathematics is a language for reasoning about structure, including algorithm correctness), claiming that balanced binary search trees don't have "predictable structure", etc.) makes me suspect of your intuition about this data structure about which you are clearly very excited -- unless you can provide a reason why you have this feeling that doesn't just say what's good about your data structure, but explains what's lacking in Okasaki's

It's clear you don't have a lot of experience with the design of functional data structures. I think if you read some of Okasaki's work, you will be better able to communicate statement like "trellises can support both data and code" using prose that other programmers can understand.

In this particular case, I suspect my confusion about your feeling is the same as that of somnium in reply to your comment. Okasaki's random access lists are a polymorphic data structure. They can hold anything -- data, code, linguine, fettuccine, bikini. They support pushing an element onto (or removing an element from) the front of the list in O(1) worst-case time, even when used functionally (this has a special meaning here other than "in a functional language" or "in a way that is not broken". Compare "confluently presistent", which is weaker.) They also support lookup (that is, nth) and update of the ith element in O(min(i,lg n)) time.

I do not think your data structure supports all of these operations with the same time bounds, and it's unclear what is unique about its ability to "support both data and code".

[somnium]

Perhaps you could elaborate on that feeling? (and also clarify what you mean by supporting data and code)

The linked SRFI advocates replacing Scheme's traditional pairs/lists with RALists.

[daniel-cussen]

I'm looking at that and McCarthy's eval now.

[jbapple]

> trellises require Omega(lg n) for cons.

In the worst-case, I mean.