Examples of functional programs 'writing themselves' via type analysis

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

Bottom

Ok, this is not a super great example, but 'ok', and maybe will help get some other ideas going...

Suppose

f : unit -> 'a

That is, I want to write a function that I pass no arguments, and it returns a value of any type. What does the function do?

Note that I can't just return 'new obj()', as the type signature is generic, e.g. I can call it with f<int> and get back an int, for example.

Give up? Here's the most common possibility:

let rec f() = f()

It's an infinite loop. It never returns, so the return type is irrelevant. You can do this is many languages.

In a language like Haskell, 'exceptions' would be 'effects' governed by the type system, but in F#:

let f() = failwith "kaboom!"

is another example. If we throw an exception, once again, the return type does not matter.

Finally, implementation details of many runtimes allow for "default initialization" of any type, so e.g. in F#

let f() = Unchecked.defaultof<'a>

is ok too. I think maybe these are the only three possible implementations in F#.

Answer 2

Identity

Suppose I want to write a function f

f : 'a -> 'a

In F#, I think the only interesting implementation is:

let f x = x

The identity function above is the natural implementation for most any language.

And as in my other answer, you could also loop, throw, or default-initialize. But those are less interesting. Those "backdoors" kinda throw a wrench in the works of all these 'type derived' computations, so it may be best to ignore them.

The key in this one is, for all types 'a, you know nothing about the type, so the only way to 'get' a real object of that type is for someone to already give you one. So the identity function is the only reasonable implementation of that signature.

Answer 3

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.

Answer 4

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 5

Map

A couple more to consider...

om2 : ('a -> 'b) -> 'a option -> 'b option

The only interesting implementation is Option.map:

let om f xo =
    match xo with
    | None -> None
    | Some x -> Some(f x)

Now I could have written

let om (f:'a -> 'b) (xo:'a option) : 'b option =
    None

and just ignore both arguments and always return None. But that's not interesting. Someone's passing us all these useful arguments, surely we're meant to do something with them, right? So the first implementation above is the only one (again modulo the trivialities mentioned in other answers, due to looping, effects, etc.).

Similarly

lm : ('a -> 'b) -> 'a list -> 'b list

You'd be hard pressed to write anything other than List.map. You could always return the empty list, but that'd ignore both arguments. You could write

let lm f xs =
    match xs with
    | [] -> []
    | h::t -> [f h]

but again it seems weird for someone to pass this whole useful list and we ignore all of it except the first element. If you assume you're 'meant' to 'use' all the data, List.map is the obvious implementation. (Though nothing is stopping you from mapping twice or thrice and returning a new list that 2x or 3x as long as the original. Once again, there is a sense/aesthetic in which there is a 'simplest obvious' implementation that matches the type signature and consume the data passed in, and this 'obvious' implementation is the useful one. When you see the signature

('a -> 'b) -> 'a list -> 'b list

you just think 'List.map', no one even considers all the other theoretically possible implementations, because the others are all pretty much just nonsense in the context of software engineering.)

I don't know if any of this is convincing or not.

Answer 6

(a -> b) -> [a] -> [b]

The type practically is the implementation.

Answer 7

Silly starter example, following on from my update:

Give that I have a List<string>, how can I get to Array<float>, with the current functions (with one thrown in for obfuscation!)

fn1: string -> float
fn2: List<'a> -> Array<'a>
fn3: Array<'a> -> List<'a>
fn4: ('a -> 'b) -> Array<'a> -> Array<'b>

Well, let's see:

//Start at the beginning
let input:List<string> = myData
// the only thing that I can apply to this is a 
//     function that starts with List<something>, so...

input |> fn2 // List<'a> -> Array<'b>, so now I have Array<string>
// At this point, it looks like I have no choice but fn3, but that takes 
//   me back where I came from. However, there is an Array<'a> in 
//   the middle of fn4.

input |> fn2 |> fn4 ???
//oops, I need something else here, a function that goes ('a -> 'b).
//   But all my functions go ('a -> 'b)! However, in this case my 'a is a string,
//   so that limits my choice to fn1:

input |> fn2 |> fn4 fn1 // so here I have Array<float> yoohoo!

//recapitulate with the real function names
let convert input = 
    input |> Array.ofList    //List<string> -> Array<string>
          |> Array.map float //Array<string> -> (string -> float) -> Array<float>

Answer 8

Another answer is from Wes Dyer, who mentions this precise phenomenen when explaining Select for IObservable. The signature being:

IObservable<U> Select<T, U>(this IObservable<T> source, Func<T, U> selector)

I'll let you work it out... (I'm quite pleased with myself, I managed to write my own Select and Where)

Answer 9

See

http://stackoverflow.com/questions/3548532/f-best-way-to-condense-a-list-of-option-type-down-to-only-elements-that-are-not

Briefly, the goal is to solve for f here:

> [Some 4; None; Some 2; None] |> f;; 
val it : int list = [4; 2] 

(a function which projects out just the Some values in a list). My commentary on the solution (which is List.choose id) was

Just let the types guide you. You want a function that contains option in its signature but returns just a list (not a list of options). Look though the API, and there's only one such function, choose, and now you're already 95% the way there.