Today I learned that map can be implemented in terms of fold, i.e. if we have fold (reduce) we already have map.

The source code for foldr is:

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

So, we can do something like:

Prelude> foldr ((:).(+1)) [] [1,2,3]
[2,3,4]

Instead of using (+1) here, we can compose any function.

We can also do

Prelude> foldr (+) 0 [1,2,3]
6

The beauty of fold is that for a given data of type A, it can return data of type B.
While for map, for a given data of type A it will always return data of type A.

As we’ve shown, fold can return a list, a number, or anything else that we specify. But this is not the case with map.

The reason is that fold has a more generic morphism (catamorphism), and this is what makes it more powerful than map (homomorphism).

Here are some examples:

Prelude> foldr ((++)) [] ["hello", "world"]
"helloworld"

Prelude> foldr ((++).(words)) [] ["hello world", "I am fine"]
["hello","world","I","am","fine"]

And for something more complex:

parsePackets :: String -> [String]
parsePackets [] = []
parsePackets x = a:parsePackets b
  where
  (a,b) = splitAt 4 x

*Main> parsePackets "hey test 123 packets aligned in 4 bytes"
["hey ","test"," 123"," pac","kets"," ali","gned"," in ","4 by","tes"]

And here’s an analogous example with fold:

*Main> fst $ foldr (\x (chunks,partial) -> if length partial == 3 then
    ((x:partial):chunks,"") else (chunks,x:partial)) ([],[])
    "hey test 123 packets aligned in 4 bytes"
[" tes","t 12","3 pa","cket","s al","igne","d in"," 4 b","ytes"]
Prelude> foldr (\x (chunks, partial, all, cnt) -> if x == 3 || cnt == 3 then
    (x:chunks, partial, x:all, cnt+1) else (chunks, x:partial, x:all, cnt+1))
    ([],[],[],0) [1,2,3,4,5,6,7,3]
([3,5,3],[1,2,4,6,7],[1,2,3,4,5,6,7,3],8)

So we can notice that it is quite analogous to an imperative loop, i.e. we can look at fold’s accumulator as a local variable.

We can also implement a fixed point combinator using fold, proving that iterations can be reduced to folds:

fix f = foldr (\_ -> f) undefined (repeat undefined)

The undefined is just a gap-filler. The expression ‘repeat undefined’ generates a list of unbounded length. We don’t care about its elements, so anything will do. The fact that the list is infinite means that we get as many applications of the f parameter as we need. Note that, because the list is infinite, foldr will never reach the empty list, so it does not matter what value we give for the base case argument. Nonetheless, the type-checker requires that the argument has a polymorphic type, so it is quite convenient to use undefined here also.¹

So, now we can experiment some more with recursion:

Prelude> let fix f = foldr (\_ -> f) undefined (repeat undefined)
Prelude> let fact x = if x == 0 then 1 else x * fact (x-1)
Prelude> (fix (\x -> fact)) 4
24

1. Pope, Bernie. “Getting a Fix from the Right Fold“. The Monad.Reader (6): 5–16.

Today on #haskell@freenode I had an interesting discussion. It all started when I asked if the following statements make any sense:

Just 5 >>= \x -> Just $ x+1
what this does is basically unwraps Just, adds 1 to its value and returns Just. (*
return (Just 5) >>= \y -> y >>= \x -> Just $ x+1
what this does is basically unwraps the monadic value of Just 5, so we have Just 5.
So we have return (Just 5) >>= \y -> y == Just 5. Now (*) applies here.

Let’s check the types:

Prelude> :t Just 5
Just 5 :: Num a => Maybe a
Prelude> :t return (Just 5)
return (Just 5) :: (Monad m, Num a) => m (Maybe a)

So, basically, my question was (as can be seen from the statement above), how is it possible to convert m (Maybe a) to Maybe a? And, if m (m a) -> m a is possible, why isn’t m a -> a possible?

Well, m a -> a can be possible for some monads, for example for the Maybe monad, if we define it like:

fromJust (Just x) = x

But it’s not something that can be easily implemented for just any monad.

Now, as for why m (m a) -> m a is possible (and, in general m (m (… (m a) …)) -> m a), we can take a look at the definition of join, which is:

join x = x >>= id

So, if we try to do something like this:

Prelude> join $ Just (Just 5)
Just 5
Prelude> :t Just (Just 5)
Just (Just 5) :: Num a => Maybe (Maybe a)
Prelude> :t Just 5
Just 5 :: Num a => Maybe a
Prelude> join $ Just (Just 5)
Just 5
Prelude> :t join $ Just (Just 5)
join $ Just (Just 5) :: Num b => Maybe b

We can see basically how it “unboxes” stuff, and in my statement above I implicitly used join, which is the underlined part.

But how does it really work?

Well, if we look at the type of the bind operator:

Prelude> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

We can now start experimenting. What if we set a = m c?

We get m (m c) -> (m c -> m b) -> m b. Can we find such a function that satisfies this?

For (a -> m b) we can basically use the following lambda \x -> return x
So, for (m a -> m b), what if we omit return, and instead try \x -> x?

Prelude> Just (Just 5)
Just (Just 5)
Prelude> Just (Just 5) >>= \x -> x
Just 5
Prelude> :t Just (Just 5) >>= \x -> x
Just (Just 5) >>= \x -> x :: Num b => Maybe b
Prelude> :t Just (Just 5)
Just (Just 5) :: Num a => Maybe (Maybe a)
Prelude> :t (Just 5)
(Just 5) :: Num a => Maybe a

So, by using return, in the example of m a -> (a -> m b) -> m b we give back a “boxed” value, because we have \x -> return x where x = a, and return x = m a.

But, by not using return in the example of m (m a) -> (m a -> m b) -> m b we give back the same value that we receive, because we have \x -> x where x = m a, and the lambda expression will evaluate to m a.

So, with this we have shown how it’s possible to convert m (m a) to m b, and thus in general m (m (… (m a) …)) to m b.

Some interesting excerpts from the chat (please note that some parts are removed):

 the difference between "return $ Just 5" and "Just 5" is that the first is a monadic value
  (instance of Monad), and the second is only instance of data Maybe?
 BoR0: Maybe is an instance of Monad, the difference is this:
 > return $ Just 5 :: [Maybe Int]
  [Just 5]
 > return $ Just 5 :: Maybe (Maybe Int)
  Just (Just 5)
 BoR0: Maybe is an instance of Monad, "Monad m => m" says "any monad will work"
 BoR0: So "(>>=) :: Monad m => m a -> (a -> m b) -> m b" says it'll work for *any* Monad,
  even if if you don't know yet which one
 BoR0: There's no reason why a monad cannot contain another monad inside
 > return 5 :: [Int]
  [5]
 aha, okay. so return $ Just 5 is doubly "wrapped"
 BoR0: Yes
 BoR0: ^
 so if we have return x = Just x for Maybe monad, why doesn't return $ Just 5 give Just (Just 5)
  to us?
 BoR0: It will, if you ask for it
 > return (Just 5) :: Maybe (Maybe Int)
  Just (Just 5)
 but what does it do without specifying :: ... ?
 BoR0: Without the type signature it's polymorphic, it can be any Monad instance
 polymorphic! that clarifies it! great
 BoR0: Yes, all typeclasses are polymorphic, unless you specify a type OR type inference sees
  which type you wanted (actually, this is the only way, the type annotation just explicitly tell the
  type inference what you want :)
 I somewhere read that IO String can't be converted to String. but with this discussion I think
  the opposite, what is wrong now?
 so what held for Maybe monad (extracting x from Just x) doesn't necesarilly hold for IO monad?
 BoR0: For Maybe, you weren't really extracting. You were putting the value back into a Just
  at the end with return. All monadic expressions have a return at the end.
 BoR0: Yes, some *specific* monads may provide tools for extracting values (i.e. Maybe
  and list, for example). But the generic monad class does not provide a way to do that
 BoR0: Since IO doesn't provide a function to extract values, there's no way to get them out
 BoR0: monads allow you to go from an arbitrary number of applications of M to A to just M A

In Haskell, the Functor instance is only supposed to handle the mapping between objects, under the following rules:

1. Identity (fmap id = id)
2. Composition fmap f . fmap f = fmap (f o g)

So, if we want to declare a Functor instance over some type, that’s all we need to care about.
Functors are nothing more than that (to handle fmap for some actual type). The type definition of fmap is:

fmap :: Functor f => (a -> b) -> f a -> f b

So, from this we can see that the first parameter is a morphism, and the second parameter is the actual object. So, for instance, we can have:

fmap floor [1.5, 2.5, 3.5]

And we can see how our list “morphs” from a list with doubles to a list with integers!

Prelude> :t [1.5, 2.5, 3.5]
[1.5, 2.5, 3.5] :: Fractional t => [t]
Prelude> :t [1, 2, 3]
[1, 2, 3] :: Num t => [t]
Prelude> :t fmap floor [1.5, 2.5, 3.5]
fmap floor [1.5, 2.5, 3.5] :: Integral b => [b]

Another interesting thing to have a look at is the instance for ((->) r), which is defined as:

instance Functor ((->) r) where
    fmap f g = (\x -> f (g x))

Now, by having this definition, and that of fmap’s, we can apply ((->) r) to fmap to get:

fmap :: Functor f -> (a -> b) (r -> a) (r -> b)
    fmap f g = (\x -> f (g x))  

So, with this we can see that we can apply fmap to functions too!

Prelude> fmap (* 123) succ 3
492
Prelude> fmap (* 100) (\x -> x + 1) 123
12400

And, for some more theory (if you care), Wikipedia states that Functors are morphisms, and for morphisms:

In many fields of mathematics, morphism refers to a structure-preserving mapping from one mathematical structure to another. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms are functions; in linear algebra, linear transformations; in group theory, group homomorphisms; in topology, continuous functions, and so on.
In category theory, morphism is a broadly similar idea, but somewhat more abstract: the mathematical objects involved need not be sets, and the relationship between them may be something more general than a map.

We have last’ defined like:

last' [x] = x
last' (x:xs) = last' xs (*)

Base case: A list of one element is equal to that element itself.

Inductive step: Assume that last’ (x:xs) returns the last element of the list.
Then, if last’ (x:xs) holds, last’ (y:x:xs) must also hold.

We must show that it holds for y:x:xs.

Set zs = x:xs and obtain:
last’ (y:zs) = (*) = last’ zs = last’ (x:xs) = inductive assumption = last element of the list

So the recursion chops elements from beginning until it reaches one element, which will be the last element from our list.

The Probably Monad is same as the Maybe Monad, so this is how I had it defined:

data Probably x = Nope | Kinda x deriving (Show)

instance Monad Probably where
    Kinda x >>= f = f x
    Nope >>= f = Nope
    return = Kinda

add x y = x >>= (\x -> y >>= (\y -> return (x + y)))
-- Example: add (add (Kinda 1) (Kinda 2)) (Kinda 4)

Proof:

1. Left identity:
return a >>= f ≡ f a
“return a” by definition is “Kinda a”, and so the bind operator is defined as “Kinda a >>= f ≡ f a”.
So with these two definitions, we have shown that “return a >>= f ≡ f a”.

2. Right identity:
m >>= return ≡ m
If we let m equal “Kinda n”, then we have “Kinda n >>= return ≡ Kinda n”, but by definition of the binding operator,
we have that “Kinda n >>= return = return n”, and so “return n”. So, by definition of return, we have “Kinda n”, which is m.

3. Associativity:
(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)
If we let m equal “Kinda n”, then we have:
LHS: (Kinda n >>= f) >>= g ≡ (f n) >>= g
RHS: Kinda n >>= (\x -> f x >>= g) ≡ (\x -> f x >>= g) n ≡ f n >>= g