My question is very simple, how do I make this code lazy:
/*
input: [
[1, 2],
[3, 4],
[5, 6]
]
output: [
[1, 3, 5],
[1, 3, 6],
[1, 4, 5],
[1, 4, 6],
[2, 3, 5],
[2, 3, 6],
[2, 4, 5],
[2, 4, 6],
]
*/
func combinations<T>(options: [[T]]) -> [[T]] {
guard let head = options.first else {
return [].map({ [$0] })
}
if options.count == 1 {
return head.map({ [$0] })
}
let tailCombinations = combinations(options: Array(options.dropFirst()))
return head.flatMap({ option in
return tailCombinations.map({ combination -> [T] in
return [option] + combination
})
})
}
The code above works to calculate the combinations, but it does so creating the entire array of arrays in memory.
What I need is to have it return something like LazySequence<Array<T>>
, except the Swift type system doesn't let me do something that generic.
Any ideas how to achieve this and keep the functional style?
Ps.: I did think of another way to solve this problem with generators and keeping track of indexes, but I don't wanna keep track of any state, I want a pure functional (as in FP) solution. Haskell does it by default, btw, and I'm looking for the same thing.
EDIT: I've managed to solve part of the problem, the type system, with AnyCollection
func combinations<T>(options: [[T]]) -> LazyCollection<AnyCollection<[T]>> {
guard let head = options.first else {
return AnyCollection([].lazy.map({ [$0] })).lazy
}
if options.count == 1 {
return AnyCollection(head.lazy.map({ [$0] })).lazy
}
let tailCombinations = combinations(options: Array(options.dropFirst()))
return AnyCollection(head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + $0 })
})).lazy
}
But when I use the function, it loads the entire collection in memory, i.e., not lazy.
EDIT 2: Doing some more investigation, turns out the problem is with AnyCollection
// stays lazy
let x1 = head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + $0 })
})
// forces to load in memory
let x2 = AnyCollection(head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + $0 })
}))
Not sure how to solve this yet.
Here is what I came up with:
The main difference to this solution is that the recursive call creates a sequence of the first
N-1
options, and then combines each element of that sequence with each element of the last option. This is more efficient because the sequence returned from the recursive call is enumerated only once, and not once for each element that it is combined with.Other differences are:
.lazy
on theAnySequence
if that sequence is already lazy. The return type is therefore "simplified" toAnySequence<[T]>
.CollectionOfOne
to create a single-element sequence for the empty array.options.count == 1
separately is not necessary for the algorithm to work (but might be a possible performance improvement).A completely different approach is to define a custom collection type which computes each combination as a function of the index, using simple modulo arithmetic:
No extra storage is needed and no recursion. Example usage:
Output:
Testing with
this collection-based method turned out to be faster then the my above sequence-based method by a factor of 2.
I found one possible solution, but I'll leave this answer not accepted for a while to see if someone knows a better one.
The solution was to use
AnySequence
instead ofAnyCollection
. I'm not sure why though, I'd still like to have theAnyCollection
interface rather thanAnySequence
, since it provides me with a few more methods, likecount
.