Как вы определяете карту и фильтр, используя foldr в Haskell?

Ответ 1

Я бы хотел просто прокомментировать, но, увы, мне не хватает кармы.

Другие ответы - все хорошие, но я думаю, что самая большая путаница, по-видимому, связана с вашим использованием x и xs.

Если вы переписали его как

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x:xs)   = foldr (\y ys -> (f y):ys) [] xs

вы ясно увидите, что x даже не упоминается с правой стороны, поэтому никак не может быть в решении.

Приветствия

Ответ 2

Для вашего первого вопроса foldr уже имеет случай для пустого списка, поэтому вам не нужно и не следует указывать случай для него на вашей собственной карте.

map' f = foldr (\x xs -> f x : xs) []

То же самое верно для filter'

filter' p = foldr (\x xs -> if p x then x : xs else xs) []

В ваших лямбда-выражениях нет ничего плохого, но что-то не так с вашими определениями filter' и map'. В случае cons (x: xs) вы едите голову (x), а затем передаете хвост на foldr. Функция foldr никогда не сможет увидеть первый элемент, который вы уже съели.:)

Обратите внимание, что:

filter' p = foldr (\x xs -> if p x then x : xs else xs) []

эквивалентен (η-эквивалент):

filter' p xs = foldr (\x xs -> if p x then x : xs else xs) [] xs

Ответ 3

В ваших определениях вы выполняете сопоставление образцов для x:xs, что означает, что когда ваш аргумент [1,2,3,4], x привязан к 1 и xs привязан к остальной части списка: [2,3,4].

То, что вы не должны делать, это просто выбросить часть x:. Затем ваш foldr будет работать над полным списком.

Итак, ваши определения должны выглядеть следующим образом:

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f xs       = foldr (\x xs -> (f x):xs) [] xs

и

filter'             :: (a -> Bool) -> [a] -> [a]
filter' p []        = []
filter' p xs        = foldr (\x xs -> if p x then x:xs else xs ) [] xs

Ответ 4

Я бы определил карту с помощью foldr и состав функций следующим образом:

map :: (a -> b) -> [a] -> [b]
map f = foldr ((:).f) []

И для случая фильтра:

filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr (\x xs -> if p x then x:xs else xs) []

Обратите внимание, что нет необходимости передавать список при определении функций над списками с помощью foldr или foldl. Проблема с вашим решением заключается в том, что вы удаляете головку списка, а затем применяете карту по списку и поэтому глава списка отсутствует, когда отображается результат.

Ответ 5

Другой способ думать об этом - foldr существует, потому что часто используется следующий рекурсивный шаблон:

-- Example 1: Sum up numbers
summa :: Num a => [a] -> a
summa []     = 0
summa (x:xs) = x + suma xs

Взятие произведения чисел или даже обращение вспять списка выглядит структурно очень похожим на предыдущую рекурсивную функцию:

-- Example 2: Reverse numbers
reverso :: [a] -> [a]
reverso []      = []
reverso (x:xs)  = x `op` reverso xs
  where
    op = (\curr acc -> acc ++ [curr])

Структура в приведенных выше примерах отличается только от начального значения (0 для summa и [] для reverseo) вместе с оператором между первым значением и рекурсивным вызовом (+ для summa и (\q qs -> qs ++ [q]) для reverseo). Таким образом, функциональную структуру для приведенных выше примеров можно рассматривать как

-- Generic function structure
foo :: (a -> [a] -> [a]) -> [a] -> [a] -> [a]
foo op init_val []      = init_val
foo op init_val (x:xs)  = x `op` foo op init_val xs

Чтобы увидеть, что это "общее" foo работает, мы могли бы переписать reverseo с помощью foo и передать ему оператор, начальное значение и сам список:

-- Test: reverso using foo
foo (\curr acc -> acc ++ [curr]) [] [1,2,3,4]

Давайте дадим foo более общую подпись типа, чтобы она работала и для других проблем:

foo :: (a -> b -> b) -> b -> [a] -> b

Теперь, возвращаясь к вашему вопросу, мы могли бы написать фильтр следующим образом:

-- Example 3: filter
filtero :: (a -> Bool) -> [a] -> [a]
filtero p []     = []
filtero p (x:xs) = x `filterLogic` (filtero p xs)
  where
     filterLogic = (\curr acc -> if (p curr) then curr:acc else acc)

Это снова имеет очень похожую структуру для суммирования и реверсирования. Следовательно, мы должны иметь возможность использовать foo для его перезаписи. Скажем, мы хотим отфильтровать четные числа из списка [1,2,3,4]. Затем снова мы передаем оператор foo (в данном случае filterLogic), начальное значение и сам список. filterLogic в этом примере принимает функцию p, называемую предикатом, которую мы должны определить для вызова:

let p = even in foo (\curr acc -> if (p curr) then curr:acc else acc) [] [1,2,3,4] 

foo в Haskell называется foldr. Итак, мы переписали фильтр с помощью foldr.

let p = even in foldr (\curr acc -> if (p curr) then curr:acc else acc) [] [1,2,3,4] 

Итак, фильтр можно записать с помощью foldr, как мы видели:

-- Solution 1: filter using foldr
filtero' :: (a -> Bool) -> [a] -> [a]
filtero' p xs = foldr (\curr acc -> if (p curr) then curr:acc else acc) [] xs 

Что касается map, мы могли бы также записать его как

-- Example 4: map
mapo :: (a -> b) -> [a] -> [b]
mapo f []   = []
mapo f (x:xs) = x `op` (mapo f xs)
  where
    op = (\curr acc -> (f curr) : acc)

поэтому его можно переписать с помощью foldr. Например, чтобы умножить каждое число в списке на два:

let f = (* 2) in foldr (\curr acc -> (f curr) : acc) [] [1,2,3,4]

Итак, map может быть написана с помощью foldr, как мы видели:

-- Solution 2: map using foldr
mapo' :: (a -> b) -> [a] -> [b]
mapo' f xs = foldr (\curr acc -> (f curr) : acc) [] xs

Ответ 6

Ваше решение почти работает.) Проблема в том, что у вас есть две разные привязки для x в обеих ваших функциях (внутри шаблона шаблона и внутри вашего выражения лямбда), поэтому вы теряете трек первого элемента.

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x:xs)   = foldr (\x xs -> (f x):xs) [] (x:xs)

filter'             :: (a -> Bool) -> [a] -> [a]
filter' p []        = []
filter' p (x:xs)    = foldr (\x xs -> if p x then x:xs else xs ) [] (x:xs)

Это должно к трюку:). Кроме того: вы можете легко писать свои функции в стиле pointfree.

Ответ 7

Я новичок в Haskell (на самом деле я нашел эту страницу с тем же вопросом), но это мое понимание списков и foldr:

• - это элементы, которые связаны с следующим элементом с помощью оператора cons (:). они заканчиваются пустым списком []. (подумайте об этом как о двоичном операторе, как добавление (+) 1+2+3+4 = 10, 1:2:3:4:[] = [1,2,3,4]
• Функция foldr принимает функцию, которая принимает два параметра. это заменит оператор cons, который определит, как каждый элемент привязан к следующему.
• он также принимает значение терминала для операции, которое может быть жестким как начальное значение, которое будет присвоено пустым спискам. для cons это пустой список []. если вы свяжете пустой список с любым списком, результатом будет сам список. поэтому для функции sum это 0. для функции умножения это 1 и т.д.
• и он принимает сам список

Итак, мое решение таково:

filter' p = foldr (\x n -> if p x then x : n else n) []

выражение лямбда - это наша функция связи, которая будет использоваться вместо оператора cons (:). Пустым списком является наше значение по умолчанию для пустого списка. Если предикат выполняется, мы ссылаемся на следующий элемент, используя (:) как обычно, иначе мы просто не связываемся вообще.

map' f = foldr (\x n -> f x : n) []

здесь мы привязываем f x к следующему элементу вместо просто x, который просто дублирует список.

Также обратите внимание, что вам не нужно использовать сопоставление шаблонов, поскольку мы уже говорим foldr, что делать в случае пустого списка.

Я знаю, что этот вопрос действительно старый, но я просто хотел ответить на него в любом случае. Надеюсь, это не противоречит правилам.