我目前正在上一门函数式编程课程，我对高阶函数和作为一等公民的函数的概念感到非常有趣。然而，我还想不出许多实际有用的、概念上令人惊叹的，或者只是简单有趣的高阶函数。（除了典型且相当乏味map的 ,filter等功能）。
你知道这些有趣功能的例子吗？
也许返回函数的函数，返回函数列表的函数（？）等。
我很欣赏 Haskell 中的示例，这是我目前正在学习的语言 :)
问问题
6094 次
14 回答
45
好吧，你注意到 Haskell 没有循环语法吗？否while或do或for。因为这些都只是高阶函数：
map :: (a -> b) -> [a] -> [b]
foldr :: (a -> b -> b) -> b -> [a] -> b
filter :: (a -> Bool) -> [a] -> [a]
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
iterate :: (a -> a) -> a -> [a]
高阶函数取代了语言中对控制结构的内置语法的需求，这意味着几乎每个 Haskell 程序都使用这些函数——使它们非常有用！
它们是迈向良好抽象的第一步，因为我们现在可以将自定义行为插入通用骨架函数中。
特别是，monad之所以成为可能，是因为我们可以链接在一起并操纵函数来创建程序。
事实是，一阶的生活很无聊。编程只有在你拥有高阶之后才会变得有趣。
于 2011-04-26T15:44:39.340 回答
15
当我了解到函数可以成为数据结构的一部分时，我才真正开始感受到力量。这是一个“消费者单子”（technobabble：free monad over (i ->)）。
data Coro i a
= Return a
| Consume (i -> Coro i a)
因此 aCoro可以立即产生一个值，或者根据某些输入成为另一个 Coro。例如，这是一个Coro Int Int：
Consume $ \x -> Consume $ \y -> Consume $ \z -> Return (x+y+z)
这会消耗三个整数输入并返回它们的总和。您还可以根据输入使其表现不同：
sumStream :: Coro Int Int
sumStream = Consume (go 0)
where
go accum 0 = Return accum
go accum n = Consume (\x -> go (accum+x) (n-1))
这会消耗一个 Int，然后在产生它们的总和之前消耗更多的 Int。这可以被认为是一个带有任意多个参数的函数，没有任何语言魔法，只是高阶函数。
数据结构中的函数是一个非常强大的工具，在我开始使用 Haskell 之前，它并不是我词汇的一部分。
于 2011-04-26T17:41:27.313 回答
11
查看论文“Even Higher-Order Functions for Parsing 或为什么有人想要使用六阶函数？” 克里斯冈崎. 它是使用 ML 编写的，但这些想法同样适用于 Haskell。
于 2011-04-26T17:28:37.227 回答
9
Joel Spolsky 写了一篇著名的文章，展示了Map-Reduce如何使用 Javascript 的高阶函数工作。任何提出这个问题的人都必须阅读。
于 2011-04-27T01:45:32.270 回答
7
currying也需要高阶函数，Haskell 在任何地方都使用它。本质上，一个接受两个参数的函数等价于一个接受一个参数的函数并返回另一个接受一个参数的函数。当你在 Haskell 中看到这样的类型签名时：
f :: A -> B -> C
...(->)可以读作右关联，表明这实际上是一个返回类型函数的高阶函数B -> C：
f :: A -> (B -> C)
两个参数的非柯里化函数将具有如下类型：
f' :: (A, B) -> C
因此，任何时候你在 Haskell 中使用部分应用程序，你都在使用高阶函数。
于 2011-04-26T15:51:43.420 回答
6
Martín Escardó 提供了一个有趣的高阶函数示例：
equal :: ((Integer -> Bool) -> Int) -> ((Integer -> Bool) -> Int) -> Bool
给定两个 functionals f, g :: (Integer -> Bool) -> Int，然后equal f g决定fandg是否（扩展地）相等，即使fandg没有有限域。事实上，codomain, Int, 可以被任何具有可判定相等性的类型替换。
Escardó 给出的代码是用 Haskell 编写的，但同样的算法应该适用于任何函数式语言。
您可以使用 Escardó 描述的相同技术来计算任意精度的任何连续函数的定积分。
于 2011-04-28T11:13:28.387 回答
4
I'm a particular fan of higher-order memoization:
memo :: HasTrie t => (t -> a) -> (t -> a)
(Given any function, return a memoized version of that function. Limited by the fact that the arguments of the function must be able to be encoded into a trie.)
This is from http://hackage.haskell.org/package/MemoTrie
于 2011-04-27T17:14:49.267 回答
4
您可以做的一件有趣且有点疯狂的事情是使用函数模拟面向对象的系统并将数据存储在函数的范围内（即在闭包中）。在对象生成器函数是返回对象（另一个函数）的函数的意义上，它是高阶的。
我的 Haskell 相当生疏，所以我不能轻易地给你一个 Haskell 的例子，但这里有一个简化的 Clojure 例子，希望能传达这个概念：
(defn make-object [initial-value]
(let [data (atom {:value initial-value})]
(fn [op & args]
(case op
:set (swap! data assoc :value (first args))
:get (:value @data)))))
用法：
(def a (make-object 10))
(a :get)
=> 10
(a :set 40)
(a :get)
=> 40
同样的原则也适用于 Haskell（除了你可能需要更改 set 操作以返回一个新函数，因为 Haskell 是纯函数式的）
于 2011-04-26T16:05:57.463 回答
3
这是一个小的解释代码片段：
rays :: ChessPieceType -> [[(Int, Int)]]
rays Bishop = do
dx <- [1, -1]
dy <- [1, -1]
return $ iterate (addPos (dx, dy)) (dx, dy)
... -- Other piece types
-- takeUntilIncluding is an inclusive version of takeUntil
takeUntilIncluding :: (a -> Bool) -> [a] -> [a]
possibleMoves board piece = do
relRay <- rays (pieceType piece)
let ray = map (addPos src) relRay
takeUntilIncluding (not . isNothing . pieceAt board)
(takeWhile notBlocked ray)
where
notBlocked pos =
inBoard pos &&
all isOtherSide (pieceAt board pos)
isOtherSide = (/= pieceSide piece) . pieceSide
这使用了几个“高阶”函数：
iterate :: (a -> a) -> a -> [a]
takeUntilIncluding -- not a standard function
takeWhile :: (a -> Bool) -> [a] -> [a]
all :: (a -> Bool) -> [a] -> Bool
map :: (a -> b) -> [a] -> [b]
(.) :: (b -> c) -> (a -> b) -> a -> c
(>>=) :: Monad m => m a -> (a -> m b) -> m b
(.)是.运算符，并且(>>=)是do-notation“换行符”。
在 Haskell 中编程时，您只需使用它们。当你意识到它们是多么有用时，你没有高阶函数的地方。
于 2011-04-26T18:46:16.820 回答
3
这里有几个例子：http ://www.haskell.org/haskellwiki/Higher_order_function
我还推荐这本书：http ://www.cs.nott.ac.uk/~gmh/book.html ，它很好地介绍了所有 Haskell 并涵盖了高阶函数。
高阶函数通常使用累加器，因此可以在从较大列表中形成符合给定规则的元素列表时使用。
于 2011-04-26T15:44:28.053 回答
3
这是一个我还没有看到其他人提到过的模式，当我第一次了解它时，我真的很惊讶。考虑一个统计数据包，其中您有一个样本列表作为输入，并且您想要计算一堆不同的统计数据（还有很多其他方法可以激发这一点）。底线是您有一个要运行的函数列表。你如何运行它们？
statFuncs :: [ [Double] -> Double ]
statFuncs = [minimum, maximum, mean, median, mode, stddev]
runWith funcs samples = map ($samples) funcs
这里有各种各样的高阶善良，其中一些已经在其他答案中提到过。但我想指出'$'功能。当我第一次看到“$”的这种用法时，我被震撼了。在此之前，除了作为括号的方便替代品之外，我并没有认为它非常有用......但这几乎是神奇的......
于 2011-04-27T15:06:42.920 回答
2
如果不是特别实用的话，一件很有趣的事情就是Church Numerals。这是一种仅使用函数来表示整数的方法。疯了，我知道。<samelessPlug>这是我用JavaScript 编写的一个实现。它可能比 Lisp/Haskell 实现更容易理解。（但可能不是，说实话。JavaScript 并不是真的适合这种事情。）</samelessPlug>
于 2011-04-27T03:09:08.307 回答
2
有人提到 Javascript 支持某些高阶函数，包括Joel Spolsky 的一篇文章。Mark Jason Dominus 写了一整本书，叫做Higher–Order Perl；本书的源代码可以多种精美格式免费下载，包括PDF。
至少从 Perl 3 开始，Perl 支持的功能更像 Lisp 而不是 C，但直到 Perl 5 才完全支持闭包以及随之而来的所有功能。最初的 Perl 6 实现中没有一个是用 Haskell 编写的，这对该语言的设计进展产生了很大影响。
Perl 中的函数式编程方法的示例出现在日常编程中，尤其是使用mapand grep：
@ARGV = map { /\.gz$/ ? "gzip -dc < $_ |" : $_ } @ARGV;
@unempty = grep { defined && length } @many;
由于sort也承认闭包，这种map/sort/map模式非常常见：
@txtfiles = map { $_->[1] }
sort {
$b->[0] <=> $a->[0]
||
lc $a->[1] cmp lc $b->[1]
||
$b->[1] cmp $a->[1]
}
map { -s => $_ }
grep { -f && -T }
glob("/etc/*");
或者
@sorted_lines = map { $_->[0] }
sort {
$a->[4] <=> $b->[4]
||
$a->[-1] cmp $b->[-1]
||
$a->[3] <=> $b->[3]
||
...
}
map { [$_ => reverse split /:/] } @lines;
该reduce函数使列表黑客变得容易而无需循环：
$sum = reduce { $a + $b } @numbers;
$max = reduce { $a > $b ? $a : $b } $MININT, @numbers;
还有很多，但这只是一种味道。闭包可以很容易地创建函数生成器，编写自己的高阶函数，而不仅仅是使用内置函数。事实上，比较常见的异常模型之一，
try {
something();
} catch {
oh_drat();
};
不是内置的。然而，它几乎被简单地定义try为一个带有两个参数的函数：第一个参数中的闭包和第二个参数中的闭包函数。
Perl 5 没有内置柯里化，尽管有一个模块。然而，Perl 6 内置了柯里化和一流的延续，还有更多。
于 2011-04-27T23:56:01.980 回答