Given these definitions:
(.) :: (b -> c) -> (a -> b) -> a -> c
map :: (a -> b) -> [a] -> [b]
head :: [a] -> a

Find the type of (map . head)

1. (f . g) x = f (g x)
(map . head) x = map (head x)

2. If we set
x :: [a -> b]
then we have
head x :: a -> b

3. \x -> map (head x) :: [a -> b] -> [a] -> [b]
=>
map . head :: [a -> b] -> [a] -> [b]

Let’s now try to find a senseful definition of [a -> b] -> [a] -> [b] by using hole-driven approach (inspired by http://www.youtube.com/watch?v=52VsgyexS8Q):

In this example we are using a silent hole (i.e. undefined). We are also writing the types of each argument (xs and ys)

{-# LANGUAGE ScopedTypeVariables #-}

f :: forall a b. [a -> b] -> [a] -> [b]
f xs ys = undefined
    where
    _ = xs :: [a -> b]
    _ = ys :: [a]

It’s compiling. But it does nothing.

Let’s try to do the same with a noisy hole:

data Hole = Hole

f :: forall a b. [a -> b] -> [a] -> [b]
f xs ys = Hole
    where
    _ = xs :: [a -> b]
    _ = ys :: [a]

We get this error:
Couldn’t match expected type `[b]’ with actual type `Hole’

How do we get from Hole to [b]? We have xs :: [a -> b]. What if instead we tried map?

f :: forall a b. [a -> b] -> [a] -> [b]
f xs ys = map Hole Hole
    where
    _ = xs :: [a -> b]
    _ = ys :: [a]

We now get these errors:
Couldn’t match expected type `a0 -> b’ with actual type `Hole’
Couldn’t match expected type `[a0]’ with actual type `Hole’

The second hole is obviously just ys:

f :: forall a b. [a -> b] -> [a] -> [b]
f xs ys = map Hole ys
    where
    _ = xs :: [a -> b]
    _ = ys :: [a]

Now we get:
Couldn’t match expected type `a -> b’ with actual type `Hole’

What if we try to use just xs instead of Hole?

Couldn’t match expected type `a -> b’ with actual type `[a -> b]’

Now it wants just x, not xs.

One way to get to that is to use (head xs)

f :: forall a b. [a -> b] -> [a] -> [b]
f xs ys = map (head xs) ys
    where
    _ = xs :: [a -> b]
    _ = ys :: [a]

This makes it happy.

Conclusion:
The function of type [a -> b] -> [a] -> [b] is not unique, because we could use something else for map instead of just (head xs).

Bonus:
id’ :: forall a. a -> a
id’ x = Hole
    where
    _ = x :: a

Couldn’t match expected type `a’ with actual type `Hole’

id’ x = x

Today I was again playing with folds, but this time implementing them in PHP.
So, consider the list [a, b, c]:
foldr f z [a,b,c] = a `f` (b `f` (c `f` z))
foldl f z [a,b,c] = (((a `f` b) `f` c) `f` z) = z `f` (c `f` (a `f` b))

Note the bolded parts of foldr and foldl. They look pretty same, just that the elements are kind of reversed (e.g. (0 – 1 – 2 – 3) against (3 – 2 – 1 – 0)).

Now consider we use array_reduce in PHP like this:

<?php
var_dump(array_reduce(array(1,2,3), function($x, $y) { return $x - $y; } ));

This will print “-6” as a result. And in Haskell:

Prelude> foldl (-) 0 [1,2,3]
-6

So it turns out we’re using a left fold. What can we do to make it a right fold?
What if we try something like

<?php
var_dump(array_reduce(array(1,2,3), function($x, $y) { return $y - $x; } ));

This one will print “2” as a result. Haskell says:

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

And in Haskell we can also do something like

Prelude> let f x y = y - x
Prelude> foldr f 0 [1,2,3]
-6

So, it’s interesting to play around with associativity of binary operators 🙂
But we don’t want to do it in a “hacky” way by changing the operands in the function. So we want foldr.
Here’s the full PHP code with foldr and foldl implemented:

<?php
interface iBinaryOperator {
    public function calc($x, $y);
}

function foldr(iBinaryOperator $f, $z, array $xs) {
    try {
        $x = array_shift($xs);
        if ($x == null) {
            return $z;
        }
        return $f->calc($x, foldr($f, $z, $xs));
    } catch (Exception $e) {
        return "error";
    }
}

// Foldl is tail recursive
function foldl(iBinaryOperator $f, $z, array $xs) {
    try {
        $x = array_shift($xs);
        if ($x == null) {
            return $z;
        }
        return foldl($f, $f->calc($z, $x), $xs);
    } catch (Exception $e) {
        return "error";
    }
}

class Subtraction implements iBinaryOperator {
    public function calc($x, $y) {
        if (gettype($x) != "integer" || gettype($y) != "integer") {
            throw new Exception("MathException");
        }
        return $x - $y;
    }
/*
    public function partial_calc($x) {
        if (gettype($x) != "integer") {
            throw new Exception("MathException");
        }
        return function ($y) use ($x) {
            if (gettype($y) != "integer") {
                throw new Exception("MathException");
            }
            return $x - $y;
        };
    }
*/
}

$x = new Subtraction();
var_dump(foldr($x, 0, array(1,2,3)));
var_dump(foldl($x, 0, array(1,2,3)));

/*
> php test.php
int(2)
int(-6)
*/

Today we’ll play around with the following task:

Write a program that will receive a number N as an input, and that then will do additional N reads and print them out.

So first, let’s see how we can do this with a static number of times, say 3:

*Main> (readLn :: IO Int) >>= \x -> return $ x : []
1
[1]

*Main> (readLn :: IO Int) >>= \x -> (readLn :: IO Int) >>= \y -> return $ x : y : []
1
2
[1,2]
*Main> (readLn :: IO Int) >>= \x -> (readLn :: IO Int) >>= \y -> (readLn :: IO Int) >>=
  \z -> return $ x : y : z : []
1
2
3
[1,2,3]
*Main>

So what we need, is a function that will take a number as an input, and spit list of IO Ints as an output.
There are 2 ways to do this, and we’ll do both and then discuss the difference between them.

pn :: Int -> [IO Int]
pn' :: Int -> IO [Int]

What pn does, is returns a list of IO actions that need to be executed (which we can execute with sequence for example).
pn’ on the other hand, returns an IO action of list of numbers.
So we can view pn’ as one IO action that returns a list of numbers, and pn as a list of IO actions that return a number. Pretty simple!

Let’s start with pn. To cover the base case, we say that pn = 0 will return an empty list of actions. Note that [] is [IO Int] here, not [Int].

pn 0 = []

For the inductive step, we store the *read a number using readLn* action in a list (but not execute it), and then append that action to the list. Note that x is IO Int here, not Int.

pn n = do
-- No need for explicit signature here because Haskell already knows this by the fn signature
  let x = readLn :: IO Int
  x : pn (n - 1)

Now, to execute this, we can do:

*Main> sequence $ pn 3
1
2
3
[1,2,3]
*Main>

And what is sequence?

*Main> :t sequence
sequence :: Monad m => [m a] -> m [a]
sequence []     = return []
sequence (x:xs) = do v <- x; vs <- sequence xs; return (v:vs)
*Main>

So, sequence takes a list of monads (IO actions in this case), executes each one of them and returns their result *combined*.
pn’ is the same implementation as pn, but with sequence _within_ it so that we don’t have to call sequence each time.

pn' :: Int -> IO [Int]
pn' 0 = return []
pn' n = do
  x <- readLn
  xs <- pn' (n - 1)
  return $ x : xs

For the base case, we need a monadic empty list, that is:

*Main> :t return
return :: Monad m => a -> m a
*Main> :t (return []) :: IO [Int]
(return []) :: IO [Int] :: IO [Int]

For the inductive step, we are reading a number into x, i.e. executing the read action with <- (in contrast to =). Note that x is Int here, not IO Int.
Then, we recursively call pn’ to read for more numbers, and store those executed reads in xs. Note that xs is [Int] here.
After that, we return x:xs in order to get a IO [Int] instead of [Int].
We can now call it like:

*Main> pn' 3
1
2
3
[1,2,3]
*Main>

Let’s try to unwrap this call:

test :: IO [Int]
test = do
  x' <- readLn
  xs' <- do
    x'' <- readLn
    xs'' <- do
      x''' <- readLn
      xs''' <- return []
      return $ x''' : xs'''
    return $ x'' : xs''
  return $ x' : xs'

And that’s how it works. Or, we can rewrite everything as:

Prelude> let pn'' n = sequence $ take n $ repeat (readLn :: IO Int)
Prelude> pn'' 5
1
2
3
4
5
[1,2,3,4,5]
Prelude>

But it’s worth knowing what it does behind the scenes 🙂
We can now extend this function to accept an additional parameter (function), that will do something to the read value:

pn''' :: Int -> (Int -> Int) -> IO [Int]
pn''' 0 _ = return []
pn''' n f = do
  x <- readLn
  xs <- pn'' (n - 1) f
  return $ (f x) : xs

And call it like:

*Main> pn''' 5 succ
1
2
3
4
5
[2,3,4,5,6]
*Main>

Today I was playing around with Haskell and Monoids, and here’s what I came up with:

import Data.Monoid

data Vector = Vector (Int, Int) deriving (Show)
newtype SumVector = SumVector Vector deriving (Show)
newtype ProductVector = ProductVector Vector deriving (Show)

instance Monoid (SumVector) where
    mempty = SumVector $ Vector (0, 0)
    SumVector (Vector (a, b)) `mappend` SumVector (Vector (c, d)) = SumVector $ Vector (a+c, b+d)

instance Monoid (ProductVector) where
    mempty = ProductVector $ Vector (1, 1)
    ProductVector (Vector (a, b)) `mappend` ProductVector (Vector (c, d)) = ProductVector $ Vector (a*c, b*d)

What I was interested in, what is the difference between newtype and data? Since when I replaced newtype with data, the code worked as expected.
Here’s what I got as an answer:

 what is the main difference between data and newtype?
 Bor0: newtype has the same runtime representation as the underlying type
 data can do sum types (using |) and multi-element records
 you'd use newtype for performance reasons, when it is possible to do so
 also, you can use GeneralizedNewtypeDeriving to pull existing instances into your new type
 e.g., suppose you have data Foobar { ... } and instance ToJSON Foobar
 then you can do newtype Baz = Baz Foobar deriving (ToJSON)
 you can't do that with data Baz = Baz Foobar