Другой способ думать об этом - существует 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 для итога и [] для реверсо) вместе с оператором между первым значением и рекурсивным вызовом (+ для итога и (\q qs -> qs ++ [q]) для реверсо). Таким образом, структура функции для приведенных выше примеров в целом может рассматриваться как
-- 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 работает, мы теперь можем переписать reverso, используя 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 в Хаскеле называется foldr . Итак, мы переписали фильтр, используя foldr.
let p = even in foldr (\curr acc -> if (p curr) then curr:acc else acc) [] [1,2,3,4]
Итак, filter можно записать с помощью 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