-- An attempt to explain monads to C# (and other OO) programmers.
-- By Peter Verswyvelen

import Prelude hiding ((>>), (>>=), return, IO)
import System.Random

-- GOAL: Compute a random 3D point inside some volume.

-- First, the C# 2.0 version
{-

using System;

public class Program
{
    public struct Point3D
    {
        public readonly int X, Y, Z;

        public Point3D( int x, int y, int z )
        {
            X = x;
            Y = y;
            Z = z;
        }
    }

    public static int randomInt( Random seed, int range )
    {
        return seed.Next() % range;
    }

    public static Point3D randomPoint(Random seed, int width, int height, int depth)
    {
        int x = randomInt( seed, width );
        int y = randomInt( seed, height );
        int z = randomInt( seed, depth );
        return new Point3D( x, y, z );
    }
}

-}

-- Next, the Haskell version. We will start with an incorrect naive approach and evolve towards monads...
-- I will assume you are new to Haskell, and know nothing about lambda functions, currying, partial application and monads...

---------------------------------------------------------------------------------------------------------------
-- Some constants for testing

volumeWidth  = 100
volumeHeight = 100
volumeDepth   = 100
initialSeed  = mkStdGen 0

---------------------------------------------------------------------------------------------------------------
-- StdGen is defined in the prelude and represents the standard random generator, which we informally call the "seed" here.
type Seed = StdGen

-- Declare the 3D point, and derive functions to show it as a string
data Point3D = Point3D Int Int Int deriving Show

---------------------------------------------------------------------------------------------------------------
-- TAKE 1: Naive imperative programmer's approach...

-- randomValue1 computes a pseudo random value between [0..range)
--
-- Note: next, fst, mod are functions from the prelude;
-- (fst (x,y)) returns x (the first value of a pair)
-- (next seed) returns the pair (randomValue, newSeed)
-- (mod x y) computes x modulo y. 
-- (x `mod` y) is the operator form of the mod function.
-- In Haskell, you can use any binary function as an operator by enclosing it in back-quotes
randomValue1 :: Seed -> Int -> Int
randomValue1 seed range = fst (next seed) `mod` range

-- randomPoint1 computes a random 3D point in the range ( [0..width), [0..height), [0..depth) )
randomPoint1 :: Seed -> Int -> Int -> Int -> Point3D
randomPoint1 seed width height depth = Point3D x y z where
  x = randomValue1 seed width
  y = randomValue1 seed height
  z = randomValue1 seed depth

-- Let's test it.
test1 = randomPoint1 initialSeed volumeWidth volumeHeight volumeDepth
-- Result: Point3D 84 84 84

-- Oops, that did not work, we always get the same coordinates...
-- Of course, that's because the same seed is passed to randomValue1 on each iteration.
-- In imperative or object-oriented languages, mutable variables are used to solve this, but Haskell is a pure functional language, so it does not have mutable variables in the C/C++/C# sense (for good reasons beyond the scope of this tutorial). 
-- Now because we don't have mutable variables in Haskell, we must return the modified seed from randomValue1 and randomPoint1.
-- Back to the drawing board...

---------------------------------------------------------------------------------------------------------------
-- TAKE 2: Passing the modified seed around

randomValue2 :: Seed -> Int -> (Int,Seed)
randomValue2 seed0 range = (value `mod` range, seed1) where (value, seed1) = next seed0

randomPoint2 :: Seed -> Int -> Int -> Int -> (Point3D,Seed)
randomPoint2 seed0 width height depth = ( Point3D x y z, seed3 ) where
  (x,seed1) = randomValue2 seed0 width
  (y,seed2) = randomValue2 seed1 height
  (z,seed3) = randomValue2 seed2 depth

-- Let's test it.
test2 = fst (randomPoint2 initialSeed volumeWidth volumeHeight volumeDepth)

-- Result: Point3D 84 94 64 

-- The result looks correct, but it is annoying and error prone to come up with new seed names and pass them around explicitly.
-- Surely, we must be able to improve this. Ultimately we would like to write something like (in pseudo code)
--
-- randomPoint2 width height = ( x := randomValue2 width; y := randomValue2 height; z := randomValue2 depth; return (Point3D x y z) )
--
-- where we treat the seed as a "global" variable as you get when you use C's rand() function. 
--
-- Of course in Haskell, you don't have global mutable variables, and we don't want them either, so we must come up with something different.
--
-- The imperative programmer executes statements in a specific order, one after the other, seperated by ;
-- In our case the dependency on the seed values determines the order of execution.
--
-- So let's think about a way to combine functions using some operator, 
-- passing the result (if any) from one function to the other, together with the modified seed.
--
-- That looks hard. So let's start simpler: only passing the modified seed between functions.

---------------------------------------------------------------------------------------------------------------
-- TAKE 3: combining functions together, only passing the modified seed between them.

-- Combine the functions
combine3 :: (Seed -> (a, Seed)) -> (Seed -> (b, Seed)) -> Seed -> (b, Seed)
combine3 f1 f2 seed0 = (value2, seed2) where
  (value1, seed1) = f1 seed0
  (value2, seed2) = f2 seed1

-- In C# we combine statements using the ; seperator.
-- Let's define our own operator for doing this. 
-- Notice that the output of this operator is compatible with its input, so it can be applied in a sequence, like f1 |> f2 |> f3 ...
-- Also note that I could have dropped the last pair of parentheses on the type signature without making a difference.
-- So (|>) :: (Seed -> (a, Seed)) -> (Seed -> (b, Seed)) -> Seed -> (b, Seed) would be the same function.
-- This is a consequence of currying: in Haskell, each function actually takes just a single parameter.
-- See http://www.haskell.org/haskellwiki/Currying for more details 
(|>) :: (Seed -> (a, Seed)) -> (Seed -> (b, Seed)) -> (Seed -> (b, Seed))
f1 |> f2 = combine3 f1 f2

--- Here we just call 3 random functions for testing.
dummy3a seed0 range = (value3,seed3) 
  where
    (value1, seed1) = randomValue2 seed0 range
    (value2, seed2) = randomValue2 seed1 range
    (value3, seed3) = randomValue2 seed2 range

-- Combine 3 random functions just for testing.
dummy3b seed0 range = (rv |> rv |> rv) seed0 
  where
    rv seed = randomValue2 seed range 

-- Let's test if it works. 
test3 = (fst (dummy3a initialSeed volumeWidth), fst (dummy3b initialSeed volumeWidth))

-- Result: (64,64)

-- We get twice the same result, so our combinator seems to work (this is not a prove, just an indication ;-)

-- But it is still annoying to pass the seed around. 
-- We like to treat it as a "global" variable in the context of our functions.
--
-- To solve this, we can make use of Haskell's partial application. 
-- See http://www.haskell.org/haskellwiki/Partial_application
--
-- To do this, we must move the seed argument to the end of the argument list.
-- In Haskell, it is always a good idea to move arguments that are common to a group of functions to the end of the argument list.
-- For example, if you are writing a simulation where "time" is passed around to all functions, make time the last argument, 
-- and invent your own combinators to glue together time-related higher order functions. This gives nice easy to read code. 
-- See http://haskell.org/soe for more details.

-- So let's rewrite our random functions with the seed as the last argument.

---------------------------------------------------------------------------------------------------------------
-- TAKE 4: dropping the seed

randomValue4 range seed = randomValue2 seed range 
randomPoint4 width height depth seed = randomPoint2 seed width height depth

-- Now if we write (randomValue5 range) we have created a function that returns a function of type Seed -> (Int,Seed).

-- So now we can drop the seed. Hopefully something nice grows out of it.
dummy4 range = (rv |> rv |> rv) where rv = randomValue4 range 

test4 = fst (dummy4 volumeWidth initialSeed)
-- Result: 64

-- So far so good, but combining functions without passing the value from a function application to the next one is rather useless in our case, 
-- although a similar technique is useful when e.g. printing simple text on the screen, etc

-- So how do we combine functions and pass values around? Let's give it a shot.

---------------------------------------------------------------------------------------------------------------
-- TAKE 5: Combining functions and besides passing the modified seed, 
-- also passing the value from the first function application to the next one.

combine5 :: (Seed -> (a,Seed)) -> (a -> Seed -> (b,Seed)) -> (Seed -> (b,Seed))
combine5 f1 ff2 seed0 = (value2,seed2)
   where
     (value1,seed1) = f1 seed0
     f2 = ff2 value1
     (value2,seed2) = f2 seed1

-- Note the second function is called ff2. This is not a typo. 
-- You can look at ff2 as a function taking two arguments (value1 seed1),
-- or as a function that, given value1, evaluates to a function that, given seed1, evaluates to something of type (b, Seed). 
-- Again, this is just a consequence of currying and partial application.
-- Wow that's a mouthful. But the code should be easier to read ;) 

-- Writing these function signatures gets bulky. 
-- So let's define a type for functions that take a seed as input, and deliver some value and a modified seed as output.
type SeedIO a = Seed -> (a, Seed)

-- Now let's define the operator that combines functions together, making use of the SeedIO type.
-- Again notice that the output of this operator is compatible with its input, so it can be applied in a sequence, like f1 >>= f2 >>= f3 ...
(|>=) :: (SeedIO a) -> (a -> SeedIO b) -> (SeedIO b)
fa |>= ffb = combine5 fa ffb

-- So let's rewrite randomPoint using the >>= operator. 
-- To make it clear what the full function definitions are, 
-- I'll add the seed again to every function for clarity
randomPoint5a :: Int -> Int -> Int -> SeedIO Point3D
randomPoint5a width height depth seed0 = (rvw |>= fx) seed0
  where
    rvw seed = randomValue4 width seed
    rvh seed = randomValue4 height seed
    rvd seed = randomValue4 depth seed
    return value seed = (value,seed)
    fx x seed = (rvh |>= (fy x)) seed
    fy x y seed = (rvd |>= (fz x y)) seed
    fz x y z seed = return (Point3D x y z) seed

-- Of course I could again drop the seed.
-- Note that I even dropped all arguments in the return function.
-- (,) x y is the function form of the (x,y)
randomPoint5b :: Int -> Int -> Int -> SeedIO Point3D
randomPoint5b width height depth = (rvw |>= fx)
  where
    rvw = randomValue4 width 
    rvh = randomValue4 height 
    rvd = randomValue4 depth 
    return = (,)
    fx x = (rvh |>= (fy x)) 
    fy x y = (rvd |>= (fz x y)) 
    fz x y z = return (Point3D x y z)

-- Here we use the $ operator, so we have to type less parentheses. 
-- (f $ x) is just the same as (f x), but $ has the lowest precedence and is right associative, so everything to its right is evaluated first.
test5 = (fst $ randomPoint5a volumeWidth volumeHeight volumeDepth initialSeed, fst $ randomPoint5b volumeWidth volumeHeight volumeDepth initialSeed)
-- Result: (Point3D 84 94 64,Point3D 84 94 64)

-- Now you're thinking "wait a second dude, you just made things even more complicated!!! How much longer do I have to endure this???"
-- Hang on, let's rewrite it, but this time make use of on more Haskell feature, lambda functions, which are a lot like C# 2.0 anonymous delegates (C# 3.0 even has real lambda functions, and a lot of new stuff like LINQ that originates from functional programming languages!)

---------------------------------------------------------------------------------------------------------------
-- TAKE 6: Using lambda functions to avoid all those dummy function names

randomPoint6 :: Int -> Int -> Int -> SeedIO Point3D
randomPoint6 width height depth = let return = (,) in
                             randomValue4 width |>= \x ->
                             randomValue4 height |>= \y ->
                             randomValue4 depth  |>= \z ->
                             return (Point3D x y z)

test6 = fst $ randomPoint6 volumeWidth volumeHeight volumeDepth initialSeed

-- Result: Point3D 84 94 64

-- Now we're getting somewhere! This is really close to the imperative version.
-- Congratulations, you just invented a monad for the Seed type...

-- Now the Haskell compiler makes it even easier to write, like this:
-- randomPoint8 width height depth = do 
--  x <- randomValue3 width
--  y <- randomValue3 height
--  z <- randomValue3 depth
--  return (Point3D x y z)
-- 
-- But that is just syntactic sugar. Note this code won't work because our SeedIO is not an instance of the prelude Monad class. More on that at the end.
--
-- Now how does Haskell handle real input/output? After all, we just made some kind of monad on a Seed type, 
-- but that does not help us getting things done in the real world.
-- Well, actually it does. The Haskell compiler declares a special type, called RealWorld. The RealWorld represents your computer's hardware.
-- Every function that changes something in your computer takes a RealWorld as input, and returns (a, RealWorld) as output.
-- But the difference is that you can't grab the RealWorld. After all, you can't make a copy of it! 
-- For more details, see http://haskell.org/haskellwiki/IO_inside

-- Now Haskell developers like abstraction a lot. So a monad in Haskell is more abstract.

---------------------------------------------------------------------------------------------------------------
-- TAKE 8: Abstraction

-- Look at the function signature of
-- type SeedIO a = Seed -> (a, Seed)
-- (|>=) :: (SeedIO a) -> (a -> SeedIO b) -> (SeedIO b)
--
-- The first thing to notice, is that we should generalize the Seed to any type, so

newtype GenericIO s a = GIO (s -> (a,s))

genericCombine :: (GenericIO s a) -> (a -> GenericIO s b) -> (GenericIO s b)
genericCombine (GIO f1) ff2 = GIO (\seed0 -> 
                                   let 
                                     (value1,seed1) = f1 seed0
                                     GIO f2 = ff2 value1
                                     (value2,seed2) = f2 seed1
                                   in
                                     (value2,seed2)
                                  )

genericReturn value = GIO (\seed -> (value,seed))

-- but even that is not general enough, because putting the (value,state) in a pair and assuming this is done by a function is still a restriction.
--
-- To make the concept fully abstract, we must generalize that also, and general concepts are always placed in a type class:

class MyMonad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fa >> ffb = fa >>= (\_ -> ffb)  -- _ is a wildcard, meaning "whatever, I don't need this value"

-- For example, our Seed instance would become
instance MyMonad (GenericIO Seed) where
  (>>=) = genericCombine
  return = genericReturn

-- But ofcourse, that's allready done in the prelude, which contains instances of Monads for the Maybe type (once something is Nothing, it remains Nothing), RealWorld ttype (encapsulating the real world), list type (doing the same as list comprehesions but then using a monadic way of writing). Furthermore many other monads exists in other libaries.

-- One last note, if you make your own monad instance, you should make sure your functions obey some monad laws, to make sure your code behaves like a real monad.
-- See http://haskell.org/haskellwiki/Monad_Laws for details