MemoMonad (abstract for dynamic programming)

MemoMonad (abstract for dynamic programming)

--------------------- Lateset ----------------------------
interface MemoStructure<_memoState, _index> {
    state: _memoState;
    index: _index;
    memoAction: (memo: _memoState, _index: _index) => unknown;// this should be passed and used in func in the input of compute 
}

class MemoMonad<_memoState, _index, S extends MemoStructure<_memoState, _index>> {
    public memo: S;
    public rootState?: _memoState;

    constructor(memo: S) {
        this.memo = memo;
    }

    static of<_memoState, _index>
        (memo: MemoStructure<_memoState, _index>):
        MemoMonad<_memoState, _index, MemoStructure<_memoState, _index>> {
        const newSelf= new MemoMonad<_memoState, _index, MemoStructure<_memoState, _index>>(memo);
        
        if(!newSelf.rootState){
            newSelf.rootState = memo.state
        }
        return newSelf
    }

    compute<R, InputInterf, M>(
        { func, input }: { func: ({ input }: { input: InputInterf, rootState: _memoState|undefined, memo: S }) => R, input: InputInterf  }
    ): MemoMonad<_memoState, _index, MemoStructure<_memoState, _index>> {
        const result = func({ input, rootState: this.rootState, memo: this.memo })//this.memo.memoAction(this.memo.state, this.memo.index)
        return this
    }
    
}


------------ Class version ------------
class MemoMonad<T> {
    private memo: Record<string, T>;

    constructor(memo: Record<string, T> = {}) {
        this.memo = memo;
    }

    static of<T>(memo: Record<string, T> = {}): MemoMonad<T> {
        return new MemoMonad<T>(memo);
    }

    compute<R>(func: (...args: any[]) => R, ...args: any[]): MemoMonad<T> {
        const key = JSON.stringify(args);
        if (key in this.memo) {
            return MemoMonad.of(this.memo);
        } else {
            const result = func(...args, this.memo);
            this.memo[key] = result as unknown as T;
            return MemoMonad.of(this.memo);
        }
    }

    getValue(): T | undefined {
        const keys = Object.keys(this.memo);
        return this.memo[keys[keys.length - 1]];
    }
}

// Example usage with Fibonacci:
function fibFn(n: number, memo: Record<string, number>): number {
    if (n.toString() in memo) return memo[n.toString()];
    if (n <= 1) return n;
    memo[n.toString()] = fibFn(n - 1, memo) + fibFn(n - 2, memo);
    return memo[n.toString()];
}

function fib(n: number): number | undefined {
    return MemoMonad.of<number>().compute(fibFn, n).getValue();
}

------------ Function version ------------

type MemoMonad<T> = {
    compute: <R>(func: (...args: any[]) => R, ...args: any[]) => MemoMonad<T>;
    getValue: () => T | undefined;
};

function createMemoMonad<T>(memo: Record<string, T> = {}): MemoMonad<T> {
    return {
        compute: function<R>(func: (...args: any[]) => R, ...args: any[]): MemoMonad<T> {
            const key = JSON.stringify(args);
            if (!(key in memo)) {
                memo[key] = func(...args, memo) as unknown as T;
            }
            return createMemoMonad(memo);
        },
        getValue: function(): T | undefined {
            const keys = Object.keys(memo);
            return memo[keys[keys.length - 1]];
        }
    };
}


function fibFn(n: number, memo: Record<string, number>): number {
    if (n.toString() in memo) return memo[n.toString()];
    if (n <= 1) return n;
    memo[n.toString()] = fibFn(n - 1, memo) + fibFn(n - 2, memo);
    return memo[n.toString()];
}

function fib(n: number): number | undefined {
    return createMemoMonad<number>().compute(fibFn, n).getValue();
}

//console.log(memoizedFib(10))

------------ Weakmap version ------------

class MemoMonad<T> {
    private memo: WeakMap<object, T>;

    constructor(memo: WeakMap<object, T> = new WeakMap()) {
        this.memo = memo;
    }

    static of<T>(memo: WeakMap<object, T> = new WeakMap()): MemoMonad<T> {
        return new MemoMonad<T>(memo);
    }

    compute<R,P>(func: (...args: P[]) => R, argsKey: object, ...args: P[]): MemoMonad<T> {
        if (this.memo.has(argsKey)) {
            return MemoMonad.of(this.memo);
        } else {
            const result = func(...args);
            this.memo.set(argsKey, result as unknown as T);
            return MemoMonad.of(this.memo);
        }
    }

    getValue(argsKey: object): T | undefined {
        return this.memo.get(argsKey);
    }
}

// Example usage (requires adaptation to use objects as keys):
function fibFn(n: number): number {
    if (n <= 1) return n;
    return fibFn(n - 1) + fibFn(n - 2);
}

function fib(n: number): number | undefined {
    const argsKey = { n }; // Creating an object to be used as a key
    return MemoMonad.of<number>().compute(fibFn, argsKey, n).getValue(argsKey);
}



------------ Map version (most generic but slow)------------
class MemoMonad<T> {
    private memo: Map<string, T>;

    constructor(memo: Map<string, T> = new Map()) {
        this.memo = memo;
    }

    static of<T>(memo: Map<string, T> = new Map()): MemoMonad<T> {
        return new MemoMonad<T>(memo);
    }

    compute<R, InputInterf>({func, input}: 
    {func: ({ input, memo }: { memo?: Map<string, T>, input: InputInterf }) => R, 
        input: InputInterf}
    ): MemoMonad<T> {
        if (this.memo.has(JSON.stringify({input}))) {
            return MemoMonad.of(this.memo);
        } else {
            const result = func({ input: input, memo: this.memo  });
            this.memo.set(JSON.stringify({input}), result as unknown as T);
            return MemoMonad.of(this.memo);
        }
    }

    getMemoByInput({input}){
        return this.memo.get(JSON.stringify({input}))
    }

}

// Example usage (requires adaptation to use objects as keys):
function fibFn({input, memo = undefined}: {input: number, memo?: Map<string, any> }): number {
    if (input <= 1) return input;
    return fibFn({input: input - 1}) + fibFn({input: input - 2});
}

function fib(n: number): number | undefined {
    const memo = MemoMonad.of<number>().compute({func: fibFn, input: n});
    return  memo.getMemoByInput({input: n})
    
}


------------ Map version (with Longest Common Subsequence problem)------------
class MemoMonad<T> {
    public memo: Map<string, T>;

    constructor(memo: Map<string, T> = new Map()) {
        this.memo = memo;
    }

    static of<T>(memo: Map<string, T> = new Map()): MemoMonad<T> {
        return new MemoMonad<T>(memo);
    }

    compute<R, InputInterf>({func, input}: 
    {func: ({ input, memo }: { memo?: Map<string, T>, input: InputInterf }) => R, 
        input: InputInterf}
    ): MemoMonad<T> {
        if (this.memo.has(JSON.stringify({input}))) {
            return MemoMonad.of(this.memo);
        } else {
            const result = func({ input: input, memo: this.memo  });
            this.memo.set(JSON.stringify({input}), result as unknown as T);
            return MemoMonad.of(this.memo);
        }
    }

}

const longestCommonSubsequenceFn = ({input, memo = new Map()}:{input: {text1: string[], text2: string[]}, memo?: Map<string, number[]>}): number=>{
    
    const {text1, text2 } = input
    const _memo = memo.get('context')!
    for (let i = 1; i <= text1.length; ++i) {
        let prev = 0;
        for (let j = 1; j <= text2.length; ++j) {
            const temp = _memo[j];
            
            if (text1[i - 1] === text2[j - 1]) {
                _memo[j] = prev + 1;
            } else {
                _memo[j] = Math.max(_memo[j], _memo[j - 1]);
            }
            prev = temp; // Update prev for the next iteration
        }
    }

    // The last element of dp contains the length of the longest common subsequence
    return _memo[text2.length];
}

function longestCommonSubsequence(text1: string[], text2: string[]){
    const init = new Array(text2.length + 1).fill(0)
    const initMap = new Map()
    initMap.set('context', init)
    const resultMemo = MemoMonad.of(initMap).compute({input:{text1, text2},func: longestCommonSubsequenceFn } )
    return resultMemo.memo.get(JSON.stringify({input: {text1, text2}}))
}