Haskell中的高阶函数到底能做什么扩展C不能？

Question

GCC具有C扩展,允许使用嵌套函数.

实际上,我不明白Haskell中的高阶函数(或其他纯函数式语言)C(函数指针和嵌套函数扩展)不能完全是什么？

Answer 1

我从未使用过这个gcc扩展名; 但我会根据你对你给出的链接的解释来解释.

据我理解文档,关键的区别在于那些嵌套函数不允许你构建函数程序员在"闭包"下理解的东西 - 那些嵌套函数不能在它们的定义上下文之外使用,因为外部函数退出后,它们使用的堆栈变量会丢失.

在Haskell中,当我执行以下操作时:

const x = \y -> x 
foo = const 2      -- remember or "close over" 2
bar = foo 1        -- now, bar == 2

你看到在申请const时2,参数2被我们调用的闭包"保存"了foo.之后,在bar,2可以被召回并返回 - 因为它仍然被记住foo.但是,在C:

typedef int (*int_to_int_fn)(int);
int_to_int_fn constant(int x)
{
  int constant_impl(int y) { return x; }
  return constant_impl;
}

int main()
{
   int_to_int_fn foo = constant(2);
   int bar = foo(1);
}

这可能甚至没有编译,但如果它会,它将违背我们对C函数的基本期望:xin foo,由参数构成constant,需要保留在某个地方(可能不在堆栈上!),直到一段时间后才foo被召唤.这不是原始工作的原因 - 在这个意义上,C是原始的(我们可能需要在堆上分配一些东西,复制东西,稍后清理它,担心引用/值等).

通过查看C++ 11 lambda语法可能可以实现一些启示.在那里,constant_impl可以写在这个地方:

auto constant_impl = [x](int y){ return x; }

[x]那里的部分恰好是我们告诉编译器的地方"请,请记住x给我!".

Answer 2

实际使用高阶函数的关键是你需要闭包:除了参数之外,普通的旧函数只能使用全局/静态数据.这意味着像

GHCi>过滤器(> 4)[7,4,3,6,87,5,4]
[7,6,87,5]

除非你定义全局,否则无法真正起作用

bool largerThan4(int i) {return (i>4);}

这显然不会扩展.没有办法从程序中的其他位置"注入"数字4.功能语言将此类信息打包在闭包中.

现在,这个GNU C扩展为您提供了有限意义上的闭包,我认为这与C++ 11为lambdas通过引用捕获定义的意义相同:本地函数可以引用其包含范围内的变量.对于比方说,这样做效果相当好

typedef std::vector<int> IntArray;

IntArray filter (const IntArray& a, std::function<bool(int)> pred) {
  IntArray result;
  for(auto& i: a) if (pred(i)) result.push_back(i);
  return result;
}

int main() {
  std::vector<int> v{{7,4,3,6,87,5,4}};
  int minNumber = 4;
  for(auto i: filter(v, [&](int i){return i>minNumber;}))
    cout << i << endl;
  return 0;
}

(在没有范围,循环等.那会是更麻烦大家知道,C).在这里,当地的匿名函数只使用,而minNumber剩下的就是的范围main,因此,虽然filter在调用该谓词保持它永远可以指向点.

但这是一个非常简单的场景.在函数式语言中,您通常会更普遍地使用高阶函数,包括诸如

• 从另一个函数返回一个函数.这已经成为词法闭包的问题 - 你不能在它离开范围后引用局部变量!所以你需要复制/移动该变量作为额外的回报.
• 在封闭中使用变量,这些封闭来自其他封闭本身,您无法直接控制它们.闭包不能无限期地停留,它们需要在某个时候被删除 - 但是编译器怎么知道什么时候它是安全的？功能语言通常是垃圾收集的,这解决了这个问题.
• 以自身为参数的函数递归.这意味着可以有效地存在变量引用的循环("打结").这通常意味着程序将挂起,除非您有懒惰的评估.