I decided to try what neat fp stuff I can use in swift. A famous heterogeneous list was chosen for fiddling.
I have defined it as such.
precedencegroup ListConsPrecedence {
associativity: right
}
infix operator |- : ListConsPrecedence
protocol PairComponent {
associatedtype L
associatedtype R: PairComponent
}
struct Cons<A, B: PairComponent>: PairComponent {
typealias L = A
typealias R = B
}
struct End: PairComponent {
typealias L = End
typealias R = End
}
indirect enum HList<T: PairComponent> {
case cons(T.L, HList<T.R>), end
}
func |- <T, K>(l: T, r: HList<K>) -> HList<Cons<T, K>> {
.cons(l,r)
}
func |- <K>(l: K, r: HList<End>) -> HList<Cons<K, End>> {
.cons(l,.end)
}
let a = "Hello, there!" |- 42 |- 0.5 |- .end
So far is was working, but the problem occurred once I decided to use it.
func elimHList<T>(_ hlist: HList<T>) -> Double? {
func elim<Tail>(_ innerHlist: HList<Cons<Double, Tail>>) -> Double? {
switch innerHlist {
case .cons(let val, _):
return val
default:
fatalError()
}
}
func elim<L, Tail>(_ innerHlist: HList<Cons<L, Tail>>) -> Double? {
switch innerHlist {
case .cons(_, let tail):
return elim(tail)
default:
fatalError()
}
}
func elim(_ innnerHlist: HList<End>) -> Double? {
return nil
}
return elim(hlist)
}
Strangely, compiler complaints: Cannot convert value of type 'HList<Cons<L, Tail>.R>' (aka 'HList<Tail>') to expected argument type 'HList<End>' and Cannot convert value of type 'HList<T>' to expected argument type 'HList<End>'. I don't see why it wants to unify End and T. Can somebody hint at me on why it doesn't produce the desired behaviour?
Calling elim(hlist) and elim(tail) does not provide you any dispatch. Out of 3 overloads of elim() compiler attempts to pick one at compilation time, and will always use it regardless of value of T. Looks like compiler attempts to use the last one, which expects HList<End>.
If I'm not mistaken, what you are trying to achieve is called Generalized abstract data types (GADTs)?, which currently not supported in Swift. But you can emulate them using protocols and visitor pattern:
protocol HList {
func accept<V: HListVisitor>(_ visitor: V) -> V.Result
}
protocol HListVisitor {
associatedtype Result
func visitCons<Head, Tail: HList>(head: Head, tail: Tail) -> Result
func visitEnd() -> Result
}
struct End: HList {
func accept<V: HListVisitor>(_ visitor: V) -> V.Result {
return visitor.visitEnd()
}
}
struct Cons<Head, Tail: HList>: HList {
var head: Head
var tail: Tail
func accept<V: HListVisitor>(_ visitor: V) -> V.Result {
return visitor.visitCons(head: head, tail: tail)
}
}
func elimHList<T: HList>(_ hlist: T) -> Double? {
struct DoubleEliminator: HListVisitor {
func visitCons<Head, Tail: HList>(head: Head, tail: Tail) -> Double? {
if let doubleHead = head as? Double {
return doubleHead
}
return tail.accept(self)
}
func visitEnd() -> Double? {
return nil
}
}
return hlist.accept(DoubleEliminator())
}
I come to understanding swift dispatch model from this example:
protocol G {
associatedtype K
var v: K { get }
}
struct L<A>: G { let v: A }
struct R<A>: G { let v: A }
struct J<T: G>: G {
typealias K = T
let v : K
}
func dispatchDemo<T>(_ arg: J<L<T>>) {
print("J<L<\(T.self)>>")
}
func dispatchDemo<T>(_ arg: J<R<T>>) {
print("J<R<\(T.self)>>")
}
func dispatchDemo<T>(_ arg: J<T>) {
print("J<\(T.self)>")
}
dispatchDemo(J<L<Int>>.init(v: .init(v: 0)))
dispatchDemo(J<R<String>>.init(v: .init(v: "")))
extension Int: G {
typealias K = Self
var v: Int { self }
}
dispatchDemo(J<Int>.init(v: 0))
It prints as expected:
J<L<Int>>
J<R<String>>
J<Int>
It suggest that swift does resolve method implementation based on type matching and thus elim() should work. Apparently, compiler cannot handle the case when overload resolution must happen within a 'generic context' (I don't know the correct word), and it looks like an issue to me, because it forbids some valid programs that rely on polymorphic recursion to be written.
Is there a reason it shouldn't work?
Your example demonstrates overload resolution, but not a dispatch. I call "dispatch" a situation where type information is first erased, and later is recovered. In your example there is not type erasure of any sort - at the call site compiler sees the full concrete type of the argument. But the following example will not work:
func dispatchDemo<T>(_ arg: J<L<T>>) {
print("1")
}
func dispatchDemo<T>(_ arg: J<R<T>>) {
print("2")
}
func dispatchDemo<T>(_ arg: J<T>) {
print("3")
}
func eraser<T>(_arg: J<T>) {
dispatchDemo(arg)
}
eraser(J<L<Int>>.init(v: .init(v: 0))) // prints "3"
eraser(J<R<String>>.init(v: .init(v: ""))) // prints "3"
eraser(J<Int>.init(v: 0)) // prints "3"
I don't have sufficient knowledge to explain why this is done in Swift this way. It seems to be challenging, but not impossible, though it probably has its share of counter-arguments. But anyway that's the current state of things.
Note that to achieve true dynamic dispatch compiler would have to synthesize code doing dynamic type casts. For simple cases (when you need to cast to concrete types or protocols), you can do this manually. But for more general case, like in dispatchDemo it is not possible to do it ad-hoc. Sometimes you can make some workarounds using protocols design ahead of time to facilitate dynamic dispatch. To be able to do it ad-hoc, we would need generalised existentials.
If we would have generalised existentials, I think you could write something like this:
func dispatchDemo_dispatcher<T>(_ arg: J<T>) {
if let<U> a: J<L<U>> = arg as? (any<V> J<L<V>>) {
return dispatchDemo(a) // prints "1"
}
if let<U> a: J<R<U>> = arg as? (any<V> J<R<V>>) {
return dispatchDemo(a) // prints "2"
}
dispatchDemo(a) // prints "3"
}
func eraser<T>(_arg: J<T>) {
dispatchDemo_dispatcher(arg)
}
eraser(J<L<Int>>.init(v: .init(v: 0))) // prints "1"
eraser(J<R<String>>.init(v: .init(v: ""))) // prints "2"
eraser(J<Int>.init(v: 0)) // prints "3"
But currently we have neither generalised existentials nor opening existentials, so the syntax I've used is completely made up:
-
any<V> J<L<V>> - generalised existential type, erasing type V, but preserving information that argument of J is L.
-
let<U> a = - syntax for opening existentials
I have played a bit more and discovered that this code generates nil:
Code
func elimHList<T>(_ hlist: HList<T>) -> Double? {
func elim<Tail>(_ innerHlist: HList<Cons<Double, Tail>>) -> Double? {
switch innerHlist {
case .cons(let val, _):
return val
default:
fatalError()
}
}
func elim<L, Tail>(_ innerHlist: HList<Cons<L, Tail>>) -> Double? {
switch innerHlist {
case .cons(_, let tail):
return elim(tail)
default:
fatalError()
}
}
// not concrete anymore
func elim<K>(_ innnerHlist: HList<K>) -> Double? {
return nil
}
return elim(hlist)
}
print(elimHList(a))
This behavior breaks pattern displayed in this bit of code:
where invocations of dispatchDemo print what is expected. At this point, current behaviour looks like a bug and I'll report it.