Memoization in enums


(Tierry Hörmann) #1

Hi all

I discovered that memoization can be pretty hard to implement for pure functions in enums and I wanted to ask if anyone knows of a good way to implement it?
To explain the problem further look at this example of a primitive lazy linked list:

public struct LazyList<T> {
    let root: LLE<T>
    
    init(_ root: LLE<T> = LLE<T>.End) {
        self.root = root
    }
    
    public var hd: T? {
        get {return root.val()}
    }
    
    lazy private var tail: LLE<T> = self.root.tail()()
    public var tl: LazyList<T> {
        mutating get {
            return LazyList<T>(tail)
        }
    }
}

enum LLE<T> {
    case End
    indirect case Node(T, () -> LLE<T>)
    
    func val() -> T? {
        switch self {
        case let .Node(v, _):
            return v
        default:
            return nil
        }
    }
    
    func tail() -> () -> LLE<T> {
        switch self {
        case let .Node(_, tl):
            return tl
        default:
            assert(false, "Can't call tail on empty list")
            return {self}
        }
    }
}

For the memoization I need a separate struct which wraps the actual linked list. For this primitive list this would work, but as soon as you want to implement “count”, it gets very complicated: A call of count would require the evaluation of the tail, so it would make sense to memoize the tail (and its computed count property). But this way it is not possible, because a struct does not allow to have a stored property that references itself. And as I cannot have any stored property at all in a enum, I don’t find a way how I could implement memoization for a pure function like “tail” in the enum.

So is it somehow possible to memoize the output of a pure function in an enum?

Greetings
Tierry Hoermann