Challenge: Flattening nested optionals

Here’s a little programming puzzle:

Can you write a Swift function that will flatten any arbitrary Optional, no matter how deeply nested, down to a single level of optionality?

That is, the function accepts an Optional, determines whether the deepest inhabited layer contains nil or a non-Optional value, and returns the result as a single Optional without any nesting.

In particular, it should work without knowing what type is ultimately wrapped at the bottom of the pile, and it should even work if the outermost type is an Any? hiding unknown additional Optionals inside.

4 Likes
func flatten(_ opt: Any?) -> Any? {
  guard let unwrapped = opt else {
    return nil
  }

  if Mirror(reflecting: unwrapped).displayStyle == .optional {
    return flatten(Mirror(reflecting: unwrapped).children.first!.value)
  } else {
    return Optional(unwrapped)
  }
}

I think this will do it. I feel a bit dirty after writing this, but hey, it seems to do the job. Let me know if it does/doesn't work, it's late and I'm going to go to bed now. :slight_smile:

I ended up using Mirror to avoid having to create a protocol, but a protocol-based solution may be more desirable if you want "vanilla" Swift code. Perhaps there exists a way to do this without either caveat!

Another try:

private protocol _OptionalProtocol {
    var _deepUnwrapped: Any? { get }
}
extension Optional: _OptionalProtocol {
    fileprivate var _deepUnwrapped: Any? {
        if let wrapped = self { return deepUnwrap(wrapped) }
        return nil
    }
}
func deepUnwrap(_ any: Any) -> Any? {
    if let optional = any as? _OptionalProtocol {
        return optional._deepUnwrapped
    }
    return any
}

deepUnwrap(1)                                                       // 1
deepUnwrap(Optional<Int>.none)                                      // nil
deepUnwrap(Optional<Int>.some(1))                                   // 1
deepUnwrap(Optional<Optional<Int>>.none)                            // nil
deepUnwrap(Optional<Optional<Int>>.some(Optional<Int>.none))        // nil
deepUnwrap(Optional<Optional<Int>>.some(Optional<Int>.some(1)))     // 1
7 Likes

Well done, that was quick!

I posted this puzzle because I only just figured out how to do it yesterday, after having previously tried unsuccessfully some months ago.

The solution I had in mind is very similar to @gwendal.roue’s, though singly-recursive rather than bouncing between two functions:

protocol Flattenable {
  func flattened() -> Any?
}

extension Optional: Flattenable {
  func flattened() -> Any? {
    switch self {
    case .some(let x as Flattenable): return x.flattened()
    case .some(let x): return x
    case .none: return nil
    }
  }
}

Can I ask why you'd want to do this? Is it not possible to flatten each level as you go?

3 Likes

This seems to work:

let nestedOptional = Optional<Optional<Optional<Int>>>.some(Optional<Int>.some(1))

let unwrapped = nestedOptional.flatMap { $0! }

unwrapped is Optional(1)

Unless I'm mistaken, that's equivalent to:

let nestedOptional: Int??? = 1
let unwrapped = nestedOptional.flatMap { $0! }
print(type(of: unwrapped)) // Optional<Int>

And it only works for 2 and 3 levels of optionality, ie it doesn't do what the OP asked for ("flatten any arbitrary Optional, no matter how deeply nested, down to a single level of optionality"):

let nestedOptional1: Int?? = 1
let nestedOptional2: Int??? = 1
let nestedOptional3: Int???? = 1
let nestedOptional4: Int????? = 1
let unwrapped1 = nestedOptional1.flatMap { $0! }
let unwrapped2 = nestedOptional2.flatMap { $0! }
let unwrapped3 = nestedOptional3.flatMap { $0! }
let unwrapped4 = nestedOptional4.flatMap { $0! }
print(type(of: unwrapped1)) // Optional<Int>
print(type(of: unwrapped2)) // Optional<Int>
print(type(of: unwrapped3)) // Optional<Optional<Int>>
print(type(of: unwrapped4)) // Optional<Optional<Optional<Int>>>

Also, for a single level of optionality

let nestedOptional0: Int? = 1

the expression won't compile:

let unwrapped0 = nestedOptional0.flatMap { $0! } // ERROR: Cannot force unwrap value of non-optional type 'Int'
1 Like

May I present this non-recursive solution which doesn't erase the type (but still works for Any?):

func funwrap<T>(_ v: T????????????????????) -> T? {
    return (v as? T?) ?? nil
}

It works for 0 through 20 levels of optionality.

Adding more than 20 gets hard on the type checker, and the following demonstration program will take 15 seconds to compile on my machine:

func funwrap<T>(_ v: T????????????????????) -> T? {
    return (v as? T?) ?? nil
}

let  v0: Int = 0
let  v1: Int? = nil
let  v2: Int?? = 2
let  v3: Int??? = nil
let  v4: Int???? = 4
let  v5: Int????? = nil
let v20: Int???????????????????? = 20

let result: [Int?] = [ funwrap(v0), funwrap(v1), funwrap(v2), funwrap(v3),
    funwrap(v4), funwrap(v5), funwrap(v20) ]

print(result)

$ time swiftc demo.swift
real 0m15.087s
user 0m14.762s
sys 0m0.270s
$ ./demo
[Optional(0), nil, Optional(2), nil, Optional(4), nil, Optional(20)]

But isn't the simplest solution to just use as? T? directly, like this:

// Here, v can have any level of optionality, although there will be a warning
// when flattening if the level is 0, 1 or 2:
let v: Int??????????????????????????????????????????????????????????? = 123
let flattenedToOneLevelOfOptionality = (v as? Int?) ?? nil

print(type(of: flattenedToOneLevelOfOptionality)) // Always prints Optional<Int>
dump(flattenedToOneLevelOfOptionality)
2 Likes

v as? Int is even simpler:

let v: Int??????????????????????????????????????????????????????????? = 123
let flattenedToOneLevelOfOptionality = v as? Int
1 Like

Ah, of course! :man_facepalming: So my "solution" (which is really just an unnecessary wrapper around as?) can be simplified into:

func funwrap<T>(_ v: T????????????????????) -> T? {
    return (v as? T)
}

It would be interesting to know if it is possible to rewrite this function (still non-recursively) so that it works for any level of optionality, ie not just 0 through 20, but 0 and more.

1 Like

In additional to be being limited by the number of question marks you write in the function definition, that also breaks down when Any is involved, by actually increasing the optionality up to the number of question marks:

let x: Any? = 0
let y = funwrap(x)
print(y.debugDescription)
// Optional(Optional(Optional(Optional(Optional(Optional(Optional(Optional(Optional(Optional(
//  Optional(Optional(Optional(Optional(Optional(Optional(Optional(Optional(Optional(Optional(
//   Optional(0)))))))))))))))))))))

You're right. I'm almost sure that I did double check that it worked for Any ... : P

Well, some people seem to think it’s a good idea to work with constructs like a dictionary of AnyKeyPaths to optional properties. I don’t personally vouch for that design, but it apparently exists.

Mostly I just wanted to see if I could, and it wasn’t immediately obvious how to test whether an Any is actually an Optional for recursive unwrapping.

What is more difficult, is to programmatically identify the bottom-most Wrapped type in an arbitrary stack of Optionals that includes Any?, especially if some layer other than the innermost is actually .none.

To me, the reason why you want want to do this is simple: Nested optionals are almost never useful, but they do arise sometimes due to quirks of the language (such as accessing a value from a dictionary for which the type of its values are Optional); therefore it's nice to have a function to call to flatten them to a single optional in one step. And could you elaborate on what you mean by "flatten each level as you go?" I'm not sure I understand.

1 Like

Has anyone figured out how to do this without casting the result to Any?? Is there some way preserve the type of the underlying value by using generics?

It’s actually cases like this that I’d suggest unwrapping things layer by layer. There’s a distinction between not having any value (outer optional) and having the value that is nil (inner optional). There’s really no point in making value type optional if it doesn’t

So one should unwrap the first layer to see if it has value at all, then unwrap the second layer to see if the stored value is nil.

Nonetheless, if you already know the bottom type those optionals are wrapping, this thread doesn’t really apply and you can just use as?.

1 Like

Is it possible for an Optional equivalent of the nested Slice<Slice<Slice<...>>> situation to occur naturally from some recursive function call, and render this exhaustive flattening useful?

That will work when you have a double-wrapped optional, of course, but that was just one example meant do demonstrate a broader point: Suppose you have a triple-wrapped optional—or a quadruple-wrapped optional—and you want do find out if the innermost value is nil. You would have to write more code for each additional layer of optionality. This kind of redundancy is a code smell to me.

Of course there is a difference between an optional, a double-wrapped optional, a triple-wrapped optional, and so on. They're all different types. For some cases that difference matters, so I fully understand why swift doesn't implicitly remove the extra layers of optionality, but in other cases, the difference does not matter and it would be nice to have a single function that removes all the extra layers of optionality.

True, but I'm looking for a function that would work for any bottom type and that doesn't cast the result to Any?.

I'm not sure what you're referring to.

To me, not handle each layer of optionality that appears explicitly is also a big code smell. It’s not like you keep wrapping each optional layer for the sake of it. And as I said, if you know the target type, just use as?. I haven’t even mentioned Any? anywhere.

What are you trying to do? The OP of this thread wants it to work with Any as an outer type. You already lose a lot of type information whether you cast it to Any? or not.

Perhaps it is. The main difference with optional is that it does mean different things at different places. Even then, you wouldn’t see a lot of deeply nested optionals (or slices, for that matter) in recursive functions.