-- | Notes taken by Ugnė Pacevičiūtė 
--
-- In this lesson we will discuss two main topics: recursion and
-- Algebraic Data Types (ADT).
module Lessons.Lesson02 (f,f',length', length'', t1, t2, trd, FireExtinguisher(..), FEType(..),
    capacity, refill) where

-- | This is the first example of a recursive function.
-- Since Haskell is ummutable, we cannot have loops like one would
-- have in C, Java or C#. Recursion is the only awailable tool.
--
-- Also it uses a technique called pattern matching: a function might
-- have a few body lines which are tested top-down. The first matching
-- the actual arguments is applied.
-- Underscore matches any element but ignores it. `:` deconstructs a list
-- into a head (single first element) and a tail (a list of elements w/o the head).
--
-- The function return the head of a list, or 0 if the list is empty.
--
-- >>> f []
-- 0
--
-- >>> f [1,2,3]
-- 1
f :: [Integer] -> Integer
f :: [Integer] -> Integer
f [] = Integer
0
f (Integer
h:[Integer]
_) = Integer
h

-- | This pattern matching is dangerous, if only one-element list is
-- provided to the function it throws an exception.
--
-- >>> f' []
-- 0
--
-- >>> f' [1]
-- /workspaces/fp-2025/src/Lessons/Lesson02.hs:(40,1)-(41,9): Non-exhaustive patterns in function f'
--
-- >>> f' [1,2]
-- 1
f' :: [Integer] -> Integer
f' :: [Integer] -> Integer
f' (Integer
h1:Integer
h2:[Integer]
_) = Integer
h1
f' [] = Integer
0

-- | Let's implement our first recursive function! It calculates a length of
-- a list (with elements of any type `a`).     
--    
-- This function is mathematically correct but it consumes stack space to keep
-- intermediate "+" arguments. So this function will fail on "large" lists.
--
length' :: [a] -> Int
length' :: forall a. [a] -> Int
length' [] = Int
0
length' (a
_:[a]
t) = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ [a] -> Int
forall a. [a] -> Int
length' [a]
t

-- | To eliminate this drawback using a [Tail call optimization](https://en.wikipedia.org/wiki/Tail_call).
-- We need the recursive call to be a final action of the function.
--
-- To achieve this we will have to introduce an additional parameter acc - accumulator where
-- we will collect intermediate results (and not on a top of the stack).
length'' :: [a] -> Int
length'' :: forall a. [a] -> Int
length'' [a]
l = [a] -> Int -> Int
forall a. [a] -> Int -> Int
length''' [a]
l Int
0
    where
        length''' :: [a] -> Int -> Int
        length''' :: forall a. [a] -> Int -> Int
length''' [] Int
acc = Int
acc
        length''' (a
_:[a]
t) Int
acc = [a] -> Int -> Int
forall a. [a] -> Int -> Int
length''' [a]
t (Int
acc Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)

-- | Now let's switch to "data structures".
--
--A tuple is fixed-size structure which can contain different type elements 
t1 :: (Integer, Char)
t1 :: (Integer, Char)
t1 = (Integer
42, Char
'a')

-- | Three element's tuple
t2 :: (Integer, Int, String)
t2 :: (Integer, Int, String)
t2 = (Integer
43, -Int
1, String
"labas")

-- | Tuples can be pattern-matched.
--
-- This function is also an example of "parametric polymorphism": we have no
-- concrete types, only type variables which are not know at the time of function
-- declaretion but will be know at compilation time
--
-- >>> trd (1, 10.09, "labas")
-- "labas"
trd :: (a, b, c) -> c
trd :: forall a b c. (a, b, c) -> c
trd (a
_, b
_, c
v) = c
v

-- | ADT - Algerbraic data type - is way to define custom "data structures".
-- Left hand side is a type (name). Right hand side is a list of constructors.
-- Please ignore the "deriving Show" part of the declarations, it just says
-- the GHC compiler to generate a default String representation of the ADT.
-- We will be back to this question soon.
--
-- One way to define an ADT is just a "named tuple". It acts like a tuple but has a name:
-- `FireExtinguisher` is a constructor with two arguments `Integer`
-- AND `FEType`. To create a `FireExtinguisher` you have to pass both of them.
--
-- Constructors act like ordinary functions:
--
-- >>> :t FireExtinguisher 10
-- FireExtinguisher 10 :: FEType -> FireExtinguisher
data FireExtinguisher = FireExtinguisher Integer FEType deriving Int -> FireExtinguisher -> ShowS
[FireExtinguisher] -> ShowS
FireExtinguisher -> String
(Int -> FireExtinguisher -> ShowS)
-> (FireExtinguisher -> String)
-> ([FireExtinguisher] -> ShowS)
-> Show FireExtinguisher
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> FireExtinguisher -> ShowS
showsPrec :: Int -> FireExtinguisher -> ShowS
$cshow :: FireExtinguisher -> String
show :: FireExtinguisher -> String
$cshowList :: [FireExtinguisher] -> ShowS
showList :: [FireExtinguisher] -> ShowS
Show

-- | You might have a few constructors for a ADT. `FEType` can be create by calling the
-- `A` constructor OR `B` constructor OR `C` constructor.
--
-- >>> A
-- A
data FEType = A | B | C deriving Int -> FEType -> ShowS
[FEType] -> ShowS
FEType -> String
(Int -> FEType -> ShowS)
-> (FEType -> String) -> ([FEType] -> ShowS) -> Show FEType
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> FEType -> ShowS
showsPrec :: Int -> FEType -> ShowS
$cshow :: FEType -> String
show :: FEType -> String
$cshowList :: [FEType] -> ShowS
showList :: [FEType] -> ShowS
Show

-- | ADTs can be pattern matched.
capacity :: FireExtinguisher -> Integer
capacity :: FireExtinguisher -> Integer
capacity (FireExtinguisher Integer
c FEType
_) = Integer
c

-- | Usually you create new ADTs based on already existing ones.
refill :: FireExtinguisher -> FireExtinguisher
refill :: FireExtinguisher -> FireExtinguisher
refill (FireExtinguisher Integer
_ FEType
t) = Integer -> FEType -> FireExtinguisher
FireExtinguisher Integer
10 FEType
t