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

Сравнивая это с третьим случаем, мы видим, что они идентичны, за исключением того, что это специализировано, когда 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

Answer 2

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

Answer 3

EEVIAC уже опубликовал ответ, поэтому я просто объясню, как придумать его самостоятельно.Как вы, наверное, знаете, map имеет сигнатуру типа (a -> b) -> [a] -> [b].Теперь dotProduct имеет тип [(Float, Integer)] -> Float -> [(Float, Integer)], и вы где-то там будете вызывать map, поэтому он должен выглядеть примерно так:

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

, где ??? - это функция типаFloat -> (Float, Integer) -> (Float, Integer) - это немедленно следует из сигнатуры типа map и того факта, что мы передаем z функции, которую мы должны сделать, просто потому, что нет другого места, где ее можно использовать.

В общем, функции map и функции более высокого порядка заключаются в том, что вы должны помнить, что делает функция более высокого порядка, и «просто» снабжать ее правильной функцией.Поскольку map применяет данную функцию ко всем элементам в списке, ваша функция должна работать только с одним элементом, и вы можете забыть все о списке - map позаботится об этом.