Haskell:带元组的映射函数

Question

我必须编写一个执行以下操作的 Haskell 程序:

Main> dotProduct [(1,3),(2,5),(3,3)]  2
[(2,3),(4,5),(6,3)]

我必须在有和没有的情况下都这样做 map功能。
我已经做到了 map ，但我不知道如何使用 map .

我的 dotProduct没有 map功能:

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct [] _ = []
dotProduct [(x,y)] z = [(x*z,y)]
dotProduct ((x,y):xys) z = (x*z,y):dotProduct (xys) z

所以我真的需要帮助 map版本。

Answer 1

而不是从尝试适应开始 map以某种方式，考虑如何简化和概括您当前的功能。从此开始:

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct [] _ = []
dotProduct [(x,y)] z = [(x*z,y)]
dotProduct ((x,y):xys) z = (x*z,y):dotProduct (xys) z

首先，我们将使用 (:) 重写第二种情况构造函数:

dotProduct ((x,y):[]) z = (x*z,y):[]

扩展 []在使用第一种情况的结果中:

dotProduct ((x,y):[]) z = (x*z,y):dotProduct [] z

将此与第三种情况进行比较，我们可以看到它们是相同的，只是专门用于 when xys是 [] .因此，我们可以简单地完全消除第二种情况:

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct [] _ = []
dotProduct ((x,y):xys) z = (x*z,y):dotProduct (xys) z

接下来，泛化函数。首先，我们重命名它，让 dotProduct称它为:

generalized :: [(Float, Integer)] -> Float -> [(Float, Integer)]
generalized [] _ = []
generalized ((x,y):xys) z = (x*z,y):generalized (xys) z

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized xs z

首先，我们通过操作对其进行参数化，专门用于乘法 dotProduct :

generalized :: (Float -> Float -> Float) -> [(Float, Integer)] -> Float -> [(Float, Integer)]
generalized _ [] _ = []
generalized f ((x,y):xys) z = (f x z,y):generalized f (xys) z

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized (*) xs z

接下来，我们可以观察到两件事: generalized不再直接依赖算术，所以它可以在任何类型上工作；唯一一次 z用作 f 的第二个参数，所以我们可以将它们组合成一个函数参数:

generalized :: (a -> b) -> [(a, c)] -> [(b, c)]
generalized _ [] = []
generalized f ((x,y):xys) = (f x, y):generalized f (xys)

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized (* z) xs

现在，我们注意到 f仅用于元组的第一个元素。这听起来很有用，所以我们将其提取为一个单独的函数:

generalized :: (a -> b) -> [(a, c)] -> [(b, c)]
generalized _ [] = []
generalized f (xy:xys) = onFirst f xy:generalized f (xys)

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

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized (* z) xs

现在我们再次观察到，在 generalized , f仅用于 onFirst ，所以我们再次将它们组合成一个函数参数:

generalized :: ((a, c) -> (b, c)) -> [(a, c)] -> [(b, c)]
generalized _ [] = []
generalized f (xy:xys) = f xy:generalized f (xys)

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized (onFirst (* z)) xs

再一次，我们观察到 generalized不再依赖于包含元组的列表，所以我们让它适用于任何类型:

generalized :: (a -> b) -> [a] -> [b]
generalized _ [] = []
generalized f (x:xs) = f x : generalized f xs

现在，比较 generalized 的代码对此:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

事实证明， onFirst 是一个稍微通用的版本。也存在，所以我们将替换它和 generalized与他们的标准库等价物:

import Control.Arrow (first)

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = map (first (* z)) xs