Trouble using a local func with parameter pack args

Using Swift
1

I have a working generic memoize function that uses parameter packs, but I'm trying to extend it so the memoized function can be called recursively. I'm having trouble using the local wrapper function:

func memoize<each T: Hashable, U>(_ f: @escaping ((repeat each T)->U, repeat each T)->U) -> (repeat each T) -> U {
  var cache: [Int: U] = [:]
  func wrap(_ args: repeat each T) -> U {
    var h = Hasher()
    for arg in repeat each args {
      h.combine(arg)
    }
    let key = h.finalize()
    if let v = cache[key] {
      return v
    }
    let v = f(wrap, repeat each args)
    //        `- error: pack expansion requires that 'each T' and 'repeat each T' have the same shape
    //        `- error: cannot convert value of type '(repeat each T) -> U' to expected argument type
    cache[key] = v
    return v
  }
  return wrap
  //     `- error: pack expansion requires that 'each T' and 'repeat each T' have the same shape
  //     `- error: cannot convert return expression of type '(repeat each T) -> U' to return type '(repeat each T) -> U'
}

It seems like the type of wrap is not matching (repeat each T)->U, so it can't be returned or passed as the first argument to the wrapped function. I'm also not certain about the args expansion when calling f, but I think the compiler just has a problem with wrap.

An example usage is like:

let fact = memoize { f, x in
   if x == 0 {
     return 1
   }
   return x * f(x - 1)
}

Which the compiler does seem to be happy with.

I'm using Swift 6.0.2.

Any ideas on this one?

1 Like
2

I'd do something like the following instead. Relying only on a Hasher does not account for possible hash collisions, so I'd create a private container type that properly conforms to Hashable and store that in the dictionary.

func memoize<each In: Hashable, Out>(_ factory: @escaping (repeat each In) -> Out) -> (repeat each In) -> Out {
    var memo: [Container<repeat each In>: Out] = [:]
    return { (pack: repeat each In) -> Out in
        let container = Container(repeat each pack)
        if let result = memo[container] {
            return result
        } else {
            let result = factory(repeat each pack)
            memo[container] = result
            return result
        }
    }
}

private struct Container<each T> {
    let value: (repeat each T)

    init(_ value: repeat each T) {
        self.value = (repeat each value)
    }
}

extension Container: Equatable where repeat each T: Equatable {
    static func == (lhs: Container<repeat each T>, rhs: Container<repeat each T>) -> Bool {
        for (left, right) in repeat (each lhs.value, each rhs.value) {
            guard left == right else { return false }
        }
        return true
    }
}

extension Container: Hashable where repeat each T: Hashable {
    func hash(into hasher: inout Hasher) {
        for element in repeat each value {
            hasher.combine(element)
        }
    }
}
3

Thanks for that feedback and I'll definitely manage the cache key the way you suggest. My compiler problem, however, is with returning the wrap local function from the memoize function. If I try to return a closure as in your example, then I can't pass the wrapped memoize function to the factory function to enable recursion. If I try to capture the closure with a let binding, then the compiler complains about using a binding before it's created.

Here is a simpler example:

func curry<T, each U, V>(_ arg: T, _ f: @escaping (T, repeat each U) -> V) -> (repeat each U) -> V {
  func wrap(_ args: repeat each U) -> V {
    f(arg, repeat each args)
  }
  return wrap
  //     `- error: pack expansion requires that 'each U' and 'repeat each U' have the same shape
  //     `- error: cannot convert return expression of type '(repeat each U) -> V' to return type '(repeat each U) -> V'
}

I get the same error here as my first post, but works if written this way:

func curry<T, each U, V>(_ arg: T, _ f: @escaping (T, repeat each U) -> V) -> (repeat each U) -> V {
  return { (args: repeat each U) in
    f(arg, repeat each args)
  }
}

So it seems I can return a parameter pack powered closure, just not a named function.