swiftgenericsfunctional-programmingunfold

Defining a generic unfoldr function


func unfoldr<A, B>(_ f: @escaping (B) -> (A, B)?) -> (B) -> UnfoldFirstSequence<A> {
    return { b in sequence(
        first: b, next: { x in
                switch f(x) {
                case .some(let(a, b)):
                    return Optional(a)
                default:
                    return Optional.none
            }
            }
        )
    }
}

With this definition, I am getting the following error:

Cannot convert value of type 'B' to expected argument type 'A'.

Is there some way of solving this issue and definining this function ?


Solution

  • Your sequence doesn't seem to be a UnfoldFirstSequence. Your sequence seems to have a state B, and f is responsible for producing a new state and an element for the sequence. An UnfoldFirstSequence has no state that you can control. You can only produce the next element from the previous element.

    Your sequence can be modelled by the more general UnfoldSequence, which has a State generic parameter. In fact, an UnfoldFirstSequence<T> is just an UnfoldSequence<T, (T?, Bool)>! See why the former is a special case of the latter by reading the source code :)

    You can create such a sequence using sequence(state:next:).

    func unfoldr<A, B>(_ f: @escaping (B) -> (A, B)?) -> (B) -> UnfoldSequence<A, B> {
        return {
            sequence(state: $0) { x in
                guard let (a, b) = f(x) else { 
                    return nil 
                } 
                x = b 
                return a
            }
        }
    }
    

    Example:

    let seq = unfoldr { x -> (String, Int)? in
        if x == 10 {
            return nil
        } else {
            return ("\(x)", x + 1)
        }
    }
    seq(0).forEach { print($0) }