Haskell : Class 2

« Paradigmes et langages non classiques 2014

module Cours2 where

import Control.Applicative
import Control.Monad
import Data.Monoid

-- Here, we define facts as an infinite list of factorials. Like a recursion,
-- you only have to give the initial value and explain how to go on from there.
facts :: [Integer]
facts = 1 : zipWith (*) facts [1..]

-- Implementing a factorial function becomes trivial.
fact = (facts !!)

-- Let's try this (slooow) recursive version of the Fibonacci sequence.
fibo 0 = 1
fibo 1 = 1
fibo n = fibo (n-1) + fibo (n-2)

-- And let's do it with an elegant and much faster definition.
fibos = 1 : 1 : zipWith (+) fibos (tail fibos)

-- Here we are.
fibo' = (fibos !!)

-- We did the test with fathers, but I prefer the term parent.
parents = [("Daniel", "Jacques"), ("Jacques", "Toto"),
           ("Toto", "Oldelaf"), ("Oldelaf", "Bison fute"),
           ("Marcel", "Giedre"), ("Marcel", "Daniel"),
           ("Giedre", "Jean"), ("Giedre", error "Giedre has no second parent")]

-- The standard lookup is too narrow: Eq a => a -> [(a, b)] -> Maybe b
-- It forces you to get one answer at most. Let's redefine another lookup
-- which lets you choose the kind of MonadPlus you want to store your result
-- into.
advlookup :: (MonadPlus m, Eq a) => a -> [(a, b)] -> m b
advlookup _ [] = mzero
advlookup a ((k, v) : xs) | a == k    = (return v) `mplus` advlookup a xs
                          | otherwise = advlookup a xs

-- We can check that we can get back the limited version by forcing the
-- types to be restricted to the same ones as lookup.
lookup' :: Eq a => a -> [(a, b)] -> Maybe b
lookup' = advlookup

-- Lookup one or several parents. You can coerce the result into a single result
-- by using (parent x :: Maybe String), or get all the results with (parent x :: [String]).
parent :: MonadPlus m => String -> m String
parent = flip advlookup parents

-- You can query for the grandparents the same way, by using >>= (bind) on
-- the parent in order to chain the calls.
grandparent x = parent x >>= parent


-- You can go on forever!
grandgrandparent x = parent x >>= parent >>= parent

-- The Monad typeclass looks like that (+ the >> operator which was not seen in class)
-- with instances for Maybe and lists.
--
-- class Monad m where
--   return :: a -> m a
--   fail :: String -> m a
--   (>>=) :: m a -> (a -> m b) -> m b
--   (>>) :: m a -> m b -> m b
--
--   fail = error
--   a >> b = a >>= (\_ -> b)
--
-- instance Monad Maybe where
--   return = Just
--   fail _ = Nothing
--   Nothing  >>= _ = Nothing
--   (Just x) >>= f = f x
--
-- instance Monad [] where
--   return x = [x]
--   fail _   = []
--   l >>= f  = concat [f(x) | x <- l]

-- IO operations all work in the IO monad
debug :: String -> IO ()
debug = putStrLn

-- echo and echo' are equivalent…
echo = getLine >>= (\s -> putStrLn (s ++ s))

-- …thanks to the "do" notation
echo' = do
  s <- getLine
  putStrLn (s ++ s)

-- Let's print each line twice, …
echo'' = do
  s <- getLine
  putStrLn s
  putStrLn s

-- … which is equivalent to this code.
echo''' = getLine >>= (\s -> putStrLn s >>= (\_ -> putStrLn s))

-- Now, we print the reverse of strings entered by the user.
loop = do
  s <- getLine
  putStrLn (reverse s)
  loop

-- The Writer monad depends on two types. a is the type of the data
-- stored into the monad, and w is the type of the additional information
-- (decoration) which is attached to the monad.
--
-- Its main principle is that computations will append previously existing
-- data with data provided by the function called by >>=. This is the role
-- of >>= too take care of appending all decoration data.

-- We also show the way of naming fields, and obtaining an accessor to them.
data Writer w a = Writer { runWriter :: (a, w) } deriving (Show)

-- A writer is a functor: the decoration is untouched by function application.
instance Functor (Writer w) where
  fmap f (Writer (a, w)) = Writer (f a, w)

-- A writer is an applicative: newer versions of GHC require this.
instance (Monoid w) => Applicative (Writer w) where
  pure = return
  (<*>) = ap

-- If w is a monoid (which can then start empty and gets appended to), then
-- (Writer w) is a monad which contains a value of type a (remember, Writer
-- has two types arguments, as in Writer w a).
instance (Monoid w) => Monad (Writer w) where
  -- return creates a new monad, with no decoration, just the value given by
  -- the user.
  return x = Writer $ (x, mempty)
  -- >>= calls the user provided function, takes the decoration out of the
  -- result and prepends it with the preexisting one.
  Writer (a, w) >>= f = let Writer (a', w') = f a
                        in Writer (a', w `mappend` w')

-- tell is the way to add some decoration. Using tell in the context of a Monad
-- will create a new writer with a content of () (unit) and the given decoration.
-- It will then be considered during subsequent bind calls.
tell :: w -> Writer w ()
tell x = Writer ((), x)

-- Let's write a factorial function which takes adds some decoration to the
-- computation. Without the "tell", that would be written as:
--
-- fact 0 = return 1
-- fact n = (*n) <$> fact (n-1)
--
-- Or as:
--
-- fact 0 = return 1
-- fact n = do
--   t <- fact (n-1)
--   return $ n * t
--
-- Here, we add some "tell" to give information about what is happening.
fact' :: Int -> Writer [String] Int
fact' 0 = do
  tell ["Computing fact 0"]
  return 1
fact' n = do
  t <- fact' (n-1)
  tell $ ["I just recursed for n == " ++ show n]
  return $ n * t

-- Write only the result of the computation, forgetting all about the decoration.
-- Use it as in: compute fact' 5
compute :: Writer w a -> a
compute = fst.runWriter

-- Only give the logs: logs $ fact' 5
logs :: Writer w a -> w
logs = snd.runWriter

-- Display the logs on standard output, one per line: displayLogs $ fact' 5
displayLogs :: Writer [String] a -> IO ()
displayLogs m = sequence_ $ map putStrLn $ logs m

-- Note that displayLogs can also be written using mapM_:
-- displayLogs = mapM putStrLn . logs