content: {- 👋 Welcome to Chapter Four / Four of our journey, Staunch Wanderer!
  
  Our adventure together has almost come to an end. It has been a
  magical era of mysteries and joy. But it is still no time to
  relax. This is a critical chapter, where you finally will battle with
  Monads! Mmm, exciting!
  
  This Chapter requires the knowledge from the previous modules, so it
  is highly encouraged to at least look through the material of those
  chapters.
  
  Let's also rewind how the training works.
  
  == You are on __Chapter Four__.
  
  In the final chapter, we are going to get acquainted with more
  standard typeclasses that usually scare people off from Functional
  Programming. Still, we hope that with all that we have been through,
  these concepts won't frighten you anymore.
  
  So, in this chapter, you are going to master:
  
   ✧ Kinds
   ✧ Functors
   ✧ Applicatives
   ✧ Monads
  
  As usual, the explanations are in the Haskell comments of this
  module. We are leaving a number of tasks on our path. Your goal is to
  solve them all.
  
  After finishing the PR, you can choose to summon me, @vrom911, to look at your
  solution in order to give some advice on your code. This is optional; however,
  you can ask us for review only if you want some feedback on your solutions.
  
  Perfect. Let's crush this!
  -}
  
  {-# LANGUAGE ConstraintKinds #-}
  {-# LANGUAGE InstanceSigs    #-}
  
  module Chapter4 where
  
  {- |
  =🛡= Kinds
  
  Before we attempt to defeat the mighty and scary Monad Dragon, we need
  to talk about __kinds__. Understanding kinds is vital for the
  wholesome perception of the Haskell type system.
  
  All values in Haskell have types. But it turns out, types themselves
  also have their own "types". Such "type of a type" is called __kind__.
  
  Kinds describe the shape of a type. And kinds are much simpler than
  types. Primitive types like 'Int' have kind * (star). You can check
  information about kinds in GHCi using the ":k" command (short for ":kind"):
  
  >>> :k Int
  Int :: *
  
  ♫ NOTE: An alternative name for the star * kind is "Type". GHC is
    slowly replacing the naming of kind as * with "Type".
  
  As data types have different types, in the same manner, there are more
  than one kind of types. For example, data types like "Maybe" (that
  have an additional type parameter) have a different kind. "Maybe" is
  parameterised by a type variable. So, "Maybe" by itself doesn't have a
  kind *. We call "Maybe" a __type constructor__. There are no values of
  type "Maybe" without any parameters specified. As a consequence, you
  can't write the following function:
  
  @
  foo :: Maybe -> Int
  @
  
  It is invalid, because "Maybe" needs some type parameters. In some
  sense, you can look at "Maybe" as a function on type-level from types
  to types: you give "Maybe" some type, and you get a concrete type in
  the end. And that is the accurate description. Its kind is indeed a
  function of two stars. You can check the kind of 'Maybe' in GHCi as
  well:
  
  >>> :k Maybe
  Maybe :: * -> *
  >>> :k Maybe Int
  Maybe Int :: *
  
  You can think of types with kind * as types in their complete final
  form. Types of kind * have values. Types of any other kind don't have
  values.
  
  Haskell has one more standard kind — __Constraint__. This is the kind
  for typeclasses. You can see ordinary types of kind * on both sides of
  the function arrow (->) in type signatures. And you can see
  constraints to the left side of the context arrow (=>).
  
  You can check the kind of some standard typeclass like "Eq" to verify this:
  
  >>> :k Eq
  Eq :: * -> Constraint
  
  We hope kinds will become your kind friends by the end of this chapter :)
  -}
  
  {- |
  =⚔️= Task 1
  
  Prepare for the first task! To complete the first challenge, you need
  to explore kinds of different types in GHCi and insert the GHCi output
  after each command.
  
  As always, try to guess the output first! And don't forget to insert
  the output in here:
  
  >>> :k Char
  
  >>> :k Bool
  
  >>> :k [Int]
  
  >>> :k []
  
  >>> :k (->)
  
  >>> :k Either
  
  >>> data Trinity a b c = MkTrinity a b c
  >>> :k Trinity
  
  >>> data IntBox f = MkIntBox (f Int)
  >>> :k IntBox
  
  -}
  
  {- |
  =🛡= Functor
  
  Let's continue our journey of exploring challenging concepts by
  meeting 'Functor'. You may have heard of it and been told or imagined
  that this is some Mathematical word, and there is nothing to do with
  Functional Programming. But it is simpler.
  
  'Functor' is just a typeclass. If we think about it from this
  perspective, we would be able to objectively see what it could bring
  to the FP world and us specifically, and stop labelling it Math
  because of the name only.
  
  And maybe we can start by looking at its definition?
  
  @
  class Functor f where
      fmap :: (a -> b) -> f a -> f b
  @
  
  As you can see, this is a class definition, but with a few more
  challenging moments, we want to highlight in there.
  
  First of all, you can see that 'Functor' has one method called 'fmap',
  and it is a higher-order function — it takes a function from 'a' to
  'b' as an argument, then something called 'f a', and returns 'f b'.
  
  Before we dive into the details of 'Functor' implementation in
  Haskell, let's try to see the meaning of this typeclass and its
  method. And providing an analogy could help us with that.
  
  'Functor' allows changing the value (and even its type) in some
  context; we know this from the method's type signature. Let's say that
  a chest is our context, and its content is the value inside that
  context. You can replace the chest content with something else: you
  can fill it with gold, you can take all the coins out the chest and
  buy clothes using that money, and put back clothes in the chest
  instead. Basically, you can replace the content of a chest with
  anything else. This process of take-change-put is exactly what 'fmap'
  describes!
  
  That should make more sense now. But let's go back to Haskell. Functor
  as a typeclass is defined for a type variable called 'f'. But from the
  definition of 'fmap' you can notice that 'f' is not an ordinary
  type. 'f' itself is parameterised by some type variable 'a' — 'f a'.
  
  And in the light of the previous excursion into kinds, we can feel
  that 'f' has a more complicated kind than 'Int' (* – star), for
  example.
  
  Indeed, you can check your suspicions by inspecting the kind of the
  'Functor' typeclass in GHCi:
  
  >>> :k Functor
  Functor :: (* -> *) -> Constraint
  
  Aha! So, we see that Functor works with types of the kind `* -> *`.
  This already tells us a lot! For example, you can't implement
  "instance Functor Int" (because Int has kind *), but you can implement
  "instance Functor Maybe" (because Maybe has kind `* -> *`).
  
  And, of course, the 'Functor' instance for 'Maybe' exists in the
  standard Haskell library. Therefore, you can already use 'fmap' on any
  Maybe value:
  
  >>> fmap not (Just True)
  Just False
  
  Let's examine this one better. Maybe is parameterised by a single type
  variable. This means that 'Maybe' can store "Int", "String", list, or
  even other 'Maybe' of something inside. Basically, anything can be put
  in there until it has the fittable kind.
  
  In the example above, we use the 'not' function to 'fmap' our 'Maybe
  Bool' value. But as 'not' doesn't change the type of Bool, then we get
  'Maybe Bool' as the result of the 'fmap' in the example above.
  
  That is a nice example, but not that interesting. Let's look at this one:
  
  >>> fmap show (Just 42)
  Just "42"
  >>> fmap (replicate 3) (Just True)
  Just [True,True,True]
  
  Notice how the result type changes when we apply 'fmap' to one
  argument at a time. Haskell has type inference, so it can infer proper
  types and match them with actual types.
  
  However, if we don't have a value inside, nothing changes. Or does it?
  
  >>> fmap (replicate 3) Nothing
  Nothing
  
  Let's look at types closer:
  
  >>> :t fmap
  fmap :: Functor f => (a -> b) -> f a -> f b
  >>> :t fmap (replicate 3)
  fmap (replicate 3) :: Functor f => f a -> f [a]
  >>> :t Nothing
  Nothing :: Maybe a
  >>> :t fmap (replicate 3) Nothing
  fmap (replicate 3) Nothing :: Maybe [a]
  
  
  In GHCi we see 'Nothing', but it is not the same 'Nothing' that it's
  been before. Its type has changed.
  
  You can see how the 'Functor' instance for 'Maybe' is implemented. The
  implementation uses good old pattern matching.
  
  @
  instance Functor Maybe where
      fmap :: (a -> b) -> Maybe a -> Maybe b
      fmap _ Nothing = Nothing
      fmap f (Just a) = Just (f a)
  @
  
  And as you see the underlying type of 'Maybe' changes over the 'fmap'.
  That explains how that 'Nothing' changed its type in reality.
  
  Now you see that Functors are not magical despite having a cryptic
  name.
  
  > QUESTION: Can you understand why the following implementation of the
    Functor instance for Maybe doesn't compile?
  
  @
  instance Functor Maybe where
      fmap :: (a -> b) -> Maybe a -> Maybe b
      fmap f (Just a) = Just (f a)
      fmap _ x = x
  @
  -}
  
  {- |
  =⚔️= Task 2
  
  Implement 'Functor' instance for the "Secret" data type defined
  below. 'Secret' is either an unknown trap with something dangerous
  inside or a reward with some treasure. You never know what's inside
  until opened! But the 'Functor' instance allows changing the reward
  inside, so it is quite handy.
  -}
  data Secret e a
      = Trap e
      | Reward a
      deriving (Show, Eq)
  
  
  {- |
  Functor works with types that have kind `* -> *` but our 'Secret' has
  kind `* -> * -> *`. What should we do? Don't worry. We can partially
  apply 'Secret' to some type variable that will be fixed inside each
  method. Yes, similar to how we can partially apply functions. See, how
  we can reuse already known concepts (e.g. partial application) from
  values and apply them to the type level?
  -}
  instance Functor (Secret e) where
      fmap :: (a -> b) -> Secret e a -> Secret e b
      fmap = error "fmap for Box: not implemented!"
  
  {- |
  =⚔️= Task 3
  
  Implement Functor instance for the "List" type defined below. This
  list type mimics the standard lists in Haskell. But for training
  purposes, let's practise our skills on implementing standard
  typeclasses for standard data types.
  -}
  data List a
      = Empty
      | Cons a (List a)
  
  {- |
  =🛡= Applicative
  
  The 'Applicative' typeclass logically continues the 'Functor'
  typeclass. Again, let's look at its definition first.
  
  @
  class Functor f => Applicative f where
      pure :: a -> f a
      (<*>) :: f (a -> b) -> f a -> f b
  @
  
  Wow, that's a lot going on again! Where did all these scary creatures
  come? But if we look closer, it all looks a bit familiar already.
  
  We now can spot straightaway, that similar to Functors, only types
  with kind `* -> *` can have an Applicative instance (e.g. Maybe, and
  not 'Int' or 'Char'), as we see the same 'f a' argument in the
  methods' types.
  
  But we also can notice the constraint in the class declaration. We
  know that the constraint is the restriction on data types. And
  actually, it works similarly in the typeclass declarations as
  well. Putting this all together, it means that first, any data type
  that wants to have an Applicative instance needs to implement the
  'Functor' instance. This is what the part "Functor f => Applicative f"
  means.
  
  To be an Applicative, you first need to be "Functor". So, Functor is a
  Level 1 creature, and Applicative is a Level 2 creature. Upgraded
  Functor if you wish.
  
  Unlike Functor, Applicative has two methods: 'pure' and operator (<*>)
  called cyclops or starship or Sauron Eye. 'pure' puts a value into the
  context, and (<*>) extracts function and value from the context,
  applies the function to the argument, and puts the result back in the
  context.
  
  And continuing the chest 'Functor' analogy here, we can notice that a
  chest is also an 'Applicative'! We can put anything we want inside our
  chest, and this is what "pure" does. Or, let's say, we have one chest
  with a key inside, and this key opens a very secret box inside another
  chest. We can take both chests, extract their content, and apply one
  to another (i.e. open the box with the key), extract the content of
  the box and put it back to our chest. And this is the (<*>)
  operator. So there are valid implementations of both methods of the
  Applicative typeclass.
  
  In pursuance of the above explanation, you probably can see now why it
  is necessary to have 'Functor' first before becoming 'Applicative'. If
  we can't replace the content of the chest with some other content, how
  can we apply some actions to it and put something new inside?
  
  Now, back to Haskell. The function 'pure' takes a value and puts in
  the context 'f'. For 'Maybe' it looks like this:
  
  >>> pure True :: Maybe Bool
  Just True
  
  The (<*>) operator is much juicier: it takes a function inside the
  context, another value in the context, and returns a new value in the
  same context. Apparently, the function somehow is extracted from the
  context and applied to the extracted value.
  
  To keep an eye (<*> hehe) on the next example, let's first check that
  you still remember that in Haskell we have Higher-Order functions,
  right? This means that functions can not only be passed as arguments
  to data types but can also be stored inside other containers. Even
  'Maybe' (e.g. "Maybe (Int -> Int)")!
  
  >>> Just not <*> Just True
  Just False
  >>> Just (+ 4) <*> Just 7
  Just 11
  >>> Just (replicate 3) <*> Just 0
  Just [0,0,0]
  
  Can you guess what will happen if we try to apply (<*>) on 'Nothing'?
  Exactly — 'Nothing'! Nothing will happen.
  
  >>> Just not <*> Nothing
  Nothing
  >>> Nothing <*> Just True
  Nothing
  
  And, finally, we are ready to see how the 'Applicative' instance for
  'Maybe' really looks like:
  
  @
  instance Applicative Maybe where
      pure :: a -> Maybe a
      pure = Just
  
      (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
      Nothing <*> _ = Nothing
      Just f <*> x = fmap f x
  @
  
  So, even if the Applicative looks menacingly, there is Nothing scary
  in it after all!
  
  The next part might be a bit difficult to comprehend without having a
  lot of practice with Applicatives, but it provides some deeper meaning
  behind the concept.
  
  If 'Functor' allows changing values inside the context, 'Applicative'
  enables chaining operations. You may reasonably wonder how often we
  have functions inside 'Maybe'. But remember, that in Haskell we have
  partial application. This means that we can apply binary functions
  partially to some values inside a context, and get a function inside
  the context that requires only one argument.
  
  Now, let's think, how can we implement a function that takes two
  optional integers, and returns an optional integer with the sum of the
  given integers inside? In other words, we want a function with the
  following type signature:
  
  @
  addMaybes :: Maybe Integer -> Maybe Integer -> Maybe Integer
  @
  
  At this point you probably can implement it using pattern matching,
  but can you do it using the 'Applicative' instance for 'Maybe'? It
  turns out, this is possible!
  
  @
  addMaybes m1 m2 = fmap (+) m1 <*> m2
  @
  
  Let's disenchant this magic spell step-by-step.
  
  ghci> :t +d (+)
  (+) :: Integer -> Integer -> Integer
  ghci> :t +d fmap (+)
  fmap (+) :: Functor f => f Integer -> f (Integer -> Integer)
  ghci> :t +d fmap (+) (Just 3)
  fmap (+) (Just 3) :: Maybe (Integer -> Integer)
  
  You see that by applying 'fmap' to (+) and some 'Maybe' we get a value
  of type "Maybe (Integer -> Integer)". And this means that we can use
  the '(<*>)' operator to combine it with another "Maybe Integer".
  
  The beautiful thing about 'Applicative' is that scales over functions
  of any number of arguments. The following code is valid, if the
  function 'f' takes `x` arguments.
  
  @
  fmap f m1 <*> m2 <*> m3 <*> ... <*> m_x
  @
  
  Applicatives can be found in many applications:
  
   ✦ Chaining operations over optional values
   ✦ Parsers
   ✦ Input form validation
   ✦ Concurrent and parallel execution of tasks
  -}
  
  {- |
  =⚔️= Task 4
  
  Implement the Applicative instance for our 'Secret' data type from before.
  -}
  instance Applicative (Secret e) where
      pure :: a -> Secret e a
      pure = error "pure Secret: Not implemented!"
  
      (<*>) :: Secret e (a -> b) -> Secret e a -> Secret e b
      (<*>) = error "(<*>) Secret: Not implemented!"
  
  {- |
  =⚔️= Task 5
  
  Implement the 'Applicative' instance for our 'List' type.
  
  🕯 HINT: in the applicative instance for lists, you have a list of
    functions and a list of arguments for those functions. You need to
    apply each function to each argument and combine all the results. You
    may also need to implement a few useful helper functions for our List
    type.
  -}
  
  
  {- |
  =🛡= Monad
  
  Now, the Monad Dragon. We've come that far not to give up. If we
  managed to fight 'Functor' and 'Applicative', then sure, we can beat
  'Monad', right?💪
  
  As usual, we need to know with whom we are dealing, so let's inspect
  the 'Monad' typeclass definition:
  
  @
  class Applicative f => Monad f where
      (>>=) :: f a -> (a -> f b) -> f b
  @
  
  Look, it is just a simple typeclass! Also, it looks very familiar to
  'Functor' and 'Applicative'. You can even start thinking that they are
  all here just to confuse developers by moving arrows and 'f' letters
  from one place to another.
  
  First of all, to become a 'Monad', a Level 3 creature, a type must be
  an 'Applicative' first. Only after that, it can even dare to implement
  the (>>=) operator called __bind__.
  
  *And this is again our reporter from the Chest Analogy show live.*
   Turns out, our chest is also a monad! If our chest contains some
   gold, we can take all our gold and buy a new chest using our
   gold. The remaining gold can be put to the new chest. The amount of
   money we have determines the quality of our new chest. And this is
   what monad is about — the next context can depend on the value in the
   current context.
  
  And to expand a bit more on why you need to have the 'Applicative'
  instance before becoming a 'Monad': if you can't put values (stuff)
  inside a context (chest) using "pure", then there is no sense in
  buying a new chest at all.
  
  So, our chest is 'Functor', 'Applicative' and 'Monad'. Pure gold example!
  
  To describe the same in more technical words, The bind (>>=) operator
  takes a value of the type 'f a' ('a' in the 'f' context), a function
  from 'a' to 'f b' ('b' in the 'f' context), and returns a value of
  type 'f b'. So, to understand what it means, let's get back to our
  example with 'Maybe'. But first, we need to get a function somewhere
  that we would be able to use for the second argument of (>>=) in our
  examples.
  
  Let's implement a "safe" 'half' function, that divides a number by 2,
  but only if the number is even.
  
  -}
  half :: Int -> Maybe Int
  half n
      | even n = Just (div n 2)
      | otherwise = Nothing
  
  {- |
  
  Now, we can experiment with this function and the 'Monad' instance of
  'Maybe' in GHCi:
  
  >>> Just 6 >>= half
  Just 3
  >>> Just 3 >>= half
  Nothing
  >>> Nothing >>= half
  Nothing
  
  That makes sense — the resulting context depends on the value in the
  initial context.
  
  Let's now see how it is implemented. The instance for 'Maybe' is
  rather straightforward:
  
  @
  instance Monad Maybe where
      (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
      Nothing >>= _ = Nothing
      Just x >>= f = f x
  @
  
  Look, it is even simpler than the 'Applicative' instance! I feel
  deceived now. I heard legends about merciless Monads, scary stories
  when I was a kid, but in reality, there is Nothing special in it!
  Could I even name myself a Monad conqueror now? (Of course, you can,
  but after you try to implement the instances in the exercises)
  
  On a general note, you can notice some similarities between the main
  methods of all three typeclasses:
  
  @
  fmap  ::   (a -> b) -> f a -> f b
  (<*>) :: f (a -> b) -> f a -> f b
  (=<<) :: (a -> f b) -> f a -> f b
  @
  
  ♫ NOTE: The (=<<) operator is a version (>>=) with arguments
    flipped. It could be implemented via the regular bind operator.
  
  All type signatures look similar, but they represent different
  concepts in the end.
  -}
  
  {- |
  =⚔️= Task 6
  
  Implement the 'Monad' instance for our 'Secret' type.
  -}
  instance Monad (Secret e) where
      (>>=) :: Secret e a -> (a -> Secret e b) -> Secret e b
      (>>=) = error "bind Secret: Not implemented!"
  
  {- |
  =⚔️= Task 7
  
  Implement the 'Monad' instance for our lists.
  
  🕯 HINT: You probably will need to implement a helper function (or
    maybe a few) to flatten lists of lists to a single list.
  -}
  
  
  {- |
  =💣= Task 8*: Before the Final Boss
  
  So far we've been talking only about instances and use cases of
  different typeclasses. But one more cool thing we haven't discussed
  yet is the ability to implement functions polymorphic over the
  context. Let's say that you have two boolean values inside some
  contexts, and you want to apply the logical AND operation on them. But
  you don't know the context! It can be 'Maybe', or 'Either' or 'List',
  or anything else! However, this is not a problem in Haskell. You still
  can implement a function with the type signature described below.
  
  Can you implement a monad version of AND, polymorphic over any monad?
  
  🕯 HINT: Use "(>>=)", "pure" and anonymous function
  -}
  andM :: (Monad m) => m Bool -> m Bool -> m Bool
  andM = error "andM: Not implemented!"
  
  {- |
  =🐉= Task 9*: Final Dungeon Boss
  
  You did it! You made it to the end of Haskell practice! It probably
  was challenging, but you made it nevertheless! This makes us so happy
  and proud of you!
  
  Hope you enjoyed learning functional concepts and will continue it in
  the future!
  
  Let us know how did you like the journey and how we can make it even
  more remarkable for you! This will take you a few minutes, but is
  precious for us and future journey starters:
  
   * https://docs.google.com/forms/d/e/1FAIpQLScBVhLxq5CgGnAfIGUE-fCoOUqeGkDY2HXzbT7KV2jjLOsmjQ/viewform
  
  
  Also, challenge your friends with this course and spread the word about us!
  We are @kowainik on Twitter. You can also use #Learn4Haskell hashtag to share
  your story.
  
  We also have a Ko-fi page, if you want to buy us a coffee after a long road.
   ☕️ https://ko-fi.com/kowainik
  
  You can also support creators of this course and your proud mentors on GitHub:
    ✧ https://github.com/sponsors/vrom911
  
  Now, for the dessert, it is time to test your skills on the final boss!
  Your task now will be to implement a Binary Tree data structure and
  some functions on it.
  
  Specifically,
  
   ❃ Implement a polymorphic binary tree type that can store any
     elements inside its nodes
   ❃ Implement the Functor instance for Tree
   ❃ Implement the reverseTree function that reverses the tree and each
     subtree of a tree
   ❃ Implement the function to convert Tree to list
  -}
  
  
  {-
  You did it! Now it is time to open pull request with your changes
  and summon @vrom911 for the review!
  -}
  