The main thing that I want to change is only the structure Set, if some code below might gain type inference, that is perfectly fine, but overall emptySet and useSet must remain unchanged.
struct Set {
var elements: [String: Any] = [:]
}
let emptySet: () -> Set = {
func makeSet(_ xs: [Int]) -> Set {
func contains(_ i: Int) -> Bool {
return xs.contains(i)
}
return Set(elements: [
"insert": { (i: Int) in
if contains(i) {
return makeSet(xs)
} else {
return makeSet([i] + xs)
}
},
"member": contains,
"size": { () -> Int in
return xs.count
}
])
}
return makeSet([])
}
// example client
func useSets() -> Int {
let s1 = emptySet()
let s2 = (s1.elements["insert"] as! (Int) -> Set)(34)
let s3 = (s2.elements["insert"] as! (Int) -> Set)(34)
let s4 = (s3.elements["insert"] as! (Int) -> Set)(19)
if (s4.elements["member"] as! (Int) -> Bool)(42) {
return 99
} else if (s4.elements["member"] as! (Int) -> Bool)(19) {
return 17 + (s3.elements["size"] as! () -> Int)()
} else {
return 0
}
}
// 18
let a = useSets()
I am refactoring the Set struct to use a protocol-oriented approach with the DictSet protocol. This protocol defines three methods, insert, member, and size, each returning a closure of type MyClosureType. The DictImpl struct conforms to DictSet and uses these closures to implement its functionality. This approach provides better type safety and encapsulation compared to the previous implementation.
Here is the new code... just make it work :)
typealias MyClosureType = (Int) -> Any
protocol DictSet {
func insert() -> MyClosureType
func member() -> MyClosureType
func size() -> MyClosureType
}
struct DictImpl: DictSet {
var elements: [String : MyClosureType] = [:]
init() {
elements["insert"] = insert()
elements["member"] = member()
elements["size"] = size()
}
func insert() -> MyClosureType {
<#code#>
}
func member() -> MyClosureType {
<#code#>
}
func size() -> MyClosureType {
<#code#>
}
}
The issue is with how I've assigning closures to the elements dictionary in DictImpl. Maybe I should assign the closures themselves, not the result of calling them. Still new to this stuff.
Edit: I would like to keep the idea of how the dictionary is implemented inside emptySet. I get that useSets won't be that wordy after the new implementation, but lets and if statements must be there. I just don't know how would the new code would affect the dictionary inside emptySet (or how to implement it)
I believe I know the FP exercise you're trying to achieve. The goal here (if I'm correct about what you're doing) is to demonstrate functions as the storage, rather than actually storing data. So the values themselves are never in the Set; just whether they are contained. This can be quite powerful for reasons I'll demonstrate at the end, so this is not a purely academic exercise.
Your initial code goes about this incorrectly however. Here is how you'd achieve this in Swift, in all its Functional Programming glory.
struct FunctionSet {
static let empty = Self(member: { _ in false }, size: 0)
let member: (Int) -> Bool
let size: Int
func insert(_ x: Int) -> Self {
if member(x) { self }
else { Self(member: { x == $0 || member($0) },
size: size + 1)
}
}
}
(size should be Int rather than () -> Int here, both logically and for performance reasons. But it's trivial to make it a closure if you like. It's also possible to make insert a closure like you had, but there really isn't any reason to do that. It just adds unnecessary indirection because it is invariant on the data.)
Your useSets code still works as you expect, just without all the as!:
func useSets() -> Int {
let s1 = FunctionSet.empty
let s2 = s1.insert(34)
let s3 = s2.insert(34)
let s4 = s3.insert(19)
if s4.member(42) {
return 99
} else if s4.member(19) {
return 17 + s3.size
} else {
return 0
}
}
The key point is that FunctionSet contains only functions. It does not actually contain 34 and 19. It just contains a function (member) that will return true if the value is contained.
This is a useful tool if the set could be very large and is defined by a rule. To explore this, let me define a slightly simpler version that does not track its size so we can more easily deal with "infinite" sets (not really infinite since Int is finite, but let's say "very large and hard to size").
struct FunctionSet {
static let empty = Self(member: { _ in false })
let member: (Int) -> Bool
func insert(_ x: Int) -> Self {
if member(x) { self } else { Self(member: { x == $0 || member($0) }) }
}
}
Now I can create some very interesting sets (and demonstrate why size is annoying to implement here):
let evens = FunctionSet(member: { $0.isMultiple(of: 2)})
let evensAnd101 = evens.insert(101)
Capturing "all even numbers and also 101" would be impractical with a traditional Swift Set. It would be too large and lookups would be very slow. But FunctionSet implements this highly efficiently.
Now, how does this apply to protocol oriented programming? The point of POP is to allow us to write algorithms based on a promised interface. That would look like this:
protocol SetProviding {
static var empty: Self { get }
var member: (Int) -> Bool { get }
func insert(_: Int) -> Self
}
And FunctionSet definitely does this, so we can retroactively conform it with no extra work:
extension FunctionSet: SetProviding {}
Nothing about SetProviding requires that this be implemented with functions. We could implement it using Swift's built-in Set:
struct SetSet: SetProviding {
static var empty: Self { Self(values: []) }
private let storage: Set<Int>
// The double {{}} here is because member returns a function
var member: (Int) -> Bool { { storage.contains($0) } }
init(values: some Sequence<Int>) { storage = Set(values)}
func insert(_ x: Int) -> SetSet { Self(values: storage.union([x])) }
}
And with this, I can rewrite useSets to handle any kind of SetProviding, which I think was your goal:
func useSets(startingWith s1: some SetProviding) -> Int {
let s2 = s1.insert(34)
let s3 = s2.insert(34)
let s4 = s3.insert(19)
if s4.member(42) {
return 99
} else if s4.member(19) {
return 17
} else {
return 0
}
}
useSets(startingWith: SetSet.empty)
useSets(startingWith: evensAnd101)
useSets is not particularly interesting, but here is a way to elegantly add a new union method onto any SetProviding type demonstrating the real power of protocols and the power of functions:
extension SetProviding {
func union(_ other: some SetProviding) -> some SetProviding {
FunctionSet(member: { member($0) || other.member($0) })
}
}