Recursive Swift Either Enum with Generic Associated Values

Question

I want to develop a recursive Either type as a Swift enum (at least a partially working version (;), and so have been playing around with generics (trying to work with the type system).

Here is what I have so far:

enum NumericEitherEnum<Left, Right> {
  case left(Left)
  case right(Right)

  var left: Left? {
    switch self {
      case .left(let leftie) where leftie is NumericEitherEnum<Int, Float>:
        return (leftie as? NumericEitherEnum<Int, Float>)?.left // This won't work (obviously)
      case .left(let left):
        return left
      case .right(_):
        return nil
    }
  }

  var right: Right? {
    switch self {
      case .left(_):
        return nil
      case .right(let right) where right is NumericEitherEnum:
        return (right as? NumericEitherEnum)?.right // This assumes the generic parameters of Left, Right in the current enum so won't work.
      case .right(let right):
        return right
    }
  }
}

I get cryptic diagnostic error messages in Xcode, which I haven't been able to get around:

'Replace (leftie as? NumericEitherEnum<Int, Float>)? with NumericEitherEnum<Int, Float>'
'Enum case 'left' cannot be used as an instance member'

What I am trying to achieve:

print(NumericEitherEnum<NumericEitherEnum<Int, Float>, NumericEitherEnum<Int, Float>>.left(.left(3)).left ?? "failed :(") // Parses the innermost value 3

The fix-it doesn't fix the error or advise how to actually address the underlying cause. I think this is probably an edge case for the compiler to parse (maybe even bug) ;). I also realise that in fact it doesn't make sense logically to return an Int for a Left? type but is there any way I can express this within the type system (I tried associated types but I still don't know how to make this dynamic). There's also a problem to handle nested enums that have a different generic type signature (not sure how to express this).

How can I resolve this issue in a better way? Ideally, I want to have a clean call site without too much indirection and extra data structures but would be open to trying out a different data structure if this isn't practically achievable.

Pranav Kasetti Pranav Kasetti · Accepted Answer · 2021-03-05T11:45:02

So I discovered that Swift 2 introduced support for recursive enums ages ago - source! While this is great, I didn't manage to find any SO questions for this specific problem i.e. Generic Recursive Enums that had also been answered (here). I will summarise the final (partial solution) code now.

It turns out that I needed to describe what the problem is in terms of data structures. Essentially we want .left to contain either a value of type Left or a RecursiveEither<Left, Right>. With this simple idea, we can create two enums - one for the wrapper enum, and one for the nested enum which can take a Value or another wrapper.

enum RecursiveEither<Left, Right> {
  case left(ValueOrLeftOrRight<Left, Left, Right>)
  case right(ValueOrLeftOrRight<Right, Left, Right>)
  
  var left: Left? {
    guard case .left(let leftie) = self else { return nil }
    return leftie.left
  }

  var right: Right? {
    guard case .right(let rightie) = self else { return nil }
    return rightie.right
  }
}

enum ValueOrLeftOrRight<Value, Left, Right> {
  case value(Value)
  indirect case left(ValueOrLeftOrRight<Left, Left, Right>)
  indirect case right(ValueOrLeftOrRight<Right, Left, Right>)
  
  var left: Left? {
    switch self {
    case .value(let left): return left as? Left
    case .left(let content): return content.left
    default: return nil
    }
  }

  var right: Right? {
    switch self {
    case .value(let right): return right as? Right
    case .right(let content): return content.right
    default: return nil
    }
  }
}

The call site is nice with this design:

let e = RecursiveEither<Int, Int>.left(.left(.left(.left(.value(3)))))

That being said, there are still limitations to this answer - assuming Left and Right won't change even in nested Either. Also, it's possible to design this differently with only one indirect case to wrap the Either type in another associated value - that might be more memory efficient since fewer frames get pushed onto the call stack at runtime.

I have posted a gist with attempts on this problem.

If anyone has suggestions to improve this implementation, feel free to add to this.

Recursive Swift Either Enum with Generic Associated Values

1 Answers