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 工作，所以我可以说:

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;
}

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