c - Haskell Foldr C 实现

Question

我正在尝试在 C 中实现 Haskell 的 foldr 函数的一个版本，但由于我想使 + 或 * 字符(foldr 中的 char y)用作加法或乘法，所以遇到了障碍使其通用。我正在考虑尝试一个宏，但不确定什么会起作用。

这里是代码:

int
foldr(int *v, int (*f)(int*), int x, char y)
{
    int temp;
    if(*v == (int) NULL) //v is null terminated int array
        return x;
    else{
        temp = *v;
        return temp y ((*f)(++v));
    }
}

主要问题是让 char y 工作所以我可以说:

int
sum(int *v)
{
    return foldr(v, (sum), 0, '+');
}

它会正常工作。谢谢

Answer 1

我将展示一种基于递归的方法。作为练习，您可以根据需要将其转变为迭代解决方案。

(警告:未经测试)

haskell :

foldr :: (Int->Int->Int) -> Int -> [Int] -> Int
foldr f x []     = x                    -- base case
foldr f x (v:vs) = f v (foldr f x vs)   -- recursion

C:

int foldr(int (*f)(int,int),
          int x,
          int *v, size_t length) {
    // base case
    if (length == 0) return x;
    // recursion
    return f(*v, foldr(f, x, v+1, length-1));
}

测试:

int add(int a, int b) {
   return a+b;
}
int main() {
   int a[] = {1,2,3} ;
   int res = foldr(add, 0, a, sizeof a/sizeof *a);
   printf("%d\n", res);
   return 0;
}

如果您在上面传递了一个适当的函数指针(如add)，则不需要传递字符运算符'+'。

---

请注意，函数式编程语言也允许构建闭包，如:

let y = 5
in foldr (\x c -> x*y+c) 0 [1..3]

请注意函数 \x c -> x*y+c 还取决于 y 的值。 C 不允许执行工艺闭包，但如果允许向 C 函数添加 void * 参数，则可以模拟捕获的 y。

int foldr(int (*f)(void *, int, int),
          void *data,
          int x,
          int *v, size_t length) {
    // base case
    if (length == 0) return x;
    // recursion
    return f(data, *v, foldr(f, data, x, v+1, length-1));
}

测试:

int g(void *data, int x, int c) {
   int y = *(int *)data;
   return x*y+c;
}
int main() {
   int a[] = {1,2,3} ;
   int y = 5;
   int res = foldr(g, &y, 0, a, sizeof a/sizeof *a);
   printf("%d\n", res);
   return 0;
}

通过这种方式，您可以使用不同的 y 值重用 g。如果您需要捕获更多变量，请将指针传递给包含所有此类变量的合适的 struct。