Infinite loops in Haskell

I have written about my performance problems with Haskell before.

Infinite loops in Haskell gives an example of some of the subtle "fun" that can be had.

Haskell monads

Some weeks ago, I spent a couple of days working through some Haskell with a colleague of mine. This is some of the stuff we went through.

1. Haskell exercises for beginners to get back in the swing of things.


2. Write implementations for:

   mflatten :: Maybe (Maybe a) -> Maybe a
   mmap     :: (a -> b) -> Maybe a -> Maybe b
   
   lFlatMap :: [] a -> (a -> [] b) -> [] b
   mFlatMap :: Maybe a -> (a -> Maybe b) -> Maybe b



3. Observe lFlatMap and mFlatMap can be written with the same pattern. How can we reduce the "duplication"?


4. Derive flatten from flatMap:

   class FlatMap f where
     flatMap :: f a -> (a -> f b) -> f b
   
   flatten' :: (FlatMap f) => f (f a) -> f a
   flatten' = error "todo"



5. Given pure:

   class Pure p where
     pure :: a -> p a

   and flatMap, derive map:

   map' :: (FlatMap f, Pure f) => f a -> (a -> b) -> f b
   map' t f = error "todo"



6. Let's give the combination of flatMap and pure a name, perhaps Monad:
   

   class Monad' m where
     flatMap :: m a -> (a -> m b) -> m b
     pure    :: a -> m a

   A diagram to describe the relationships between our functions so far:
   
   


7. Write the following functions:
   

   liftM0    :: (Monad' m) => a -> m a
   liftM1    :: (Monad' m) => (a -> b) -> m a -> m b
   liftM2    :: (Monad' m) => (a -> b -> c) -> m a -> m b -> m c
   liftM3    :: (Monad' m) => (a -> b -> c -> d) -> m a -> m b -> m c -> m d
   ap        :: (Monad' m) => m (a -> b) -> m a -> m b
   sequence' :: (Monad' m) => [m a] -> m [a]
   mapM'     :: (Monad' m) => (a -> m b) -> [a] -> m [b]

   
   Observe:
   
   • liftM0 and liftM1 are just pure and map respectively
   
   
   • liftMn for n >= 2 can be written as:
     
     
     
     • n x flatMap + pure
     
     
     • (n - 1) x flatMap + map
     
     
     • liftM(n - 1) + flatMap
     
     
     • liftM(n - 1) + ap
   
   
   • sequence' and mapM' can each be written in terms of the other


8. Finally, note the Monad laws.

Step 2 Notes
I found it natural to write:

lFlatMap xs f = concat $ map f xs

mFlatMap Nothing _  = Nothing
mFlatMap (Just x) f = f x

However, given the similar type signatures, I can instead write:

mFlatMap xs f = mflatten $ mmap f xs

Step 3 Notes
After some reflection I realised it is important is to ignore the function names and implementations. I had internalised the concept of map as a minor generalisation of List.map i.e. traversing across elements in a 'container' and applying the same function to each one, which didn't quite fit with Maybe.

The key is simply the function signatures. If I have some functions f and g, such that

f :: (a -> b) -> t a -> t b
g :: t (t b) -> t b

then I can automatically construct a function h

h :: t a -> (a -> t b) -> t b

where h is simply the composition of g with f and nothing more can be said about it.

It does not matter that f is called map for List and it is not helpful to compare implementations of f for two different types t, looking for similarities beyond the type signature.

For me this is a case where attaching a meaning to a name impeded the process of abstraction.

Groups in Haskell

sigfpe wrote an interesting post that includes implementations of a Group in Haskell, amongst other things I don't understand, such as vector spaces and Hopf algebras.

Australian government guarantees bank deposits

Last weekend the government announced that it is guaranteeing bank deposits for the next three years (Couriermail, ABC stories). This is interesting given the enormous profits the banks have made in recent years. Have they not put enough away for a rainy day? After all, they helped create the current mess.

While I don't want to lose any money I have deposited in the banks, I don't see it as appropriate for the government to use my tax dollars to help the banks profit. So before receiving one cent, the banks should deal with the consequences of their actions like any other business does - accept lower/no profit, cut costs (e.g. excessive executive salaries, exorbitant consulting fees), etc.

I am not an economist, anthropologist or sociologist, but perhaps there are bigger issues at play, such as the fractional-reserve banking system and Western society's (media-reinforced) consumer driven mentality.

Learn You a Haskell for Great Good!

When I was first learning Haskell I stumbled upon A Gentle Introduction to Haskell, Version 98, except that "gentle" seemed completely the wrong adjective. :-) I think Yet Another Haskell Tutorial was the most useful online tutorial I found at the time.

Now there is Learn You a Haskell for Great Good!, found via Just Testing. Looks like a good introduction for those of us who come from mainstream, imperative languages.

Thoughts about types

Types in programming languages define logical properties of a program in that language.

N.B. I am not talking about type annotations, i.e. the programmer may explicitly specifiy types or they may be inferred.

When a program successfully type checks, the execution of the type checker constitutes a proof of those logical properties w.r.t the program (assuming correct, consistent behaviour of the type checker itself).

If a program fails the type checker it implies that (as far as the type checker is concerned) there is ambiguity or logical inconsistency w.r.t to the program (again assuming no bugs in the type checker itself).

Partial functions subvert the type system and therefore undermine the value of the logical proof provided by the type checker. Apparently there is a relationship between this, Turing completeness and the Halting problem, although I don't understand that yet.

One of my goals over the summer is to work through Types and Programming Languages by Benjamin Pierce.

Zermelo and set theory

I am currently studying axiomatic set theory. In the process I came across Zermelo and Set Theory, which gives details about his work and interactions with other significant mathematicians.

While interesting, it unfortunately didn't help me when working out his proof for the Schroder-Bernstein Theorem in an assignment. :-)

Digital Camera

Given the shortlist from my requirements, I bought the Fujifilm FinePix F100fd. Tried it out at the Amberley Air Show on the weekend and am happy with the results so far. Some of the photos are here on Flickr.

On a side note, I also shot some video from our digital video camera and tried uploading that to Flickr as well, but after the Flickr processing the videos looked terrible (mind you my original footage was a bit dodgy to start with :-)). I guess I need to find a decent private/public video sharing site. Vimeo and Viddler look interesting.

Digital Camera Requirements

My wife and I have used an old digital camera (generously passed on from a friend when they upgraded) for some years now and the time has finally come to upgrade. So this is what I think we need in a camera:

1. Neither of us know much about photography so we need to be able to point-and-click and still get reasonably good quality images in different light conditions.


2. 5x optical zoom or greater.


3. Low response time between pressing the button and taking the photo.


4. Wider angle would be handy for those landscape or family photos.


5. Prefer AA batteries over lithium.


6. Viewfinder might be nice for outdoor shots when it is difficult to view the LCD.

I would like to spend no more than AUD $400. From reading reviews, I arrived at the following shortlist:

• Fujifilm FinePix F100fd
  Image quality scored well in reviews: DigitalCameraReview, Digital Camera Resource Page, cnet. Has a 5x optical zoom and and 28mm wide angle lens. No viewfinder and uses a lithium-ion battery. DigitalCameraReview thought this was a great camera for the point-and-click user.


• Panasonic Lumix DMC-FS20
  Image quality scored well in reviews: DigitalCameraReview, cnet, Steve's Digicams. Auto mode got a good rap. 4x optical zoom and 30mm wide angle lens. No viewfinder, although screen did well outside and has a lithium-ion battery. Cnet thought this was a great camera for the point-and-click user, but it would be a bit over budget.


• Sony Cyber-shot DSC-W150
  Image quality didn't seem to score quite as well as the previous cameras, although still good: DigitalCameraReview, Steve's Digicams. 5x optical zoom and 30mm wide angle lens. Small viewfinder and lithium-ion battery.