Fold
Fold
Intro
| Module: | Prelude |
|---|---|
| Function: | foldl |
| Type: | [(a -> b -> a) -> a -> b] -> a |
| Description: | it takes the second argument and the first item of the list and applies the function to them, then feeds the function with this result and the second argument and so on. See scanl for intermediate results. |
| Related: | foldl1, foldr, foldr1, scanl, scanl1, scanr, scanr1 |
Example 1
Input: foldl (/) 64 [4,2,4]
Output: 2.0
Example 2
Input: foldl (/) 3 []
Output: 3.0
https://en.wikipedia.org/wiki/Fold_(higher-order_function)
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
| Rust | *iterator*.fold(*initval*, *func*) |
*iterator*.rev().fold(*initval*, *func*) |
||||
| Scala | *list*.foldLeft(*initval*)(*func*) (*initval* /: *list*)(*func*) |
*list*.foldRight(*initval*)(*func*) (*list* :\ *initval*)(*func*) |
https://blog.csdn.net/zwvista/article/details/54747749
Map
-- 映射
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
-- map f [a, b, c, d] = f a : f b : f c : f d : []
-- 过滤
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
-- p a==True, p b==False, p c==False, p d==True
-- filter f [a, b, c, d] = a : d : []
用fold实现map
分析：如何构造fold的函数F？
F的输入有两个a，b，输出类型为a；对于map来说，输出类型为[b]。所以F的第一个输入类型应该是[b]，而第二个类型为b
-- 映射
map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> (f x):acc) [] xs
-- 过滤
filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = foldr (\x acc -> if p x then x:acc else acc) [] xs
用C++实现
// ConsoleApplication1.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <vector>
#include <assert.h>
template <class F, class A, class B>
A foldl(F f, A a, std::vector<B> const& b)
{
if (b.empty())
{
return a;
}
return foldl(f, f(a, b[0]), std::vector<int>(b.begin() + 1, b.end()));
}
template <class B, class F, class A>
std::vector<B> Map(F f, std::vector<A> const& a)
{
return foldl(
[f](std::vector<B> const& b2, A a2) -> std::vector<B>
{
auto t = b2;
t.push_back(f(a2));
return t;
}
, std::vector<B>(), a);
}
template <class F, class A>
std::vector<A> Filter(F f, std::vector<A> const& a)
{
return foldl(
[f](std::vector<A> const& b2, A a2) -> std::vector<A>
{
auto t = b2;
if(f(a2))
t.push_back(a2);
return t;
}
, std::vector<A>(), a);
}
void main()
{
assert(foldl([](int a, int b) {return a + b; }, 0, std::vector<int>{ 1, 2, 3 })
==1 + 2 + 3);
auto t = Map<int>([](int a) {return a + 1; }, std::vector<int>{ 1, 2, 3 });
auto t2 = Filter([](int a) {return a%2==0; }, std::vector<int>{ 1, 2, 3, 4 });
1 + 2;
}
Point-free style
1
Point-free style means that the arguments of the function being defined are not explicitly mentioned, that the function is defined through function composition.
If you have two functions, like
square :: a -> a
square x = x*x
inc :: a -> a
inc x = x+1
and if you want to combine these two functions to one that calculates x*x+1, you can define it “point-full” like this:
f :: a -> a
f x = inc (square x)
The point-free alternative would be not to talk about the argument x:
f :: a -> a
f = inc . square
2
Haskell example:
Conventional (you specify the arguments explicitly):
sum (x:xs) = x + (sum xs)
sum [] = 0
Point-free (sum doesn’t have any explicit arguments - it’s just a fold with + starting with 0):
sum = foldr (+) 0
Or even simpler: Instead of g(x) = f(x), you could just write g = f.
3
函数组合的另一用途就是定义 point free style (也称作 pointless style) 的函数。就拿我们之前写的函数作例子：
sum' :: (Num a) => [a] -> a
sum' xs = foldl (+) 0 xs
等号的两端都有个 xs。由于有柯里化 (Currying)，我们可以省掉两端的 xs。foldl (+) 0 回传的就是一个取一 List 作参数的函数，我们把它修改为 sum' = foldl (+) 0，这就是 point free style。
4
下面这个函数又该如何改成 point free style 呢？
fn x = ceiling (negate (tan (cos (max 50 x))))
像刚才那样简单去掉两端的 x 是不行的，函数定义中 x 的右边还有括号。cos (max 50) 是有错误的，你不能求一个函数的余弦。我们的解决方法就是，使用函数组合。
fn = ceiling . negate . tan . cos . max 50
漂亮！
Ref
https://wiki.jikexueyuan.com/project/haskell-guide/high-order-function.html