I incorporated the current ideque API into Gauche.  Will send comments later.
Meanwhile, I wrote a blackbox test suite; if you haven't, feel free to grab it.
(I tried to follow Chibi test forms, but I'm running it with my ad-hoc compatibility
layer in Gauche, so I can't guarantee it runs on Chibi as is.)

https://github.com/shirok/Gauche/blob/master/test/include/ideque-tests.scm


On Fri, Jan 22, 2016 at 10:34 AM, John Cowan <xxxxxx@mercury.ccil.org> wrote:
Shiro Kawai scripsit:

> (My current implementation is based on Chris Okasaki's book:
> https://github.com/shirok/Gauche/blob/master/lib/data/immutable-deque.scm
> If you need another reference implementation, I'd be happy to make it
> portable
> and adapt to this srfi's api.)

I may, though I currently expect an implementation based on 2,3-finger
trees to land soon.  If it's *very* soon, I'll skip writing the two-list
implementation, even though it's trivial to do.  At any rate I need to
write the black-box tests as soon as the API stabilizes.

> I feel it's a bit overwhelming to have the whole set of sequence-like APIs.
> The fundamental operations of deque are basically emtpy?,
> front, back, add-front, add-back, remove-front and remove-back.
> I just expect them, plus some constructors and converters, for
> immutable deque.
>
> I can understand the motivation of the rich API; although they can
> be implemented trivially with ideque->list and list operation,
> having them directly in ideque can save construction of intermediate
> data structures.

The logic is that I don't want people to say "Lists have the richest set
of library routines, so I'll just use lists because they are the easiest
to use", at the expense of contorting their data structures.  By making
all libraries equally rich, the choice of data structure can follow other
criteria.

> OTOH, if we keep on having this set across sequence-like data types,
> I'd like to see them consistent.  Each data type exposing slightly
> different set of APIs will be very confusing.

I try.  There are two forces pushing me toward incompatibility: One is
that sometimes the old definitions are just bad:  not having a failure
thunk for SRFI 1 find and returning #f was a mistake.  There's a
workaround for this mistake, so it's not fatal, but it's discouraging.

> Missing: Obviously the "linear update" version doesn't make sense
> in immutable data types, but there are other APIs that are in
> srfi-1 but not in ideque.  Each of which I can imagine the reason;
> e.g. make-ideque makes little sense in practice.

Just so.  That is the second reason for incompatibilities: some operations
(especially constructors) just aren't reasonable for particular data
types.  I don't know anything to do about this.  Even in languages with
interfaces or type classes, typically constructors are not covered by them.

If you see particular operations that seem to be missing, please let me know.

> I don't see ideque-take is so much useful that it is worth to
> be in.   (I'd imagine the use case where I want to get first
> or last N items of ideque, but then I want it in list of N items
> rather than another ideque.)

The idea is that it allows you to partition an ideque by size of elements.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
I am he that buries his friends alive and drowns them and draws them
alive again from the water. I came from the end of a bag, but no bag
went over me.  I am the friend of bears and the guest of eagles. I am
Ringwinner and Luckwearer; and I am Barrel-rider.  --Bilbo to Smaug