Recursive Enumerations with Generics in Swift

Question

I'm new to Swift. I was trying to implement a binary tree with recursive enumerations and generics:

enum BinaryTree<T> {
  indirect case Node(T, BinaryTree<T>, BinaryTree<T>)
  case Nothing
}

func inorder<T>(_ root: BinaryTree<T>) -> [T] {
  switch root  {
  case .Nothing: 
    return []
  case let .Node(val, left, right):
    return inorder(left) + [val] + inorder(right) 
  }
}

Here's the error I got:

$ swift ADT.swift 
ADT.swift:83:20: error: cannot convert value of type 'BinaryTree<T>' to expected argument type 'BinaryTree<_>'
    return inorder(left) + [val] + inorder(right) 
                   ^~~~

However, this works:

func inorder<T>(_ root: BinaryTree<T>) -> [T] {
  switch root  {
  case .Nothing: 
    return []
  case let .Node(val, left, right):
    let l = inorder(left) 
    let r = inorder(right)
    return l + [val] + r
  }
}

Is there any mistakes in my syntax? Thanks!

I'm using Swift 3.0.

Answer 1

Update
So I tried to condense the problem into minimal example code that fails to compile and asked a question myself and filed SR-4304. Turns out the answer is that this really is a bug in the compiler.

Original Answer
As far as I can tell, your syntax is perfectly valid. It seems that the Swift compiler’s type inference seems to need a nudge in the right direction which your second solution apparently provides. As I experienced several similar problems in the past, especially regarding the + operator, your question inspired me to try several other ways to join the arrays. These all work (I am just showing the return statements and supporting functions for the last three cases):

return (inorder(left) as [T]) + [val] + inorder(right)
return Array([inorder(left), [val], inorder(right)].joined())
return [inorder(left), [val], inorder(right)].reduce([], +)
return [inorder(left), [val], inorder(right)].flatMap { $0 }

func myjoin1<T>(_ arrays: [T]...) -> [T]
{
    return arrays.reduce([], +)
}
return myjoin1(inorder(left), [val], inorder(right))

func myjoin2<T>(_ array1: [T], _ array2: [T], _ array3: [T]) -> [T]
{
    return array1 + array2 + array3
}
return myjoin2(inorder(left), [val], inorder(right))

extension Array
{
    func appending(_ array: [Element]) -> [Element]
    {
        return self + array
    }
}
return inorder(left).appending([val]).appending(inorder(right))

Calling the operator as a function compiles, too:

return (+)(inorder(left), [val]) + inorder(right)

It would be great if somebody with more intimate knowledge of the Swift compiler could shed some light on this.