Problem 1.2: Function as an ADT (300pts)

Problem

In this problem, the evil TA has replaced your list implementation in Problem 1.1 with a different one, keeping the same abstract interface but breaking everything inside.

You should only work with the abstract interface to implement the following tasks:

在这个问题中，邪恶的助教（TA）用一个不同的实现替换了您在问题 1.1 中的列表实现，保持了相同的抽象接口，但破坏了内部的一切。

您应该只使用抽象接口来实现以下任务：

Determine whether two functions are equal using the extensionality principle.

使用外延性原理（extensionality principle）来判断两个函数是否相等。

def fn_ext(fn1, fn2):
"""Return whether fn1 and fn2 represent the same function.
Two functions are the same if and only if they have the same domain
and output the same value for each input in the domain.

>>> f = fn_remap(fn_empty(), 1, 2)
>>> g = fn_remap(fn_empty(), 2, 3)
>>> fn_ext(f, g)
False
>>> fn_ext(fn_remap(f, 2, 3), g)
False
>>> fn_ext(fn_remap(f, 2, 3), fn_remap(g, 1, 2))
True
"""
"*** YOUR CODE HERE ***"

Compute the composition of two functions.

计算两个函数的复合（composition）。

def fn_compose(fn1, fn2):
"""Return a new function that is the composition of fn1 and fn2.
The composition of two functions fn1 and fn2 is a function fn such that
fn(x) = fn1(fn2(x)) for every x in the domain of fn2.

>>> f = fn_remap(fn_empty(), 2, 3)
>>> g = fn_remap(fn_empty(), 1, 2)
>>> h = fn_compose(f, g)
>>> fn_call(h, 1)
3
>>> fn_call(h, 2) is None
True
"""
"*** YOUR CODE HERE ***"

Compute the inverse of a function.

计算一个函数的逆函数（inverse of a function）。

def fn_inverse(fn):
"""Return a new function that is the inverse of fn.
The inverse of a function fn is a function fn_inv such that
fn_inv(y) = x if and only if fn(x) = y.
If fn is not invertible, return None.

>>> f = fn_remap(fn_remap(fn_empty(), 1, 2), 2, 3)
>>> fn_call(fn_inverse(f), 3)
2
>>> g = fn_remap(fn_remap(fn_empty(), 1, 2), 2, 2)
>>> fn_inverse(g) is None
True
"""
"*** YOUR CODE HERE ***"

Hints

Solutions

Generated by AI.

压行 by sprite

由于不能打破抽象，只好写成这样了...

让 fn 变成列表：

fn2lst = lambda fn: [[x, fn_call(fn, x)] for x in fn_domain(fn)]

让列表变成 fn （使用组合子）：

lst2fn = lambda x: (g := lambda f, i, a: a if not i else f(f, i[1:], fn_remap(a, i[0][0], i[0][1])))(g, x, fn_empty())

所以有

def fn_ext(fn1, fn2):
    return sorted([[x, fn_call(fn1, x)] for x in fn_domain(fn1)]) == sorted([[x, fn_call(fn2, x)] for x in fn_domain(fn2)])


def fn_compose(fn1, fn2):
    return (lambda x: (g := lambda f, i, a: a if not i else f(f, i[1:], fn_remap(a, i[0][0], i[0][1])))(g, x, fn_empty()))([[j[0], i[1]] for i in [[x, fn_call(fn1, x)] for x in fn_domain(fn1)] for j in [[x, fn_call(fn2, x)] for x in fn_domain(fn2)] if i[0] == j[1]])


def fn_inverse(fn):
    return (lambda x: (g := lambda f, i, a: a if not i else f(f, i[1:], fn_remap(a, i[0][0], i[0][1])))(g, x, fn_empty()))([i[::-1] for i in [[x, fn_call(fn, x)] for x in fn_domain(fn)]]) if (len(r := [i[1] for i in [[x, fn_call(fn, x)] for x in fn_domain(fn)]]) == len(set(r))) else None