Examples of functional programs 'writing themselves' via type analysis [closed]

Question

(Background: I've been thinking about doing a presentation on F# and functional programming. From experience, I think that the 'wow' factor of pattern matching and type inference is not necessarily enough to counteract the 'help!' factor of "where are my curly brackets and semicolons, my code is going to fall off the edge!". Which got me thinking about the real wow factor - for me - which is 1) that if it compiles, generally that means that it works and 2) that you can often infer the implementation from the types)

There is a video on Channel9 with Brian Beckman and Erik Meijer where they mentioned how implementation sometimes just 'falls out' of the type signature of a function. I've also experienced this in the past, but can't come up with a good example that would be sufficiently simple to present to someone with no previous functional experience.

Has anyone got a good example to share? (it doesn't have to be in F#)

UPDATE

If it's any help, I think we need to think about this differently: The actual puzzle is as follows:

I have some data with a given type, I want to transform it to a different type, and I have a set of functions with given signaures.

This is the 'lego' that you have to plug together.

Answer 1

Start with the simplest possible function: identity :: 'a -> 'a. How many implementations can you think of? If you give me an a, there's only one thing I can do with it to give you back an a. I give you back the same a that you gave me, so:

let id x = x

Same goes for pairs. fst :: ('a,'b) -> 'a. How many ways can you implement that? How about snd :: ('a, 'b) -> 'b? Only one implementation can possibly exist for each.

Analogously, taking the head and tail of a list falls right out of fst and snd. If head :: 'a list -> a and tail :: 'a list -> 'a list, and an 'a list is just a pair ('a, 'a list) (or the empty list), then it's obvious that to satisfy the types, you return first and second part of the list, respectively.

One more example to do with higher-order functions: compose :: ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b. There's only one implementation, and it falls right out of the types. You're given a c and two functions. What can you do with the c? Well, you can apply (c -> a). What can you then do with the a? The only thing you can do is apply (a -> b), and voila, you have satisfied the type.

let compose f g x = f (g x)

Answer 2

Pipe

Here's a third example...

Suppose I want to write a function

p : 'a -> ('a -> 'b) -> 'b

That is, I take as arguments a value of type 'a, and a function that takes an 'a and returns a 'b. And my result should be a 'b. Well, again, modulo infinite loops and exceptions and default-initialization, there's only one implementation:

let p x f = f x

'p' may not look too useful until you realize it's the pipeline operator (|>).

Hm, I feel like these examples so far are underwhelming.