Add sequence functions for various monads

[ryanbooker]

@CodaFi Is this what you were after (re: sequence conversation on Twitter https://twitter.com/CodaFi_/status/707423595601891328)?

sequence added for:

• Array
• Either
• Identity
• List
• Optional
• Proxy
• State
• String
• Stream
• Writer

I haven't been able to get Reader to type check.

[CodaFi]

Looks great! Can you throw in the bare minimum SwiftCheck properties for all of these (basically this)?

[ryanbooker]

Yep no problem. I'll get to that in the next day or so.

[mpurland]

The Reader issue seems to be an issue related to associated types.

[CodaFi]

Oh god, that looks like Swift thinks we need rank-2 polymorphism.

[ryanbooker]

@CodaFi I have some questions with the tests.

While looking at your SwiftCheck test for sequence on Gen, I noticed (at least it looks like) the order is being reversed by sequence. Is that intended?

Is the shape of a test for a give type M supposed to look like the following?

property("Gen.sequence occurs in order") <- forAll { (xs : [String]) in
    return forAllNoShrink(sequence(xs.map(M.pure))) { ss in
        return ss == xs
    }
}

If so, it seems that forAllNoShrink etc need to be implemented for all the types being sequenced, in SwiftCheck… Is that correct or have I missed something?

[CodaFi]

The file I linked to is on a branch where I fixed the order issue and committed that test. Use it instead of master.

[CodaFi]

@ryanbooker If you want me to write the tests for this, I can merge this and do it.

[mpurland]

Do we need to write the sequence function for Reader? I'm worried this may be a language/compiler limitation.

[CodaFi]

I can take a crack at it with the tests.

[ryanbooker]

Sorry. I was totally side tracked by Easter and work. I'm happy to write the tests, but I think I need some pointers/direction. I'm not particularly familiar with QuickCheck style testing. My first question:

Is the shape of a test for a give type M supposed to look like the following?

property("sequence occurs in order") <- forAll { (xs : [String]) in
    return forAllNoShrink(sequence(xs.map(M.pure))) { ss in
        return ss == xs
    }
}

If so, it seems that forAllNoShrink etc need to be implemented for all the types being sequenced, in SwiftCheck… Is that correct or have I misunderstood what is happening?

[ryanbooker]

A Haskeller friend also pointed out that sequence . fmap (what I actually needed sequence for) is traverse, should I/we look into that?

[CodaFi]

Traversable isn't typesafe in this language and doesn't generalize from Foldable at all. However, MonoTraversable will work great. As for the tests, I've implemented either Arbitrary or the WitnessedArbitrary shim for each one.

[ryanbooker]

To check my understanding, is this the right track?

property("sequence occurs in order") <- forAll { (xs : [String]) in
    return forAllNoShrink(Gen.pure(sequence(xs.map(Optional.pure)))) { ss in
        return ss! == xs
    }
}

xs.map(M.pure): transform the list into [M x]
sequence: sequence that list to get an M [x]
Gen.pure: create a generator for the M [x]
Then compare the [x] with xs

[CodaFi]

Yep! It's mostly for the order invariant.

[ryanbooker]

Tests added. Stream test is commented out. It causes the test suite to grind to a halt. I also added a special case to sequence for Arrays. If there's a better way, please let me know. But it was needed to ensure sequence([]) returns [], rather than [[]].

[CodaFi]

Yeah, that's to be expected. What happens if you use take on arbitrary subsequences to lower the law to the array ones?

[ryanbooker]

I'm not sure I understand what you mean. Do you mean basically remove sequence for Stream? So the test would be something like (or not even needed):

property("sequence occurs in order") <- forAll { (xs : [String]) in
    let seq = sequence(xs.map({ Stream.pure($0).take(1) }))
    return forAllNoShrink(Gen.pure(seq)) { ss in
        return ss.first ?? ss == xs
    }
}

[CodaFi]

No, leave it in. But equality on streams is not a thing, but equality on lists is so you see how in the Stream Spec I lower all the equality calls with take to equalities on streams of arbitrary stream heads? That's what I mean.

[ryanbooker]

It seems to be the actual sequence call that can take forever… I only compare the head of the stream against the original list for equality, and changing that to use take doesn't help. I assume I've just made a mistake that I can't see due to an incomplete understanding of Stream.

[CodaFi]

Yeah, so rather than invoke sequence on the Stream, just take an arbitrary number of elements and sequence the resulting Array instead.

[ryanbooker]

Yeah, ok. That's what I did above. But that's not really testing sequence on Stream then.

[CodaFi]

Not like we can, though. The laws require an equality that necessitates forcing the stream.

[CodaFi]

Can this take an arbitrary head of the sequence (an extra forAll)?

[ryanbooker]

It slows down to the point of not completing in any reasonable time. Assuming you mean wrapping it like other uses of take.

    return forAll { (n : UInt) in
    ...
    }

[CodaFi]

What does limiting the size of generated lists do (either with custom arguments or Gen.fromElementsIn(1...10), etc.)?

[ryanbooker]

Doesn't make a difference, even with 1...2.

[CodaFi]

Damn 😕

[CodaFi]

Welp, given the issues we discussed seem hard limits, and in the interest of honoring the great work you did here, I feel it's only appropriate to merge this.

Thanks for putting up with me through review ❤️ and for the patch ✨

⛵

[ryanbooker]

Thanks. No drama. It was a good learning process. Seems only fair seeing I use the project. :)