0

I'm trying to implement flatmap via generics. (Yes, flatmap is already a part of the language.) My attempt uses generic, overloaded functions to accomplish this. (Probably not the most efficient. I know. I've already got a working imperative version.) What I find unexpected is that flatten< T, U >( _ elem: T ) -> [ U ] is consuming arrays that flatten is called with even though the overload func flatten< T, U >( _ ary: [ T ] ) -> [ U ] exists.

I can tell what's going wrong, I just can't seem to see why, or even where to look to learn why and possibly fix it.

I've even tried a few casts, just to see, and that produced errors, which made sense to me. Why cast a T to T or [ T ] to [ T ]?. Also changed ary to elem to see if that was causing problems with the overload semantics. Produced the same output.

import Foundation

func flatten< T, U >( _ elem:    T   ) -> [ U ] {
    if let item = elem as? U {
        return [ item ]
    } else {
        return []
    }
}

func flatten< T, U >( _ ary:   [ T ] ) -> [ U ] {
    if ary.count == 0 {
        return []
    }

    return flatten( ary.first ) + flatten( Array( ary.dropFirst() ) )
}

let x: [ Int ] = flatten( [ 1, 2, [ 3, 4 ], [ [ 5, 6 ], nil, 7 ], 8, 9 ] )
print( x )  // Prints [1, 2, 8, 9 ] instead of [1, 2, 3, 4, 5, 6, 7, 8, 9]
mfaani
  • 33,269
  • 19
  • 164
  • 293
  • 1
    Compare https://stackoverflow.com/q/41980001/2976878 – overload resolution for the recursive call to `flatten` happens in the implementation of `flatten` *itself*. From that location, all the compiler knows about `ary.first` is that it's some type `T?`; therefore it cannot dispatch to the overload of `flatten` that takes a `[T]`. – Hamish Oct 25 '17 at 20:28
  • 1
    If your questions ever get marked as duplicated, just make an edit and explain why it's not a duplicate (hopefully the question would get reopened). Additionally if your questions are purely a repost, then don't repost. If they are related, then link them and if needed explain how they are related. If they aren't, then it's best to not discuss them in your question. – mfaani Oct 25 '17 at 20:54
  • @Hamish, thank you for your reply and that link. Lots of good stuff there. Thornier than I thought it might be. –  Oct 25 '17 at 21:45
  • @Honey, thanks. I would have, but the questions were, in fact, duplicates. Unintentional ones. That's why I prefaced this question. I do re/search for my answers, but with Swift, it's still very... unusual to me. I'll get a compiler error for ambiguous subscripts, for instance, and get nowhere finding out why because the real error was actually a type mismatch. Whereas, if the compiler said "Cannot convert ArraySlice...", I wouldn't have even had to post my (other) question. I'd have just fixed my n00b mistake. :). –  Oct 25 '17 at 21:57

1 Answers1

0

The compiler is getting confused by the use of the wrapped optional comming out of ary.first which will definitely go to the first function signature. But even fixing that will still leave some ambiguity on the processing of simpler cases such as [[1,2][3,4]].

Another way to approach this would be to handle all the types internally rather than leaving it up to the compiler:

func flatten<U>( _ ary:[Any] ) -> [ U ]
{
    func makeFlat(_ flat:[U], _ elem:Any) -> [U]
    {
       if let item   = elem as? U     { return flat + [item] }
       if let ary    = elem as? [U]   { return flat + ary }
       if let subAry = elem as? [Any] { return flat + flatten(subAry) }
       return flat
    }
    return ary.reduce([U](),makeFlat)
}
Alain T.
  • 40,517
  • 4
  • 31
  • 51
  • Thanks. Yup, I knew something was going on. Some of the resources mentioned in the question Hammish linked were pretty illuminating on the subject. I managed to get a few others versions of flatmap working. (Not quite what you did, though. Nice!) I thought to try out a recursive version with generics, and look at all the learning that occurred here. haha –  Oct 26 '17 at 02:09