\$ operator is an operator for function application. It has signature:
(\$) :: (a -> b) -> a -> b f \$ x = f x
At first it doesn't look like it does much, but it is actually defined as
infixr 0 meaning it is:
- An infix operator with right associativity
- Has the lowest precedence possible.
In contrast, normal function application is left associative and has the highest precedence possible. Practically, this means it can be used where you would otherwise have to use parentheses, to make code a lot cleaner. Some examples:
-- elem finds if an item x is contained in the list xs elem :: Eq a => a -> [a] -> Bool elem x xs = not (null (filter (==x) xs)) -- rewritten, without parentheses elem x xs = not \$ null \$ filter (==x) xs -- or using function composition (.) elem x = not . null . filter (==x)
Another example, shown along with a trace of it's reduction:
map (\$ 4) [even, odd] => (even $ 4) : map (\$ 4) [odd] => (even \$ 4) : (odd \$ 4) :  => True : (odd \$ 4) :  => True : False :  => [True, False]
It has already been shown how many examples of recursive functions can be rewritten with a
folding is a an example of a useful design pattern in functional programming.
Binary trees are recursive data structures, that can be recursively operated on (much like lists). The example below shows a simple definition of a binary tree along with some functions to operate on it.
-- our binary tree type data BinTree a = Leaf | Node (BinTree a) a (BinTree a) deriving Show -- simple recursive functions -- how big is the tree? size :: BinTree a -> Int size Leaf = 0 size Node (l _ r) = 1 + size l + size r -- is x contained within the tree? member:: Eq a => a -> BinTree a -> Bool member _ Leaf = False member x (Node l y r) = x == y || member x l || member x r -- what is the sum of all the Nums in the tree tsum :: Num a => BinTree a -> a tsum Leaf =0 tsum (Node l n r) = n + tsum l + tsum r
These are all recursive functions operating on a tree, and can be generalised by defining our own version of a fold for trees, dubbed
toldr. Note the similarities between
toldr :: (a -> b -> b) -> b -> BinTree a -> b toldr f z Leaf = z toldr f z (Node l x r) = f x (toldr f (toldr f z r) l) tsum :: Num a => BinTree a -> a tsum = toldr (+) 0 member :: Eq a => a -> BinTree a -> Bool member x = toldr (\y r -> x==y || r) False size :: BinTree a -> Int size = toldr(\_ r -> 1 + r) 0
This abstraction does actually exist in the standard libary, as a typeclass. A type can be an instance of
Foldable (like lists), which then allows
foldr to be used on it.
class Foldable t where foldr :: (a -> b -> b) -> b -> t a -> b -- for lists -- exists in prelude instance Foldable  where foldr f z  = z foldr f z (x:xs) = f x (foldr f z xs) -- for our bintree instance Foldable BinTree where foldr _ z Leaf = z foldr f z (Node l x r) = f x (foldr f (foldr f z r) l)
This instance of
BinTree can now be used to generalise our functions that operate on it:
sum :: (Foldable t, Num a) => t a -> t sum = foldr (+) 0 elem :: (Foldable t, Eq a) => a -> t a -> Bool elem x = foldr (\y r -> x==y || r) False length :: Foldable t => t a -> Int length = foldr (\_ r -> 1 + r) 0
These methods are actually part of the
Foldable typeclass, so when defining an instance of
Foldable on some type, you get them for free, and they are polymorphic over all foldable types.
Foldable is also a derivable typeclass using the language extension
-XDeriveFoldable, so all of this can be derived automatically.
Bringing back our
safediv function from previously:
data Maybe a = Nothing | Just a safediv :: Int -> Int -> Maybe Int safediv _ 0 = Nothing safediv x y = Just (x `div` y) divAndAdd :: Int -> Int -> Maybe Int divAndAdd x y = 5 + safediv x y -- doesn't work, type error -- using a case statement divAndAdd x y = case safediv x y of Nothing -> Nothing Just r -> Just (5+r) -- bit messy
The pattern of applying a function a value within a
Maybe can be generalise. Defining a function
pam to do this for us:
pam :: (a -> b) -> Maybe a -> Maybe b pam _ Nothing = Nothing pam f (Just x) = Just (f x) -- much nicer! divAndAdd :: Int -> Int -> Maybe Int divAndAdd x y = pam (5+) (safediv x y)
It would be nice if there was some way to generalise the pattern of applying a function to element(s) in a container. The
Functor typeclass does this for us. A type is a functor if we can apply a function to it. Lists are functors, as that is what the
map function does.
BinTrees are also functors.
class Functor f where fmap :: (a -> b) -> f a -> f b instance Functor  where fmap = map instance Functor Maybe where fmap f Nothing = Nothing fmap f (Just x) = Just (f x) instance Functor BinTree where fmap f (Leaf x) = Leaf (f x) fmap f (Node lr ) = Node (fmap f l) (fmap f r)
Functors can be thought of as "boxes", and when given a function, will apply it to the value in the box, and return the result in the same box. Some examples of definitions using functors:
-- increases all Ints in the "box" by 5 incByFive :: Functor f => f Int -> f Int incByFive = fmap (+5) -- applies the odd function to all Ints in the box odds :: Functor f => f Int -> f Bool odds = fmap odd -- redefining using fmap divAndAdd :: Functor f => Int -> Int -> Maybe Int divAndAdd x y = fmap (5+) (safediv x y)
Functor is also another typeclass that can be derived by GHC, using the
An operator that is essentially just an infix version of the
infixl 4 <\$> (<\$>) :: Functor f => (a -> b) -> f a -> f b (<\$>) = fmap fmap (replicate 6) (safediv 8 4) == replicate 6 <\$> safediv 8 4 => Just [2,2,2,2,2,2] -- redefining using <\$> divAndAdd :: Functor f => Int -> Int -> Maybe Int divAndAdd x y = (5+) <\$> (safediv x y)
There are certain laws that functors must obey for their properties to hold. A type
f is a functor if there exists a function
fmap :: (a-> b) -> f a -> f b , and the following laws hold for it:
fmap id = id
- If the values in the functor are mapped to themselves, the result will be an unmodified functor
fmap (f.g) = (fmap f) . (fmap g)
- The fusion law
- If two
fmaps are applied one after the other, the result must be the same as a single
fmapwhich applies the two functions in turn
- These laws imply that a data structure's "shape" does not change when