transpose() function

[gavinking]

I have added a transpose() function to the language module (ad3996d).

1. I would like people like @jvasileff and @lucaswerkmeister to review it.
2. I need to add some tests.

[lucaswerkmeister]

Looks alright to me.

[jvasileff]

I don't like having a worse return type (runtime & compile time) due to implementation concerns.

The implementation is local, but the return is global.

Accepting the tradeoff (introducing side effects in the implementation), I prefer:

shared {[Element?+]*} transpose<Element>
        ("The streams to be transposed"
         {{Element*}*} streams)
        => object satisfies {Row*} {
    alias Row => [Element?+];
    iterator() => object satisfies Iterator<Row> {
        value iterators = streams*.iterator();
        shared actual Row|Finished next() {
            if (!nonempty iterators) {
                return finished;
            }
            variable Boolean allFinished = true;
            value row = iterators.collect((it) {
                if (!is Finished element = it.next()) {
                    allFinished = false;
                    return element;
                }
                return null;
            });
            return allFinished then finished else row;
        }
    };
};

[jvasileff]

This is slightly better, producing a non-empty stream if streams is a nonempty stream of nonempty streams. I guess it's worth it.

shared Iterable<[Element?+], Absent> transpose<Element, Absent>
        ("The streams to be transposed"
         Iterable<Iterable<Element, Absent>, Absent> streams)
        given Absent satisfies Null
        => object satisfies Iterable<Row, Absent> {
    alias Row => [Element?+];
    iterator() => object satisfies Iterator<Row> {
        value iterators = streams*.iterator();
        shared actual Row|Finished next() {
            if (!nonempty iterators) {
                return finished;
            }
            variable Boolean allFinished = true;
            value row = iterators.collect((it) {
                if (!is Finished element = it.next()) {
                    allFinished = false;
                    return element;
                }
                return null;
            });
            return allFinished then finished else row;
        }
    };
};

[gavinking]

@jvasileff Thanks for your fixes.

introducing side effects in the implementation

Ugh. That's a bit "evil". We need a collectAndFold() method I guess. ;-)

producing a non-empty stream if streams is a nonempty stream of nonempty streams.

Yeah but that isn't quite logically correct. It would be correct if we truncated to the shortest stream, instead of padding to the longest stream. But here, as soon as you have a single possibly-empty stream, the return type is possibly-empty. So I don't see that change as very useful.

[zamfofex]

By the way, I wrote a transposition function to use in my hypercube program a while ago:

{[Element*]*} transpose<Element>({{Element*}*} streams) => streams.fold<{[Element*]*}>({[]}.cycled)(uncurry(shuffle(curry(zip<Element, Element, [Element*], Null, Null>))))*.reversed;

But since @notsonotso seems to really dislike that approach, here is an implementation translated directly from Haskell:

{[Element+]*} transpose<Element>({{Element*}+} streams)
{
	value heads = streams*.first;
	if(nonempty heads)
	{
		value tails = streams*.rest;
		return(transpose(tails).follow(heads));
	}
	else
	{
		return([]);
	}
}

I'm not sure if it will be useful to you guys, as it might not be the speediest, but I hope it's at least interesting. I myself really like that you can translate things directly from Haskell to Ceylon.

Additionally, I wrote the signature you guys probably want, if you care about emptiness:

Iterable<[Element+]|<[]&Iterable<Element, OuterAbsent>>, InnerAbsent> transpose<Element, InnerAbsent, OuterAbsent>(Iterable<Iterable<Element, InnerAbsent>, OuterAbsent> streams)
	given InnerAbsent
		satisfies Null
	given OuterAbsent
		satisfies Null

It's quite easy to port those two implementations I gave to have this signature, although, unfortunately, you'd need some asserts here and there.

[gavinking]

@Zambonifofex

*.reversed

This looks like it materializes the entire stream eagerly. That's no good at all.

here is an implementation translated directly from Haskell

That algorithm is recursive, so it would blow up the stack on the JVM.

you can translate things directly from Haskell to Ceylon

Not really, not without tail recursion.

[zamfofex]

That's pretty much the reaction I was expecting. Please don't think I wrote these algorithms to be efficient, I wrote them mostly for their elegance. Still, I feel like a couple of things can still be said their favor.

This looks like it materializes the entire stream eagerly. That's no good at all.

You could replace *.reversed with .map(function(value sequence) => sequence.reversed) or .map(Sequential<Element>.reversed). That would fix at least that, no?

That algorithm is recursive, so it would blow up the stack on the JVM.

Not really, not without tail recursion.

I meant that it works well on a conceptual/abstract level, not that it's the best solution. I'm trying to say that you'd never dream of translating things so well from Haskell to Java. I feel like Ceylon is a truly multi-paradigm language; I find it very easy to translate things directly from Haskell, Javascript, and Python, and I've heard from you on a video that it's quite easy to translate things from Java too.

[jvasileff]

@Zambonifofex that signature isn't correct for the implementation. The "inner" type never needs to be possibly-empty. The return type should be of the form:

    Iterable<[Element?+], ???>

The use of InnerAbsent to determine the result's "outer" absent also isn't quite right, since it would allow the incorrect:

    {[Integer*]+} result = transpose<Integer,Nothing,Null>([]);

[zamfofex]

@jvasileff

I feel like both of those are a matter of opinion. I think that it's better for the inner returned streams to never contain null, but instead for the outer returned stream to end with the shorter inner parameter stream. I also think that, given that each inner argument stream has the same size, transpose(transpose(a)) should always have the same elements as a. That means transpose([[]]) == [] and transpose([]) == [[]].

[jvasileff]

are a matter of opinion

well that's changing the function then.

[zamfofex]

Sure, but I feel like that's exactly what these issues are for: giving feedback. I'm just exposing what feels the most intuitive to me.

[Deleted user]

@Zambonifofex tail call optimization is possible, so your Haskell dream isn't just a dream. The point is to put the tail call semantics before lowering to JVM/JS/etc.

Frege (a Haskell-ish implementation for the JVM) has full tail call optimization support, and it does it by generating loops.

[zamfofex]

By the way, @gavinking, since you've added padding to transpose, I feel like it's interesting to note that it might look better to write transpose{null; {1, 2}, {4}, {7, 8, 9}} instead of transpose{padding=null; {1, 2}, {4}, {7, 8, 9}}.

[gavinking]

This is done, including tests.