Interesting ideas - ahri/lazymanc.net GitHub Wiki

Functions as lookups

Functions are a generalisation of maps/dictionaries (and even lists of you consider the index to be a key!) and can be seen as "containers" (functors) for values.

IO as a series of instructions

IO a is a recipe to produce values of type a, which will be "cooked" only when evaluated via a program's main :: IO ().

Functors vs. function composition

A function whose type has been applied to another type, i.e. a -> b -> c (kind * -> *-> *) becomes Int -> b -> c (kind * -> *) which means we can write a Functor instance for it, making it mappable - this already exists in GHC.Base on ((->) r). For example:

> let f = (+2)
> :t f
f :: Num a => a -> a
> let g = fmap (*3) f
> g 5
21

That's interesting...

> (*3) . (+2) $ 5
21

And given that <$> is infix for fmap...

> (*3) `fmap` (+2) $ 5
21
> (*3) <$> (+2) $ 5
21

Swapping params for pointfree

f s x = s ++ show x
f s x = (++) s (show x) -- switch to using prefix notation
f = (. show) . (++)     -- reverse calls using a composition section (. firstCall)

Which way to fold?

The most natural definition is the left fold:

foldl :: (acc -> curr -> acc) -> acc -> [curr] -> acc
foldl _ acc []        = acc
foldl f acc (curr:xs) = foldl f (f acc curr) xs

While the right fold gives us a second, hidden, base case to end recursion:

foldr :: (curr -> acc -> acc) -> acc -> [curr] -> acc
foldr _ acc []        = acc
foldr f acc (curr:xs) = f curr (foldr f acc xs)

This second case is hidden in Haskell's lazy nature; take the function (&&)

(&&) :: Bool -> Bool -> Bool
(&&) True True = True
(&&) _ _       = False

If you try to evaluate False && undefined the runtime can pattern-match and arrive at the second definition (= False) just by evaluating the first argument to (&&), this means it doesn't have to evaluate the second one, and because Haskell is a lazy language, it won't. So in this case you can't get a runtime error as undefined is never evaluated.

Back to foldr; the hidden base case, then, is that if the function passed to foldr manages to return a value without evaluating the second argument, the recursion ends.

This makes foldr useful to work on infinite lists (or other infinite foldables of course), because your function can end the recursion, whereas in the case of foldl you lose control of recursion and an infinite structure will cause the runtime to stall.

foldl has a couple of downsides even on non-infinite structures; it is applied in reverse so if you're building a new list from another list you'll have to concatenate due to those semantics if order matters, also the accumulator it's building up ends up as a (potentially long) nest of thunks that have to be evaluated out, so they take up memory and will impact program performance in an unexpected way if that accumulator is only evaluated later. This is why foldl' exists in the Data.List package - to be used in preference to foldl as it strictly evaluates the accumulator and therefore the function, stopping thunks from building up.

So the guidance for which to use is:

foldl' if you know you need to traverse the whole structure and need to do so in the most efficient way possible
foldr if you have an infinite structure or you're generating a list - this is the implementation you should reach for

Covariance and contravariance in functors

First of all, remember that no function application is going on in the following description.

Covariant functors of type a take a function f of type a -> x, so if the functor contains a function g, the fmap definition will compose the two functions in order: f . g.

Contravariant functors of type a take a function f of type x -> a, so if the functor contains a function g, the fmap definition will compose the two functions in order: g . f.

In prose: you can control the order of execution through a choice of functor or cofunctor, where in normal functors, when mapping, the supplied function wraps the existing one sat in the structure, and in cofunctors, when contramapping, the supplied function ends up being wrapped by the existing one.

Functors

Mapping morphisms

If you have a category (type, data structure) and you provide a Functor instance for it, you're enabling people to write normal (understandable) functions and then use your fmap to promote (lift) them into your category.