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]
= 1 : zipWith (*) facts [1..]
facts
-- Implementing a factorial function becomes trivial.
= (facts !!)
fact
-- Let's try this (slooow) recursive version of the Fibonacci sequence.
0 = 1
fibo 1 = 1
fibo = fibo (n-1) + fibo (n-2)
fibo n
-- And let's do it with an elegant and much faster definition.
= 1 : 1 : zipWith (+) fibos (tail fibos)
fibos
-- Here we are.
= (fibos !!)
fibo'
-- We did the test with fathers, but I prefer the term parent.
= [("Daniel", "Jacques"), ("Jacques", "Toto"),
parents "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
= mzero
advlookup _ [] : xs) | a == k = (return v) `mplus` advlookup a xs
advlookup a ((k, v) | 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
= advlookup
lookup'
-- 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
= flip advlookup parents
parent
-- You can query for the grandparents the same way, by using >>= (bind) on
-- the parent in order to chain the calls.
= parent x >>= parent
grandparent x
-- You can go on forever!
= parent x >>= parent >>= parent
grandgrandparent x
-- 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 ()
= putStrLn
debug
-- echo and echo' are equivalent…
= getLine >>= (\s -> putStrLn (s ++ s))
echo
-- …thanks to the "do" notation
= do
echo' <- getLine
s putStrLn (s ++ s)
-- Let's print each line twice, …
= do
echo'' <- getLine
s putStrLn s
putStrLn s
-- … which is equivalent to this code.
= getLine >>= (\s -> putStrLn s >>= (\_ -> putStrLn s))
echo'''
-- Now, we print the reverse of strings entered by the user.
= do
loop <- getLine
s 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 ()
= Writer ((), x)
tell 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
0 = do
fact' "Computing fact 0"]
tell [return 1
= do
fact' n <- fact' (n-1)
t $ ["I just recursed for n == " ++ show n]
tell 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
= fst.runWriter
compute
-- Only give the logs: logs $ fact' 5
logs :: Writer w a -> w
= snd.runWriter
logs
-- Display the logs on standard output, one per line: displayLogs $ fact' 5
displayLogs :: Writer [String] a -> IO ()
= sequence_ $ map putStrLn $ logs m
displayLogs m
-- Note that displayLogs can also be written using mapM_:
-- displayLogs = mapM putStrLn . logs