4

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

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

无论有没有map功能,我都必须这样做。我已经在没有的情况下做到了map,但我不知道用map.

我的dotProductmap功能:

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版本的帮助。

4

3 回答 3

13

与其从试图以某种方式适应开始,不如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

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

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

现在我们再次观察到 in仅与 一起使用generalized,因此我们再次将它们组合成一个函数参数:fonFirst

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
于 2011-08-23T18:55:04.640 回答
4
dotProduct xs z = map (\(x,y) -> (x*z,y)) xs

(\(x,y) -> (x*z,y))部分是一个函数,它接受一对并返回一个与旧对相似的新对,除了它的第一个组件乘以z. 该map函数接受一个函数并将其应用于列表中的每个元素。因此,如果我们将(\(x,y) -> (x*z,y))函数传递给map,它将将该函数应用于 中的每个元素xs

虽然你确定你的第一个是正确的吗?点积运算通常被定义为它采用两个向量,将相应的分量相乘,然后将它们相加。像这样:

dotProduct xs ys = sum $ zipWith (*) xs ys
于 2011-08-23T18:31:07.943 回答
2

EEVIAC 已经发布了答案,所以我将解释如何自己提出答案。您可能知道,map具有类型签名(a -> b) -> [a] -> [b]。现在,dotProduct有了类型[(Float, Integer)] -> Float -> [(Float, Integer)],你会map在其中的某个地方调用,所以它必须看起来像这样:

dotProduct theList z = map (??? z) theList

where???是类型的函数Float -> (Float, Integer) -> (Float, Integer)- 这直接来自于的类型签名map和我们传递给函数的事实z,这是我们必须做的,仅仅是因为没有其他地方可以使用它。

一般来说,具有高阶函数的事情map是你必须记住高阶函数的作用并“简单地”为它提供正确的函数。由于map将给定函数应用于列表中的所有元素,您的函数只需要使用一个元素,您可以忘记列表的所有内容 -map会处理它。

于 2011-08-23T18:35:58.850 回答