12 ms·

Understanding Clojure's Persistent Vectors, Pt. 3

62 points by JBiserkov 12y ago

ScottBurson 12y ago
At the beginning of part 1, the author says that this data structure provides "practically O(1) runtime" (emphasis added) for the important operations of lookups, insertion, updating, etc. At the end it is explained how it's "O(log32 n)", which of course is actually O(log n). And then here in part 3 where he keeps saying "effectively constant time* (emphasis in original this time), what he means is O(log n) time. The Clojure people really need to stop doing this. Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large. It is precisely not intended to communicate the absolute time the operation takes in small cases. They are confusing people when they try to communicate both pieces of information at the same time. What they should say is something like "lookup takes O(log n) time, and for seqs of size up to N items, it takes M times as long as ArrayList.get". And then, of course, to describe O(log n) time as "effectively constant" is just lying. (Second and fourth paragraphs added in edit.)
- mamcx 12y ago
  How performant is this kind of structures? For what is best?
- plinkplonk 12y ago
  I've seen it in some Clojure books too. "effectively constant","practically O(1)" etc. The funny thing is that this kind of scamming is not necessary at all.
- lomnakkus 12y ago
  log_32(2^48) is <= 10. Your computer cannot access anywhere close to 2^48 items. I appreciate a little pedantry as much as the next guy, but if you can come up with an equally concise way of saying it than "effectively constant" then please do so.
  - rawnlq 12y ago
    Here you go: Õ (read soft-O) See: http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_the_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_th... (basically means ignore multiplicative log factors) Also, to play devil's advocate, why not say all log factors are effectively constant? Note that 5 * log_32(x) = log_2(x) or to use your example, log_2(2^48) <= 50.
    - lomnakkus 12y ago
      Interesting. I was not aware of that notation, thank you. Re: "all log factors": Agreed, as long as the base of the logarithm is high enough, obviously :). I'm well aware that the base doesn't matter mathematically, but in practice it actually does. Especially since 32 is the number of bits in a CPU word, and thus neatly fits into cache lines, is easily manipulable by CPU instructions, etc. etc. (See Bagwell's papers for details.)
- NoodleIncident 12y ago
  When does this distinction matter? At some point even updating an O(1) vector is going to actually depend on your pager, cache, swap, bignum libraries and other non-O(1) factors, but no one calls out C developers for "lying".
- TheLoneWolfling 12y ago
  I have to disagree with you here. Let me put it this way: There are theoretical limits to the upper bound of problem size. The number of bits storable in the (observable) universe is only, what, about 10^120? [1] log32(10^120) is only around 80. So if you have a constant-time algorithm that runs around 80x slower than a logrithmic algorithm for small cases, the constant-time algorithm will never be faster. Period. And I've seem constant-time algorithms that take >80x the speed of theoretically asymptotically slower algorithms. I mean: a single cache miss can cause that level of slowdown. Or, to put it another way, log32(n) <= 80 for all achievable n. So, realistically, you might as well consider it effectively O(80), i.e. O(1). You have something similar, albeit more extreme, for inverse Ackermann time. [1] http://physics.aps.org/story/v9/st27 http://physics.aps.org/story/v9/st27
  - tolmasky 12y ago
    Doesn't it matter in the way functions compose however? Definitely not my area of expertise, but similar to the classic N^2 iteration trap (for(i=0;i<strlen(str);++i) ...) you could see something like that happening by multiplying log operations together. For example, if for each item in a this vector, I have 2 nested inner loops where I act as if the operation is O(1), I start feeling like it should perform O(N), in reality though, its performing O(N * log32^2 N). If N is 1,000,000 (not an unreasonable amount by any means), we're now talking 1.5 * 10^7 operations vs 1 * 10^6 that I expect. Perhaps arguably not too unreasonable a slowdown, but its certainly affecting the way my application scales in a way that wasn't immediately intuitive when I initially wrote the code. Again, not sure if this is an practical worry, but curious if these seemingly small differences can magnify as they bubble up through composition.
    - ajuc 12y ago
      If for all realistically possible n your O(log n) function is faster than O(1) function, then calling your function K times will still be faster than calling that O(1) function K times.
  - malisper 12y ago
    > There are theoretical limits to the upper bound of problem size. Big O is defined as what happens as the size of the input approaches infinity. You cannot take a O(log n) algorithm and say it is effectively O(1), that is not what big O means. If anything, you are arguing for why big O notation is a bad measure for the efficiency of an algorithm, not why you can call a O(log n) algorithm O(1).
- ajuc 12y ago
  I agree when we speak about algorithms. When we speak about specific implementations it's useles most often, because most of these implementations use datatypes that simply don't work for numbers bigger than 2^64, collections that can hold at most 2^64 items etc. So your program can sort collections of at most 2^64 items in n log n? Nice, I can do that in constant time.
- JeanPierre 12y ago
  I understand your concern, but I don't really think the problem is within Clojure people: When I started out explaining the structure to other people and that most operations have O(log n) runtime, people dismissed Clojure as being too slow for practical purposes. Part of this is because programmers, not Clojure devs in particular, connotate O(log n) with "much slower than O(1)". However, this data structure is incredibly much faster than the "O(log n)" people are generally used to. And this is the problem. As you yourself say, most programmers usually associate/assume "Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large". But formally, this is not the case at all. O(g(x)) tells you the that the worst case input to the algorithm will require less operations (usually operations, sometimes memory or other things) than the function g multiplied by some positive constant. g is usually determined by the size of the input. (This definition is also simplified somewhat, but it illustrates the problem) We can say that ArrayLists.add have O(n) runtime and that quicksort have O(n²) runtime, but they both also have O(n³) and O(n!) runtime. In addition, Big-O does not describe how the algorithm runs in the average case, or how frequent the worst case is. In and of itself, the Big-O notation tells us almost nothing about an algorithm – you barely conclude anything from it. I guess that is part of why it has become this very simplified term with a very wibbly-wobbly definition from time to time. So when you're saying that calling it "practically O(1)" is lying, I agree if this was in an academic context. But for the average programmer (regardless of language!), O(g(x)) is usually thought of as the "worst case runtime for an algorithm". Since the actual runtime is – well – effectively constant, I considered it okay. --- That being said, I have formally explained the persistent vector if you're interested in the academic version. The background chapter in http://hypirion.com/thesis.pdf http://hypirion.com/thesis.pdf should cover it.
  - rawnlq 12y ago
    Cool you seem to be the author. Instead of telling people that it's O(log n) you should just show benchmarks instead. Hitting L1 takes 1ns but main memory takes 100ns. So although you can say accessing an element in an array is always O(1) = O(100), it is hiding a factor of a 100 depending on how it is accessed. Having a log in the big Oh usually means it is jumping around a lot and is no longer a cache friendly algorithm, so that worries me more than whether it is log_2(x) or log_2(x)/5.
- michaelochurch 12y ago
  You are, on the matter of what these notations mean, absolutely right. This "effectively constant time" claim didn't originate from Clojure, by the way. Scala, which has similar 32-tree structures, used it before then. In functional programming, binary-tree structures were common for maps and sets (and still are, in Haskell and Ocaml) because they can use comparisons without hashing and can be faster. However, those trees tend to involve ~log2 n bounces, which can become a performance problem if they're very big. People end up preferring (less functional, and less performant due to hashing if your collection is small) hash tables. The 32-tree structures are great, on the whole. Not only do they offer fast lookups, but the amount of copying that has to be done for inserts and deletions is generally very small. The "effectively constant" language emerged as a way of saying, "you're not necessarily going to want to replace this with a hashtable at 1,000,000 elements". Rich Hickey gave a talk early on about this in which he acknowledged the fact that it was still O(log n) time. As he said, constants matter. The reason people equate O(log n) lookup with "slow" is that they (mistakenly) assume that n ~ 1,000,000 will prima facie the lookup 20x slower than it "needs to be". And that's, of course, false.
  - ScottBurson 12y ago
    Just to be clear, I would never suggest that the constant factor doesn't matter. I might, however, repeat the familiar quote about premature optimization :-)
- calibraxis 12y ago
  As I vaguely recall, even Plain Old Array accesses take logarithmic time on real machines. However, if we don't use bignums, they're effectively constant time. Furthermore, it's common to "lie" in computer science. Knuth wrote: "Another noteworthy characteristic of this manual is that it doesn't always tell the truth ... The author feels that this technique of deliberate lying will actually make it easier for you to learn the ideas. Once you understand the simple but false rule, it will not be hard to supplement that rule with its exceptions." Particularly since O(..) notation is generally used in reference to MODELS, not real machines. But in any case, Clojure's "effectively constant" is obviously correct.
  - billsix 12y ago
    > As I vaguely recall, even Plain Old Array accesses take logarithmic time on real machines. How does adding an offset to a pointer and referencing that data require logarithmic time? >. However, if we don't use bignums, they're effectively constant time. What are these bignums that are used for array access on "real machines"?
- ScottBurson 12y ago
  Okay, "just lying" is too strong. But see my reply to JeanPierre.
tolmasky 12y ago
I'm curious if anyone who has read (or is familiar with the data structures described in) Purely Functional Data Structures[0] can weigh in on how this persistent vector compares to say, the real time deque which is described to have worst case runtime of O(1) for cons/head/tail/snoc/last/init (along with plenty of other structures which have similar amortized time guarantees, etc.) Do these structures not have practical performance characteristics, or is there another reason a O(log) solution was chosen? Like the other poster mentioned here, its a bit upsetting having read something that rigorously analyzes worst time behavior to have an article hand wave away log32 as "effectively constant time". Especially because amortization is even trickier to consider with persistent data structures since you have to deal with the fact that you may have many operations taking place on your worst case node (several pushes on your edge case base vector, etc). Perhaps these tries actually account for that very elegantly, but I certainly don't know enough to intuit it from what I've seen here. 0. http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 http://www.amazon.com/Purely-Functional-Structures-Chris-Oka... Edit: PDF version: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
- lomnakkus 12y ago
  AFAIR the deques in PFDS don't permit anything better than O(log n) random access -- and the ones that do that are hideously complicated (again AFAIR, it's been years since I read it). Also, the thing is constants matter, and this is what the "log_32(n)" vs. "log(n)" discussion is driving at. (You're still not going to get anywhere close to a linear scan of an array with directly embedded values, but there's just no way to achieve that kind of raw performance for pure functional data structures.)
- Kutta 12y ago
  The key point here is that Clojure-style vectors have logarithmic random reads/writes, while Okasaki's aforementioned deques do the same in linear time. Clojure uses the persistent vector by default, so it's essential that people can port their usual imperative vector algorithms and expect to get acceptable performance. Hence the focus on random access. As to amortization, operations on Clojure-style vectors have pretty much zero variance (modulo the size of the vector). There is no resizing, no reordering, no rotation or whatever, it's just the exact same algorithm every time.
lisper 12y ago
I always thought "persistent" meant "stored in non-volatile storage" but this author seems to be using it as a synonym for "immutable" or "functional" which seems really weird to me. Is this a Clojure-ism?
- deleted 12y ago
  [deleted]
- augustl 12y ago
  In the context of data structures, persistent has a very specific meaning. So it's not really a Clojure-ism. https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure It's not a synonym for immutable or functional. A persistent data structure is one that shares structure with other data structures.
  - ajanuary 12y ago
    > A persistent data structure is one that shares structure with other data structures. No, a persistent data structure is one where, when you apply an operation that would ordinarily modify it, you instead get back a new data structure with the operation applied, and the old data structure appears the same. I could make an array persistent by copying the entire array each time. No structural sharing at all. Of course, you want structural sharing because it makes things a heck of a lot more efficient, but it's not a part of the definition of a persistent data structure.
    - dopamean 12y ago
      If this is totally accurate then thanks for clearing that up. I was of the impression that part of what made persistent data structures persistent was the structural sharing.
    - lisper 12y ago
      Then I'm still confused. Is "persistent data structure" a synonym for "purely functional data structure" in the sense of Oakasaki96? http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

62 points by JBiserkov 12y ago

At the beginning of part 1, the author says that this data structure provides "practically O(1) runtime" (emphasis added) for the important operations of lookups, insertion, updating, etc. At the end it is explained how it's "O(log32 n)", which of course is actually O(log n). And then here in part 3 where he keeps saying "effectively constant time* (emphasis in original this time), what he means is O(log n) time. The Clojure people really need to stop doing this. Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large. It is precisely not intended to communicate the absolute time the operation takes in small cases. They are confusing people when they try to communicate both pieces of information at the same time. What they should say is something like "lookup takes O(log n) time, and for seqs of size up to N items, it takes M times as long as ArrayList.get". And then, of course, to describe O(log n) time as "effectively constant" is just lying. (Second and fourth paragraphs added in edit.)

mamcx 12y ago
How performant is this kind of structures? For what is best?
plinkplonk 12y ago
I've seen it in some Clojure books too. "effectively constant","practically O(1)" etc. The funny thing is that this kind of scamming is not necessary at all.
lomnakkus 12y ago
log_32(2^48) is <= 10. Your computer cannot access anywhere close to 2^48 items. I appreciate a little pedantry as much as the next guy, but if you can come up with an equally concise way of saying it than "effectively constant" then please do so.
- rawnlq 12y ago
  Here you go: Õ (read soft-O) See: http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_the_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_th... (basically means ignore multiplicative log factors) Also, to play devil's advocate, why not say all log factors are effectively constant? Note that 5 * log_32(x) = log_2(x) or to use your example, log_2(2^48) <= 50.
  - lomnakkus 12y ago
    Interesting. I was not aware of that notation, thank you. Re: "all log factors": Agreed, as long as the base of the logarithm is high enough, obviously :). I'm well aware that the base doesn't matter mathematically, but in practice it actually does. Especially since 32 is the number of bits in a CPU word, and thus neatly fits into cache lines, is easily manipulable by CPU instructions, etc. etc. (See Bagwell's papers for details.)
NoodleIncident 12y ago
When does this distinction matter? At some point even updating an O(1) vector is going to actually depend on your pager, cache, swap, bignum libraries and other non-O(1) factors, but no one calls out C developers for "lying".
TheLoneWolfling 12y ago
I have to disagree with you here. Let me put it this way: There are theoretical limits to the upper bound of problem size. The number of bits storable in the (observable) universe is only, what, about 10^120? [1] log32(10^120) is only around 80. So if you have a constant-time algorithm that runs around 80x slower than a logrithmic algorithm for small cases, the constant-time algorithm will never be faster. Period. And I've seem constant-time algorithms that take >80x the speed of theoretically asymptotically slower algorithms. I mean: a single cache miss can cause that level of slowdown. Or, to put it another way, log32(n) <= 80 for all achievable n. So, realistically, you might as well consider it effectively O(80), i.e. O(1). You have something similar, albeit more extreme, for inverse Ackermann time. [1] http://physics.aps.org/story/v9/st27 http://physics.aps.org/story/v9/st27
- tolmasky 12y ago
  Doesn't it matter in the way functions compose however? Definitely not my area of expertise, but similar to the classic N^2 iteration trap (for(i=0;i<strlen(str);++i) ...) you could see something like that happening by multiplying log operations together. For example, if for each item in a this vector, I have 2 nested inner loops where I act as if the operation is O(1), I start feeling like it should perform O(N), in reality though, its performing O(N * log32^2 N). If N is 1,000,000 (not an unreasonable amount by any means), we're now talking 1.5 * 10^7 operations vs 1 * 10^6 that I expect. Perhaps arguably not too unreasonable a slowdown, but its certainly affecting the way my application scales in a way that wasn't immediately intuitive when I initially wrote the code. Again, not sure if this is an practical worry, but curious if these seemingly small differences can magnify as they bubble up through composition.
  - ajuc 12y ago
    If for all realistically possible n your O(log n) function is faster than O(1) function, then calling your function K times will still be faster than calling that O(1) function K times.
- malisper 12y ago
  > There are theoretical limits to the upper bound of problem size. Big O is defined as what happens as the size of the input approaches infinity. You cannot take a O(log n) algorithm and say it is effectively O(1), that is not what big O means. If anything, you are arguing for why big O notation is a bad measure for the efficiency of an algorithm, not why you can call a O(log n) algorithm O(1).
ajuc 12y ago
I agree when we speak about algorithms. When we speak about specific implementations it's useles most often, because most of these implementations use datatypes that simply don't work for numbers bigger than 2^64, collections that can hold at most 2^64 items etc. So your program can sort collections of at most 2^64 items in n log n? Nice, I can do that in constant time.
JeanPierre 12y ago
I understand your concern, but I don't really think the problem is within Clojure people: When I started out explaining the structure to other people and that most operations have O(log n) runtime, people dismissed Clojure as being too slow for practical purposes. Part of this is because programmers, not Clojure devs in particular, connotate O(log n) with "much slower than O(1)". However, this data structure is incredibly much faster than the "O(log n)" people are generally used to. And this is the problem. As you yourself say, most programmers usually associate/assume "Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large". But formally, this is not the case at all. O(g(x)) tells you the that the worst case input to the algorithm will require less operations (usually operations, sometimes memory or other things) than the function g multiplied by some positive constant. g is usually determined by the size of the input. (This definition is also simplified somewhat, but it illustrates the problem) We can say that ArrayLists.add have O(n) runtime and that quicksort have O(n²) runtime, but they both also have O(n³) and O(n!) runtime. In addition, Big-O does not describe how the algorithm runs in the average case, or how frequent the worst case is. In and of itself, the Big-O notation tells us almost nothing about an algorithm – you barely conclude anything from it. I guess that is part of why it has become this very simplified term with a very wibbly-wobbly definition from time to time. So when you're saying that calling it "practically O(1)" is lying, I agree if this was in an academic context. But for the average programmer (regardless of language!), O(g(x)) is usually thought of as the "worst case runtime for an algorithm". Since the actual runtime is – well – effectively constant, I considered it okay. --- That being said, I have formally explained the persistent vector if you're interested in the academic version. The background chapter in http://hypirion.com/thesis.pdf http://hypirion.com/thesis.pdf should cover it.
- rawnlq 12y ago
  Cool you seem to be the author. Instead of telling people that it's O(log n) you should just show benchmarks instead. Hitting L1 takes 1ns but main memory takes 100ns. So although you can say accessing an element in an array is always O(1) = O(100), it is hiding a factor of a 100 depending on how it is accessed. Having a log in the big Oh usually means it is jumping around a lot and is no longer a cache friendly algorithm, so that worries me more than whether it is log_2(x) or log_2(x)/5.
michaelochurch 12y ago
You are, on the matter of what these notations mean, absolutely right. This "effectively constant time" claim didn't originate from Clojure, by the way. Scala, which has similar 32-tree structures, used it before then. In functional programming, binary-tree structures were common for maps and sets (and still are, in Haskell and Ocaml) because they can use comparisons without hashing and can be faster. However, those trees tend to involve ~log2 n bounces, which can become a performance problem if they're very big. People end up preferring (less functional, and less performant due to hashing if your collection is small) hash tables. The 32-tree structures are great, on the whole. Not only do they offer fast lookups, but the amount of copying that has to be done for inserts and deletions is generally very small. The "effectively constant" language emerged as a way of saying, "you're not necessarily going to want to replace this with a hashtable at 1,000,000 elements". Rich Hickey gave a talk early on about this in which he acknowledged the fact that it was still O(log n) time. As he said, constants matter. The reason people equate O(log n) lookup with "slow" is that they (mistakenly) assume that n ~ 1,000,000 will prima facie the lookup 20x slower than it "needs to be". And that's, of course, false.
- ScottBurson 12y ago
  Just to be clear, I would never suggest that the constant factor doesn't matter. I might, however, repeat the familiar quote about premature optimization :-)
calibraxis 12y ago
As I vaguely recall, even Plain Old Array accesses take logarithmic time on real machines. However, if we don't use bignums, they're effectively constant time. Furthermore, it's common to "lie" in computer science. Knuth wrote: "Another noteworthy characteristic of this manual is that it doesn't always tell the truth ... The author feels that this technique of deliberate lying will actually make it easier for you to learn the ideas. Once you understand the simple but false rule, it will not be hard to supplement that rule with its exceptions." Particularly since O(..) notation is generally used in reference to MODELS, not real machines. But in any case, Clojure's "effectively constant" is obviously correct.
- billsix 12y ago
  > As I vaguely recall, even Plain Old Array accesses take logarithmic time on real machines. How does adding an offset to a pointer and referencing that data require logarithmic time? >. However, if we don't use bignums, they're effectively constant time. What are these bignums that are used for array access on "real machines"?
ScottBurson 12y ago
Okay, "just lying" is too strong. But see my reply to JeanPierre.

tolmasky 12y ago

I'm curious if anyone who has read (or is familiar with the data structures described in) Purely Functional Data Structures[0] can weigh in on how this persistent vector compares to say, the real time deque which is described to have worst case runtime of O(1) for cons/head/tail/snoc/last/init (along with plenty of other structures which have similar amortized time guarantees, etc.) Do these structures not have practical performance characteristics, or is there another reason a O(log) solution was chosen? Like the other poster mentioned here, its a bit upsetting having read something that rigorously analyzes worst time behavior to have an article hand wave away log32 as "effectively constant time". Especially because amortization is even trickier to consider with persistent data structures since you have to deal with the fact that you may have many operations taking place on your worst case node (several pushes on your edge case base vector, etc). Perhaps these tries actually account for that very elegantly, but I certainly don't know enough to intuit it from what I've seen here. 0. http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 http://www.amazon.com/Purely-Functional-Structures-Chris-Oka... Edit: PDF version: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

lomnakkus 12y ago
AFAIR the deques in PFDS don't permit anything better than O(log n) random access -- and the ones that do that are hideously complicated (again AFAIR, it's been years since I read it). Also, the thing is constants matter, and this is what the "log_32(n)" vs. "log(n)" discussion is driving at. (You're still not going to get anywhere close to a linear scan of an array with directly embedded values, but there's just no way to achieve that kind of raw performance for pure functional data structures.)
Kutta 12y ago
The key point here is that Clojure-style vectors have logarithmic random reads/writes, while Okasaki's aforementioned deques do the same in linear time. Clojure uses the persistent vector by default, so it's essential that people can port their usual imperative vector algorithms and expect to get acceptable performance. Hence the focus on random access. As to amortization, operations on Clojure-style vectors have pretty much zero variance (modulo the size of the vector). There is no resizing, no reordering, no rotation or whatever, it's just the exact same algorithm every time.

lisper 12y ago

I always thought "persistent" meant "stored in non-volatile storage" but this author seems to be using it as a synonym for "immutable" or "functional" which seems really weird to me. Is this a Clojure-ism?

deleted 12y ago
[deleted]
augustl 12y ago
In the context of data structures, persistent has a very specific meaning. So it's not really a Clojure-ism. https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure It's not a synonym for immutable or functional. A persistent data structure is one that shares structure with other data structures.
- ajanuary 12y ago
  > A persistent data structure is one that shares structure with other data structures. No, a persistent data structure is one where, when you apply an operation that would ordinarily modify it, you instead get back a new data structure with the operation applied, and the old data structure appears the same. I could make an array persistent by copying the entire array each time. No structural sharing at all. Of course, you want structural sharing because it makes things a heck of a lot more efficient, but it's not a part of the definition of a persistent data structure.
  - dopamean 12y ago
    If this is totally accurate then thanks for clearing that up. I was of the impression that part of what made persistent data structures persistent was the structural sharing.
  - lisper 12y ago
    Then I'm still confused. Is "persistent data structure" a synonym for "purely functional data structure" in the sense of Oakasaki96? http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf