Foldr

Universal property

Foldr & foldl

Map & filter

Fold and tuple

Fold and function

Universal property

Foldr & foldl

Map & filter

Fold and tuple

Fold and function

foldr의 정의

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

foldr의 정의

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr accum initial [] = initial
foldr accum initial (x:xs) = accum x (foldr accum initial xs)

The universal property of fold

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

-- 어떤 함수 y가 있을 때 f와 v에 대해서 다음 꼴을 만족한다면
y [] = v
y (x:xs) = f x (y xs)

-- y는 foldr로 정의할 수 있습니다.
y = foldr f v

The universal property of fold

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

-- 어떤 함수 y가 있을 때 f와 v에 대해서 다음 꼴을 만족한다면
y [] = v
y (x:xs) = f x (y xs)

-- y는 foldr로 정의할 수 있습니다.
y = foldr f v


sum :: Num a => [a] -> a
-- v = 0
sum [] = 0
-- f = (+)
sum (x:xs) = x + (sum xs)

The universal property of fold

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

-- 어떤 함수 y가 있을 때 f와 v에 대해서 다음 꼴을 만족한다면
y [] = v
y (x:xs) = f x (y xs)

-- y는 foldr로 정의할 수 있습니다.
y = foldr f v


product :: Num a => [a] -> a
-- v = 1
product [] = 1
-- f = (*)
product (x:xs) = x * (product xs)

Universal property

Foldr & foldl

Map & filter

Fold and tuple

Fold and function

foldr과 foldl

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f v [] = v
foldl f v (x:xs) = foldl (f v x) xs

foldr 펼치기

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

foldr (+) 0 [1,2,3]
1 + (foldr (+) 0 [2,3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0))
1 + (2 + 3)
1 + 5
6

foldl 펼치기

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f v [] = v
foldl f v (x:xs) = foldl (f v x) xs

foldl (+) 0 [1,2,3]
foldl (+) (1 + 0) [2,3]
foldl (+) (2 + (1 + 0)) [3]
foldl (+) (3 + (2 + (1 + 0))) []
(3 + (2 + (1 + 0)))
(3 + (2 + 1))
(3 + 3)
6

short-circuit foldr

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

fstArg a b = a

foldr fstArg 3 [1,2,3]
-> fstArg 1 (foldr fstArg 3 [2,3])
-> 1

strict foldl

foldl' :: (b -> a -> b) -> b -> [a] -> b

foldl' (+) 0 [1,2,3]
foldl' (+) 1 [2,3]
foldl' (+) 3 [3]
foldl' (+) 6 []
6

Universal property

Foldr & foldl

Map & filter

Fold and tuple

Fold and function

Map

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

map f (x:xs) = (:) (f x) (map f xs)
map f (x:xs) = ((:) . f) x (map f xs)

map = foldr ((:) . f) []

Filter

filter :: (a -> Bool) -> [a] -> [b]

filter p [] = []
filter p (x:xs) = if p x then x:(filter p xs) else (filter p xs)

-- 위 함수를 foldr 형식으로 바꿔보겠습니다.
filter p (x:xs) = (++) (if p x then [x] else [])  (filter p xs)
filter p (x:xs) = ((++) . (\x -> if p x then [x] else [])) x (filter p xs)

-- 따라서 
filter p = foldr ((++) . (\x -> if p x then [x] else [])) []

Universal property

Foldr & foldl

Map & filter

Fold and tuple

Fold and function

Fold and tuple

y = foldr f v

y [] = v
y (x:xs) = x `f` (y xs)

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

dropWhile p (x:xs) = (\y ys -> if p y then ys else y : xs) x (dropWhile p xs)

Fold and tuple

y = foldr f v

y [] = v
y (x:xs) = x `f` (y xs)


dropWhile' :: (a -> Bool) -> ([a] -> ([a], [a]))
dropWhile' p xs = (dropWhile p xs, xs)

dropWhile' p [] = ([], [])
dropWhile' p (x:xs) = if p x then (dropWhile p xs, x:xs) else (x:xs, x:xs)
dropWhile' p (x:xs) =
    let (zs, _) = dropWhile' p xs
    in if p x then (zs, x:xs) else (x:xs, x:xs)
-- zs = dropWhile p xs 
dropWhile' p (x:xs) =
  (\y (zs, ys) -> if p y then (zs, y:ys) else (y:ys, y:ys)) x (dropWhile' p xs)

Universal property

Foldr & foldl

Map & filter

Fold and tuple

Fold and function

Foldr 과 함수

compose :: [x -> x] -> (x -> x)
compose = foldr (.) id

-- 예시)
-- compose [ (+1), (+2), (+3) ]
-- -> (+1) . ( (+2) . ( (+3) . id) )
-- -> (+1) . ( (+2) . (+3) )
-- -> (+1) . (+5)
-- -> (+6)

Foldr 과 함수

suml :: [Int] -> Int
suml xs = suml' xs 0
    where
        suml' [] n = n
        suml' (x:xs) n = suml' xs (n + x)

suml' [] = v
suml' (x:xs) = f x (suml' xs)

v 찾기

suml' [] n = v n
-- -> suml' [] n = n = v n
-- -> v = id

Foldr 과 함수

suml :: [Int] -> Int
suml xs = suml' xs 0
    where
        suml' [] n = n
        suml' (x:xs) n = suml' xs (n + x)

f 찾기

suml' (x:xs) n = f x (suml' xs) n
-> suml' xs (n + x) = f x (suml' xs) n
-- suml' xs를 y로 치환
-> y (n + x) = f x y n
-> f = \x y n -> y (n + x)
-- 인자를 2개로 맞춥니다.
-> f = \x y -> (\n -> y (n + x))

suml' = foldr (\x y -> (\n -> y (n + x))) id
suml xs = foldr (\x y -> (\n -> y (n + x))) id xs 0