Foldl.hs

import Prelude hiding (foldl)

-- Module 3. Lists
-- 3.5 Левая свертка и ее сравнение с правой


-- 1) Левая свёртка
    -- Задача 1
-- 2) Реализация левой свёртки
-- 3) Строгая версия левой свёртки
-- 4) Продуктивность правой свёртки
-- 5) Свёртки-многостаночники
    -- Задача 2
    -- Задача 3
    -- Задача 4

{-
foldr f ini [] [1:2:3] ->> 1 `f` (2 `f` (3 `f` ini )) 

((ini `f` 1) `f` 2) `f` 3 -- операторный синтаксис

f(f(f ini 1) 2) 3         -- функциональный стиль

foldl :: (b -> a -> b) -> b [a] -> b
foldl _ ini []     = ini
foldl f ini (x:xs) = foldl f (f ini x) xs
-}


{-
foldr f z (a:b:c:d) = f(a f(b f(c f(d z)))), 
а foldl f z (a:b:c:d) = f(f(f(f(z a) b) c) d). 
Для каких-то f (например +,*) обе функции вернут
то же значение.
Но в общем случае результат будет разный
-}

    -- Задача 1
-- При каком значении переменной x следующие два выражения примут
-- одно и то же значение (отличное от неопределенного)?

-- foldr (-) x [2,1,5] 2 -(1-5) = 6
-- foldl (-) x [2,1,5] (-5 -1 - 2) = -8

-- right: (2 - (1 - (5 - 0))) = 6
-- left: ((0-2) -1) - 5) = -8

-- right: (2 - (1 - (5 - x))) = y
-- left: ((x-2) -1) - 5) = y
-- (2 - (1 - (5 - x))) = ((x-2) -1) - 5)
-- x = 7

-- cool!!
-- [ x | x <- [-100..100], foldl (-) x [2,1,5] == foldr (-) x [2,1,5] ]


-- 2) Реализация левой свёртки

foldl'' :: (b -> a -> b) -> b -> [a] -> b
foldl'' _ ini []     = ini
foldl'' f ini (x:xs) = foldl'' f (f ini x) xs

{-
foldl f ini 1:2:3:[]
~> fold f (f ini 1) (2:3:[])
~> fold f(f(f ini 1) 2) (3:[])
~> fold f(f(f(f ini 1) 2) 3) []
~> f (f (f ini 1) 2) 3
-}

-- получается неэффективно, если списко длинный, то 
-- создается огромное отложенное вычисление, 
-- поэтому крайне не рекомендуется
-- нужно использоваться строгую версию, которая ообычно используется


-- 3) Строгая версия левой свёртки

{-
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f ini []      = ini
foldl f ini (x:xs)  = foldl f (f ini x) xs
-}


foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f ini []      = ini
foldl f ini (x:xs)  = foldl f ini' xs -- ini' нужно форсировать при вычислении
    where ini' = f ini x

foldl'              :: (b -> a -> b) -> b -> [a] -> b
foldl' f ini []      = ini
foldl' f ini (x:xs)  = ini' `seq` foldl f ini' xs
    where ini' = f ini x


-- 4) Продуктивность правой свёртки

{-
Поведение правой и левой свертки на бесконечных списках
Правая свертка на бесконечном списке способна остановиться
-}

any :: (a -> Bool) -> [a] ->  Bool
any p = foldr (\x b -> p x || b) False

{-
any (== 2) [1..]
~> foldr (\x b -> (==2) x || b) False (1:[2..])
~> (\x b -> (==2) x || b) 1 (foldr (\x b (==2) x || b) False [2..1])
~> False || (foldr (\x b -> (==2) x || b) False [2..])
~> foldr (\x b -> (==2) x || b) False 2:[3..]
~> True || foldr (\x b -> (==2) x || b) False [3..1]
~> True
-}

-- (||) :: Bool -> Bool -> Bool
-- False || x = x
-- True  || _ = True


-- 5) Свёртки-многостаночники

-- за одни проход нужно выполнить сумму и произведение элементов списка
-- сопоставление с образцом внутри лямбды

-- ghci> foldr (\x (s,p) -> (x+s, x*p)) (0,1) [1,2,3,4]
-- (10,24)


    -- Задача 2
{-
Реализуйте функцию meanList, которая находит среднее значение элементов
списка, используя однократный вызов функции свертки.

GHCi> meanList [1,2,3,4]
2.5

Постобработка считается допустимой, то есть предполагаемая реализация
функции meanList имеет вид

meanList = someFun . foldr someFoldingFun someIni
-}

meanList :: [Double] -> Double
meanList = someFun . foldr someFoldingFun someIni


someIni :: (Num a, Num b) => (a, b)
someIni = (0, 0)

someFoldingFun :: (Num a, Num b) => a -> (a, b) -> (a, b)
someFoldingFun x (s,c) = (s+x, c+1)

someFun :: Fractional a => (a, a) -> a
someFun (a,b) = a / b


-- alternative:
-- meanList :: [Double] -> Double
-- meanList = (uncurry (/)) . (foldr (\x (s, cnt) -> (s + x, cnt + 1)) (0, 0))
{-
В данном коде uncurry применяется к функции деления /. uncurry - это функция
высшего порядка, которая принимает функцию двух аргументов и преобразует
ее в функцию, принимающую пару значений. 

В данном случае, функция деления / ожидает два аргумента типа a, где a
является числовым типом. Однако, результат foldr возвращает пару значений
(s, cnt), где s и cnt также являются числами. 

Использование uncurry позволяет применить функцию деления / к результату
foldr, передавая ему пару значений (s, cnt) вместо отдельных аргументов
s и cnt. Таким образом, uncurry (/) преобразует функцию деления / в
функцию, которая принимает пару значений и выполняет деление.

Затем, с использованием композиции функций с помощью точки, применяется
результат foldr к uncurry (/). Таким образом, meanList применяет
foldr для обработки списка и возвращает среднее значение списка,
вычисленное с использованием функции деления /.
-}


    -- Задача 3

{-
Используя однократный вызов свертки, реализуйте функцию evenOnly,
которая выбрасывает из списка элементы, стоящие на нечетных местах,
оставляя только четные.

GHCi> evenOnly [1..10]
[2,4,6,8,10]
GHCi> evenOnly ['a'..'z']
"bdfhjlnprtvxz"
-}


evenOnly :: [a] -> [a]
evenOnly xs = snd $ foldr (\x (i, acc) -> if even i then (i-1, x:acc) else (i-1, acc)) (length xs, []) xs

-- solution by staff:
evenOnly' :: [a] -> [a]
evenOnly' = snd . foldr (\a (xs, ys) -> (a : ys, xs)) ([], [])
{-
Anatomy
[1,2,3,4,5]
~> \1 (xs, ys) -> (1 : ys, xs)
~> \2 (1 : ys, xs) -> (2 : xs, 1 : ys)
~> \3 (2 : xs, 1 : ys) -> (1 : 3 : ys, 2 : xs)
~> \4 (1 : 3 : ys, 2 : xs) -> (2 : 4 : xs, 1 : 3 : ys)
~> \5 (2 : 4 : xs, 1 : 3 : ys) -> (1 : 3 : 5 : ys, 2 : 4 : xs)
~> \[] (1 : 3 : 5 : [], 2 : 4 : [])
~> snd (1 : 3 : 5 : [], 2 : 4 : [])
~> 2 : 4 : []
-}

{-
идёт с конца по списку, хранит пару из двух списков. Когда надо добавить очередной
элемент, меняет списки в паре местами и приписывает к левому — соответственно,
элементы по очереди приписываются к одному списку — к другому — к одному — к
другому. В итоге просто возвращает правильный список (правильной — это не тот,
в который был добавлен последний [первый в исходном списке] элемент). 
-}

    
    -- Задача 4

{-
Попробуйте добиться того, чтобы реализованная вами в прошлом задании функция
evenOnly позволяла работать и с бесконечными списками.
То есть, например, запрос на первые три элемента бесконечного списка, возвращаемого
этой функцией, примененной к списку всех натуральных чисел, должен завершаться:

GHCi> take 3 (evenOnly [1..])
[2,4,6]
-}
evenOnly'' :: [a] -> [a]
evenOnly'' = snd . foldr (\x ~(xs, ys) -> (x : ys, xs)) ([], [])

-- evenOnly :: [a] -> [a]
-- evenOnly (x:y:xs) = y : evenOnly xs
-- evenOnly _ = [] 


-- evenOnly :: [a] -> [a]
-- evenOnly xs = [x | (x,n) <- zip xs [1..], even n]

-- evenOnly :: [a] -> [a]
-- evenOnly = foldr (\(i, x) xs -> if even i then x:xs else xs) [] . zip [1..]