跳转到内容

Haskell/解决方案/高阶函数

Add links
来自维基教科书，开放的书籍，开放的世界

← 返回高阶函数

选择比较方式

[编辑 | 编辑源代码]
练习
编写insensitive，使得quickSort insensitive dictionary给出["a", "for", "have", "I", "Linux", "thing"] 
import Data.Char (toUpper)
insensitive string1 string2 = compare (map toUpper string1) (map toUpper string2)

与其直接比较两个字符串，我们比较两个字符串的全大写版本。然后，根据大写版本的顺序确定原始两个字符串的顺序。

高阶函数和类型

[编辑 | 编辑源代码]
练习

（有挑战性） 下面的练习结合了你对高阶函数、递归和 I/O 的学习。我们将重新创建在命令式语言中被称为for 循环的东西。实现一个函数

for :: a -> (a -> Bool) -> (a -> a) -> (a -> IO ()) -> IO ()
for i p f job = -- ???

这个函数使用方式的一个例子可能是

for 1 (<10) (+1) print

它在屏幕上打印数字 1 到 9。

for 的预期行为是：从初始值i开始，for 首先检查p i，如果它评估为真，那么它执行job i，否则它停止并且不执行任何操作。如果执行了job i，那么它使用f 修改这个值并检查修改后的值f i 是否满足某个条件p。如果不满足，它停止；否则，for 循环继续，使用修改后的f i 代替i。

  1. 在 Haskell 中实现 for 循环。
  2. 上面的段落给出了 for 循环的命令式描述。用更函数式的术语描述你的实现。

你可以尝试一些更具挑战性的练习

  1. 考虑一个像“打印从 1 到 10 的数字列表”这样的任务。鉴于print 是一个函数，并且我们想要将它应用于一个数字列表，使用map 看起来是自然的事情。但这真的有效吗？
  2. 实现一个函数sequenceIO :: [IO a] -> IO [a]。给定一个操作列表，这个函数按顺序运行每个操作并返回它们的结果作为列表。
  3. 实现一个函数mapIO :: (a -> IO b) -> [a] -> IO [b]，它给定一个类型为a -> IO b 的函数和一个类型为[a] 的列表，对列表中的每个项目运行该操作，并返回结果。
此练习的灵感来自 osfameron 的博客文章。不要偷看！

第一部分

1. Haskell 中的 for 循环

for :: a -> (a -> Bool) -> (a -> a) -> (a -> IO ()) -> IO ()
for i p f job =
    if p i
    then do
      job i
      for (f i) p f job
    else return ()

*Main> for 0 (<3) (+1) (print)
0
1
2

2. for i p f job 是一个递归构建的IO 操作。在每个递归步骤的开始，检查布尔值p i。基本情况是在p i 为False 时到达，结果是不执行任何操作的操作return ()。在递归情况下，结果是一个操作，它由job i 接着for 组成，for 使用f i 而不是i 调用，并且具有与之前相同的函数参数。

第二部分

1. 天真的解决方案map print [1..10] 将不起作用。map print [1..10] 的类型是[IO String]，一个操作列表。就其本身而言，这没有什么错，因为操作是 Haskell 值，就像其他值一样。但是，操作列表不是操作，因此它不能（例如）被放到IO do 块中并通过main 执行。

2. 

sequenceIO :: [IO a] -> IO [a]
sequenceIO [] = return []
sequenceIO (a:as) = do
    v <- a              -- runs the first action; binds the result to v.
    vs <- sequenceIO as -- recursive call; binds the other results to vs.
    return (v : vs)     -- returns all results.

或者使用foldr

sequenceIO :: [IO a] -> IO [a]
sequenceIO = foldr (\a seqio -> do v  <- a
                                   vs <- seqio
                                   return (v:vs))
                   (return [])

3. 

mapIO :: (a -> IO b) -> [a] -> IO [b]
mapIO f [] = return []
mapIO f (x:xs) = do
    y <- f x
    ys <- mapIO f xs
    return (y : ys)

或者，可以根据sequenceIO 实现mapIO

mapIO :: (a -> IO b) -> [a] -> IO [b]
mapIO f xs = sequenceIO (map f xs)

或者无点式

mapIO :: (a -> IO b) -> [a] -> IO [b]
mapIO f = sequenceIO . map f

函数操作

[编辑 | 编辑源代码]
练习
  1. 编写curry、uncurry 和const 的实现。
  2. 在不测试它们的情况下描述以下函数的作用
    • uncurry const
    • curry fst
    • curry swap，其中swap :: (a, b) -> (b, a) 交换一对元素。（swap 可以在Data.Tuple 中找到。）
  3. （非常难） 使用foldr 实现foldl。提示：首先回顾列表 III 中关于foldr 和foldl 的部分。有两个解决方案；一个是相对无聊的，另一个是真正有趣的。对于有趣的一个，仔细考虑一下如何组合一个列表中的所有函数。

1. 

myUncurry :: (a -> b -> c) -> (a, b) -> c
myUncurry f (x, y) = f x y

myCurry :: ((a, b) -> c) -> a -> b -> c
myCurry f x y = f (x, y)

myConst :: a -> b -> a
myConst x _ = x

一种风格上的替代方案是使用 lambda 来强调正在返回一个函数。如果你在尝试实现一个返回函数的函数时感到困惑，那么这样做可能会让你更容易看到实现应该是什么样子。

myUncurry :: (a -> b -> c) -> ((a, b) -> c)
myUncurry f = \(x, y) -> f x y

myCurry :: ((a, b) -> c) -> (a -> b -> c)
myCurry f = \x y -> f (x, y)

myConst :: a -> (b -> a)
myConst x = \_ -> x


2.

  • uncurry const 按顺序将一对的元素传递给const。由于const 总是返回它的第一个参数，因此uncurry const 返回一对的第一个元素；换句话说，它是fst 的伪装。
  • curry fst 将fst 转换为一个有两个参数的函数，它返回第一个参数；因此，curry fst 等效于const。
    或者，curry 和uncurry 是逆函数（也就是说，它们互相撤销；curry . uncurry 等同于id），因此如果uncurry const 是fst，那么很明显curry fst 是const。
    第三种方法是注意到，给定curry 和fst 的类型，curry fst 的类型是一个a -> b -> a 函数。唯一具有此类型的函数是const；因此，curry fst 必须等效于它。
  • swap 给定一对，产生一对，其中元素被交换。因此，curry swap 接受两个参数，并将它们按交换的顺序配对；它等效于flip (,)。

所有上述答案都可以通过展开和替换定义来严格检查。以下是第一种情况的执行方式；我们建议你用其他两种方式尝试一下。

-- For the sake of mind-numbing explicitness, we will expand all
-- definitions as functions of a single argument, using nested lambdas.
uncurry const
(\f -> \(x, y) -> f x y) const -- Definition of uncurry.
\(x, y) -> const x y           -- Applying to const.
\(x, y) -> (\x -> \_ -> x) x y -- Definition of const.
\(x, y) -> (\_ -> x) y         -- Applying to x.
\(x, y) -> x                   -- Applying to y.


3. 以下是细致入微的逐步解释。如果你在这里是因为你放弃了练习，你仍然可以跳到最后，尝试理解实现的作用，然后再返回并查看它是如何构建的。

要完成这个技巧，需要两个关键的见解。第一个是记住左折叠

foldl f acc xs
-- To make things easier to see, we will make xs = [a, b, c]
-- wherever we need a concrete example. 
foldl f acc [a, b, c]

可以扩展为

f (f (f acc a) b) c

然后意识到如果我们翻转f 并交换它的所有参数

flip f c (flip f b (flip f a acc)))

我们得到一个表达式，它与右折叠一样关联到右边！

foldr g acc [x, y, z]
-- can be expanded as
g x (g y (g z acc)))
-- Now make g = flip f; x = c; y = b and z = a.

唯一的问题是我们右关联表达式中的列表元素顺序不对。修复它的明显方法是反转输入列表。这导致了第一个解决方案

boringFoldl :: (b -> a -> b) -> b -> [a] -> b
boringFoldl f acc = foldr (flip f) acc . reverse

但是，反转列表相当不优雅，并且需要与列表长度成正比的时间。在这一点上，第二个见解发挥作用。通过查看包含嵌套flip f 的表达式，并眯着眼睛看一看

flip f c (flip f b (flip f a acc)))

我们可以看到我们实际上是在获取acc，并依次应用多个函数。我们可以通过使用(.) 重写表达式来使其透明。

flip f c . flip f b . flip f a $ acc

如果我们将(.) 切换到前缀表示法

(.) (flip f c) ((.) (flip f b) (flip f a)) $ acc

很明显，$ 左边的函数可以用(.) 作为折叠来写

foldr (.) id [flip f c, flip f b, flip f a] $ acc

另一种思考这个步骤的方法是恢复对foldr 的直觉，它获取一个列表，用二元运算符替换(:)，用初始累加器替换[]。在我们的例子中，id，即不做任何事情的哑函数，用作初始累加器。接下来，我们使用map 提取重复的flip f

foldr (.) id (map (flip f) [c, b, a]) $ acc

在这里我们遇到了同样的问题：列表元素的顺序与我们希望的顺序不同。反转与函数与(.) 组合的事实一致，即函数从右到左应用。但是，这次我们可以简单地翻转(.)，而不是反转列表

foldr (flip (.)) id (map (flip f) [a, b, c]) $ acc

仅仅翻转折叠运算符不足以将foldr 转换为foldl，因为在一般情况下，运算符参数具有不同的类型，因此翻转会导致不匹配。但是，用(.) 折叠一个列表只有在列表元素是a -> a 函数时才能起作用，并且a -> a 函数可以在两个方向上组合。

通过从具体示例中抽象出来，我们得到了第二个解决方案

coolFoldl :: (b -> a -> b) -> b -> [a] -> b
coolFoldl f acc xs = foldr (flip (.)) id (map (flip f) xs) acc

如果你发现这个最终表达式很难理解，那么通过删除flip 来使其更有指向性可能会有所帮助

coolFoldl :: (b -> a -> b) -> b -> [a] -> b
coolFoldl f acc xs = foldr (\g h -> h . g) id (map step xs) acc
    where
    step x = \acc -> f acc x

或者，我们可以使其更无点式，尽管这会有点过分。

coolFoldl :: (b -> a -> b) -> b -> [a] -> b
coolFoldl f acc = ($ acc) . foldr (flip (.)) id . map (flip f)
检索自"https://wikibooks.cn/w/index.php?title=Haskell/Solutions/Higher-order_functions&oldid=4324585"
华夏公益教科书