Haskell : Class 1
« Paradigmes et langages non classiques 2014
module Cours1 where
-- Github: samueltardieu
-- Bitbucket: rfc1149
-- Mail: email@example.com
-- Somee base types: Int, Integer, Char, Bool, Fractional, Unit
-- Since we redefine some standard data types and operators,
-- we need to mask them by explicitly importing the Prelude.
-- Otherwise, the Prelude would be automatically imported with
-- all its content.
import Prelude hiding (length, const, flip, Maybe(..), fmap, Functor,
($), Applicative(..), pure, (<*>), zipWith)
-- We define a new function which takes an Int and returns an Int.
-- We would not have to specify the type, but here we are willing
-- to restrict it.
increment :: Int -> Int
increment x = x + 1
-- Implicit type declaration.
increment' x = x + 1
-- Illustration of the if/then/else construct.
incrementifnon0 x = if x == 0
else x + 1
-- Recursive implementation of length using if/then/else.
length :: [a] -> Int
length l = if null l
else 1 + length (tail l)
-- Recursive implementation of length using pattern matching.
-- Note the use of the "dontcare" (_) which means that we are
-- not interested in naming the value since we will not use it.
-- We also use the "cons" operator ":" which builds a list from
-- its head and its tail, and can also be used for pattern matching.
length' :: [a] -> Int
length'  = 0
length' (_ : xs) = 1 + length' xs
-- Illustration of case/of which uses explicitly required pattern.
length'' :: [a] -> Int
length'' l = case l of
 -> 0
(_ : xs) -> 1 + length'' xs
-- This function takes a string and *never* returns an int, since it
-- calls error.
myfunc :: String -> Int
myfunc = error
-- This function also takes a string and also never returns an int, since
-- it loops indefinitely.
myfunc' :: String -> Int
myfunc' s = myfunc' s
-- This function has the same signature as "id", but takes forever to return.
myfakeid :: a -> a
myfakeid x = myfakeid x
-- This function has the same signature as "id", but returns with an error.
myfakeid' :: a -> a
myfakeid' x = error "I don't want to"
-- The "const" builtin function discards its second argument.
const :: a -> b -> a
const x _ = x
-- "flip" is useful to reverse the order of application.
flip :: (a -> b -> c) -> b -> a -> c
flip f y x = f x y
-- "second" discards its first element.
second :: a -> b -> b
second = flip const
-- Alternate implementation of "second". It works because "second a b"
-- is then extended into "const id a b". "const id _" is "id", so
-- the expression is really "id b" which is "b".
second' :: a -> b -> b
second' = const id
-- (.) is the "dot" operator to combine functions.
(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)
-- We define an algebraic data type which can either represent a
-- valid value (Just x) or no value (Nothing). We request the
-- automatic derivation from the Show typeclass: if the a type
-- belongs to the Show typeclass itself, we will be a member of it
-- as well using a predefined printing scheme (print the name of
-- the constructor, then the value).
data Maybe a = Just a | Nothing
-- "f" is a "Functor" if we can apply functions within "f a" objects
-- by the way of "fmap".
class Functor f where
fmap :: (a -> b) -> f a -> f b
-- Maybe is a functor, as we know how to apply the function if we have
-- a content (Just x), or it we have none (just do nothing in this case).
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)
-- Lists are functors too, you just have to apply the function to every
-- element of the list, that is… map!
instance Functor  where
fmap = map
-- Shortcut for infix notation.
(<$>) :: (Functor f) => (a -> b) -> f a -> f b
(<$>) = fmap
infixl 0 <$>
-- Shortcut for separating lengthy lines with less parentheses.
-- Writing "f x $ g y $ h z" is similar to "f x (g y (h z))".
($) :: (a -> b) -> a -> b
f $ x = f x
infixr 0 $
-- Binary tree type
data Tree a = Empty | Branch (Tree a) a (Tree a)
-- The tree is a functor, just apply the function to every value stored
-- in the tree.
instance Functor Tree where
fmap f Empty = Empty
fmap f (Branch left x right) = Branch (f <$> left) (f x) (f <$> right)
-- Demo tree to avoid retyping it every time. Not every interesting though.
tree = Branch (Branch Empty 3 (Branch Empty 4 Empty)) 17 (Branch Empty 8 Empty)
-- An applicative lets you apply a wrapped function onto a wrapped value.
class Applicative a where
pure :: x -> a x
(<*>) :: a (x -> y) -> a x -> a y
infixl 0 <*>
-- Maybe is an applicative: if there is no function, apply none and return
-- Nothing, ditto for the value. Otherwise, just do it.
instance Applicative Maybe where
pure = Just
_ <*> Nothing = Nothing
Nothing <*> _ = Nothing
(Just f) <*> (Just x) = Just $ f x
-- Lists are applicative. Here we have two alternatives: either apply every
-- function to every value (à-la cartesian product), or apply the first function
-- to the first value, the second function to the second value, and so on (and
-- stop as soon as one of both lists is empty).
instance Applicative  where
pure x = [ x ]
-- lf <*> lx = [f(x) | f <- lf, x <- lx]
lf <*> lx = zipWith ($) lf lx
-- Redefinition of (+) operator restricted to small integers.
plus :: Int -> Int -> Int
plus = (+)
-- Combine two lists using a combination function. The first element of
-- one list will be combined through the function with the first element
-- of the other, and so on. It stops when either list is empty.
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _  _ = 
zipWith _ _  = 
zipWith f (l : ls) (r : rs) = f l r : zipWith f ls rs