How to define arbitrary extensions for recursive datatypes?

[Fryie]

Hi, I'm looking for a way to add arbitrary to types that are recursive, e.g.

struct List {
   let head: Int
   let tail: [Int]
}

Knowing QuickCheck in Haskell, the impulse is to write

extension List {
   public static var arbitrary: Gen<List> {
       return Gen<List>.one(of: [
           Int.arbitrary.map { List(head: $0, tail: []) },
           return List.arbitary.flatMap { (list: List) in
               Int.arbitrary.map { (i: Int) in
                   return List(head: i, tail: list)
               }
           }
       ])
    }
}

knowing that the probability of this sequence ending after some finite number of elements is 1. But obviously, in a strict language like Swift this can't work, since List.arbitrary will just call itself endlessly. Short of having to somehow manage a maximum depth myself, is there anything I can do to emulate this?

[felix91gr]

Try running it. Since Gen<T>.one(...) picks the given options at random, the probability of giving you a Stack Overflow is 0. Unless you give it weights such that it's forced to always pick the recursive step.

Also, I'd recommend giving it a weight dependent on how deep you want the average List to be:

• 50% recursion prob: 1/1000 prob that you'll get a length 10+ List.
• 90% recursion prob: 1/3 prob that you'll get a length 10+ List.

[Fryie]

Sorry, I probably didn't explain correctly. The problem is that all of the elements of the array passed to one(...) are evaluated strictly before the function is called. That's what causes the endless recursion. That wouldn't be a problem in a lazily evaluated language like Haskell.

I'm currently testing this workaround, which seems to be able to do the job at least for the time being:

extension Gen {
    public static func lazy(_ gen: @escaping () -> Gen<A>) -> Gen<A> {
        return Gen<Bool>.pure(true).flatMap { _ in
            return gen()
        }
    }
}

// then call with:
(Gen<List>.lazy { List.arbitrary }).map ...

[felix91gr]

Ah! Of course. I see, the compiler is trying to unroll the recursion right away.

Thanks for explaining it again ^^

Yes, making a lazy extension to it like you're doing is probably the best approach.

Maybe SwiftCheck needs a LazyGen? 🤔 I don't know enough about its design, so I couldn't say.

[jgongo]

I'd love to see such a functionality included in SwiftCheck. Swift in fact includes laziness to some extent with the use of autoclosures.

Unfortunately this seems to be available only with parameters, not as a general modifier, so I guess you can't have something like an [@autoclosure ()-> Gen<A>] so you could change the signature of one(of:) from:

public static func one<S : BidirectionalCollection>(of gs : S) -> Gen<A>
    where S.Iterator.Element == Gen<A>, S.Index : RandomType

to:

public static func one<S : BidirectionalCollection>(of gs : S) -> Gen<A>
    where S.Iterator.Element == @autoclosure () -> Gen<A>, S.Index : RandomType

Maybe they could add a one(of:) method with a variable number of @autoclosure arguments the same way zip methods are generated?

[jgongo]

BTW, I think the lazy extension could be as simple as:

extension Gen {
    public static func lazy(_ gen: @autoclosure () -> Gen<A>) -> Gen<A> {
        gen()
    }
}