Challenge: Flattening nested optionals

#1

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.

3 Likes
Unexpected return type from keyPath subscript
#2
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!

(Gwendal Roué) #3

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
2 Likes
#4

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
    }
  }
}
(Jordan Rose) #5

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

3 Likes
#6

This seems to work:

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

let unwrapped = nestedOptional.flatMap { $0! }

unwrapped is Optional(1)

(Jens Persson) #7

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
(Jens Persson) #8

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)
(Michel Fortin) #9

v as? Int is even simpler:

let v: Int??????????????????????????????????????????????????????????? = 123
let flattenedToOneLevelOfOptionality = v as? Int
(Jens Persson) #10

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.

#11

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)))))))))))))))))))))
(Jens Persson) #12

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

#13

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.