MapFold OR Set Phasers to Fun

"Back to our brother of England."
-- Shakespeare, Henry V
Act II, Scene IV, Line 115.1

One of the things I love about functional programming is you can tell a lot about how a function works by just looking at its type signature.  In F# 4.0 there is a new function to work with collections, here is it type signature:

('State -> 'T -> 'U * 'State) -> 'State -> C<'T> -> C<'U> * 'State

What do you think it does?

That's right this is a MapFold.  Looking at its full definition we see the following:

let mapFold<'T,'State,'Result> 
  (f:'State -> 'T -> 'Result * 'State) acc list =

How does this work?

Looking at F#'s unit tests we see the following test name:

let ``mapFold works like map + fold`` () =

MapFold works like a map with a fold to maintain state.  I know what you are thinking maintaining state is bad, that's why functional programming is easier to reason about.  This is very true, but this is not a mutable state, this is an evolving state.

Let us look at an example, the Coin Changer kata:



The Coin Changer kata simulates one of those machines which give you back coins at a store.  It takes a list of coin values and the amount of change to be given.

The Coin Changer kata is interesting since it has two things going on at the same time: 1) state and 2) list processing.  In the Coin Changer kata you must maintain the amount of change you have left to give along with the amount of each coin to be given back.  An example would be 99 cents with an US register, you would get back 3 quarters, 2 dimes, 0 nickels, and 4 pennies.

How would this example of 99 cents with an US register work with MapFold?

changeFor [25; 10; 5; 1] 99

We'll use s to hold the state, r to hold the result, and x to hold the current coin value we are looking at .

Processing the first value: x = 25, s = 99, r = [] resulting in s = 24, r = [3]
Second value: x = 10, s = 24, r = [3] resulting in s = 4, r = [3; 2]
Third: x = 5, s = 4, r = [3; 2] resulting in s = 4, r = [3; 2; 0]
Last: x = 1, s = 4, r = [3; 2; 0] resulting in s = 0, r = [3; 2; 0; 4]

There you have it, step-by-step through the Coin Changer kata using MapFold.

Guess what the source code to MapFold looks for the most part like what we just experienced.  Here it is:



We see that it loops through each member of the collection, applying the function given against the state and current member.  Once there are no more members it returns a tuple of the result along with the state.  For the Coin Changer kata we do not care about the state (maybe we could use it verify that we have 0 cents) so we just drop it and get the result using fst.

There you have it the Coin Changer kata and MapFold seem to be made for each other.

AutoFixture for the Win

"What have I kept back?"
-- Shakespeare, Antony and Cleopatra
Act V, Scene II, Line 147.2

Anyone who has paired with me while working in C# knows that I am addicted to AutoFixture.  Now I do not try to add it to everything that I am working, but usually it finds its way into whatever I am working on.  Why?  Simply put, using AutoFixture allows me to focus on the task at hand.

Here is a quick example:



In this example I am implementing the higher order function Map using the higher order function Fold (see my other post if this interested you).

What do you not see in the tests?  The setting up of the test data.

Why?  It is not important to the task at hand.  We do not need it to test the behavior of Map.  Map takes a collection and a function and applies the function against every member of the collection producing a new collection.  What we want to verify is the applies part, which only requires a collection and a function, the actual members of the collection (and the function) do not matter for this verification.

Staying focus on the task at hand is the power of a test fixture and having someone else implement the test fixture for you is even better.  Using AutoFixture with xUnit you really do not need to think about setting up test data at all and that is good thing.

Showing Map Distributes Over Functional Composition OR Fun With Clojure

"Here by the cheeks I'll drag thee up and down."
-- Shakespeare, Henry VI Part 1
Act I, Scene III, Line 51

I love to try things out for myself.  Whenever I am trying to understand idea I need to show myself that the idea is valid.  Sometimes I will just accept something, but if I really want to understand it I will show myself that it makes sense.

While rereading Dr. Hutton's paper "A tutorial on the universality and expressiveness of fold", I came back across the following statement, "the map operator distributes over function composition".  Being the kind of person which likes to show things to myself I figured I'd show myself this idea in Clojure as part of my daily kata.



Looking at the code above we see the following:

• map f · map g = map (f · g)
• r/map f · r/map g = r/map (f · g)
• reduction f · reduction g = reduction (f · g)

So what does this give us?  Having this property we are allowed to improve the performance of our code by composing a series of transformation against a collection to a single transformation of the collection dragged through a series of composed functions.  In fact this is the whole idea behind streams.

Taken straight from Raoul-Gabriel Urma's article in Java Magazine, "[i]n a nutshell, collections are about data and streams are about computations."  Thinking about processing as a series of computation we see how we can naturally think about composing our computations together and then drag the data through using a higher order function like map to preform the series of transformations in one pass.

Folding into Map

"I have forgot the map."
-- Shakespeare, Henry IV Part I
Act III, Scene I, Line 5

Map

Map is the first of the big three Higher Order Function we will looking at Folding using Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", as a guide.  The idea of a Map is simple, you have a collection which you wish to apply some translation function against every member of the collection.

We can look at a few simple examples, the first of which would be the identity function.

 Next we can look at a constant function which maps turtle for any value given to it.

Last we can look at a function which shifts everything given to it.

All of this these functions have something in common, they all apply a function against every single member of the collection they are given, thus the resulting collection is the exact same size as the collection given to it.

We can now look at how we would implement Map using a Fold.  We see that Dr. Hutton gives Map the following definition:

map :: (α → β) → ([α] → [β])
map f = fold (λx xs → f x : xs) [ ]

Folding a Map we'll need a collection to seed with then we just apply the given function against each member concatenating it with the seed.

(similar to Reverse from last time)

Let us look at an example of upper casing Mike.

First Memoize has nothing and X has M.

Second Memoize has M and X has i.

Third time Memoize has MI and X has k.

Finally Memoize has MIK and X has e.

Giving the final result of MIKE.  Now let us look at some code examples.

Clojure

In Clojure we use the reduce function to Fold.  We give the reduce a seed of an empty collection and use conj to join applying the function given with the resulting collection.

C#

With C# we use the aggregate LINQ function to Fold.  We give the aggregate a List and add the result of applying each member of the given collection against the function we are mapping with.

ECMAScript 2015

Using ECMAScript 2015 (aka JavaScript), we use lodash's foldl to Fold.  We give the foldl an empty array and push the result of applying the function given against the member we are mapping against.

To End All

There you have it by folding with an empty collection and applying the given function against each member adding the result against the seed and you have a Map.

Examples of Map as a Series of Applying a Function -- in Clojure and kind of in C#.

"It is now apparent?"
-- Shakespeare, Measure for Measure
Act IV, Scene II, Line 135

Every now and then you read something and think, that is exactly what I have been thinking to myself but could not find the words.  Such an experience happen to myself this week.

I was reading Clojure Programming by Chas Emerick, Brian Carper, and Christophe Grand and found exactly how I have been thinking about the higher order function map but have not been able to express in words properly (it is on page 62 in the first edition).

map f [a b c] can be expressed as [(f a) (f b) (f c)]

Likewise map f [a b c] [x y z] can be expressed as [(f a x) (f b y) (f c z)] and so on ...

So what would this look like in code?

Glad you asked.



We see that in Clojure we can get exactly what we are looking for.  As a comparison we fins that in C# using the Zip we can get fairly close.

Reducing Map to Reduce OR All You Need is Fold

"That would reduce these bloody days again"
-- Shakespeare, Richard III
Act V, Scene V, Line 36

Intro

Have you heard the tale of the madman who came running into the town late at night, screaming that all you need is fold?

In Graham Hutton's paper "A tutorial on the universality and expressiveness of fold" it is shown that we can reduce recursive functions into a definition using fold.  Let's take a look reducing map to a fold.

(O-the tale of the madman is about me and not Dr. Hutton.)

Map

Map goes by a few different names, to those who speak Clojure, Haskell, or Underscore.js it goes by the name Map, to those which speak C# it goes by the name Select, those who speak C++ call it Transform, ... we could go on like this for a bit.

The point is that idea of the higher order function Map goes by different names in different language but performs the same function of taking a collection and applying a function against each member and placing it into the resulting collection.

The easiest example that actual does something is to apply an increment function with a Map.  Looking above we see that when we Map the increment function against a collection with the members of 1, 2, 3, 4 we get a resulting collection with the members of 2, 3, 4, 5.

In Clojure and C# it would look like this:

Fold

Fold goes by a few different names too, to those that speak Clojure or Underscore.js it goes by the name Reduce, to those which speak C# it is known as Aggregate, in Haskell it is known as Fold, in C++ it goes by the name Accumulate, ... we could go on like this for a while.  Again the point is that these names are all for the same idea of the higher order function Fold.

A Fold takes a collection and applies one function against each member of the collection and an accumulated result (also known as a memorize).

A very simple example of Fold would be summing.

We see in the image above that we are taking the collection 1, 2, 3, 4 and summing it up to the value of 10.  We do this by taking member 1 and the seed value of 0 and adding them together to get 1.  Next, we take the accumulated value of 1 and add the next member 2 to it giving us 3.  Then, we take the accumulated value of 3 and the member 3 add them and get 6.  Last, we take the accumulated value of 6 and the member of 4 giving us the final result of 10.

In Clojure and C# this would look like the following:

Mapping Map to Fold

... and birds go tweet, what is the point?  Glad you asked, we see with both Map and Fold some similarities.

1. applying a function against each member of a collection
2. building a resulting collection

Let's look at the first Map example again.  We see that we applying a function against each member of a collection and are accumulating a resulting collection, this sounds very similar to Fold.

In fact I would say that if we had an empty collection in which we accumulated the results of applying the function against the members of the collection we would have the same functionality.  That was a lot of words lets have some code.

In Clojure and C# we would have the following:

We see that both Map and the Fold give the exact same result.  In both the Clojure and C# code we see that we need an initial empty collection to store the resulting collection in and place the result of applying the function against a member into the resulting collection (using conj in Clojure and Add in C#).  For the C# code since we are using a List to accumulated the resulting collection instead of an array we need to reshape the resulting collection using the ToArray method.

By looking at this simple example we see that we can reduce Map to a Fold and thus all we need is Fold.  :)

Maps, Filters, and Folding ... Oh My! OR Yet Another Blog on Higher Order Functions

"Ay me! I see the ruin of my house.
The tiger now hath seized the gentle hind;
Insulting tyranny begins to jut

Upon the innocent and aweless throne.

Welcome destruction, blood, and massacre!
I see, as in a map, the end of all."
-- Shakespeare, Richard III
Act II, Scene IV, Lines 49-54

This is taken from my presentation called, "Maps, Filters, and Folding.  Oh my!" given at the Chicago Code Camp on April 27th, 2013.

f ◦ g

By higher order functions, we are talking about functions that take functions.  In other words we are talking about f ◦ g.

Mapping

Our first higher order function is f : A → B, called the mapping function.

In a mapping function everything in A has a value that it maps to through the function f to B.  Thus we can write f : A → B.

Mapping example - Identity

The identity function takes a value and maps it to the value given.  In other words it does nothing.

C#

var x = new List{1, 2, 3};

var numbers = from number in x
              select number;

F#

let x = [1; 2; 3]

let numbers = List.map (fun n -> n) x

OR

let x = [1; 2; 3]

let numbers = x |> List.map id

Haskell

map (\x -> x) [1, 2, 3]

OR

[x | x <- 2="" 3="" font="">

OR

 map id [1, 2, 3]

C

int* mapIdentity(int* list, int length) {

  int result[length];

  int i;

  for (i = 0; i < length; i++) {

    result[i] = list[i];

  }

  return result;

}

Mapping example - Turtles All the Way Down

Stephen Hawkings in a Brief History of Time gives us the following story:

A well-known scientist once gave a public lecture on astronomy. He described how the earth orbits around the sun and how the sun, in turn, orbits around the center of a vast collection of stars called our galaxy. At the end of the lecture, a little old lady at the back of the room got up and said: "What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise." The scientist gave a superior smile before replying, "What is the tortoise standing on?" "You're very clever, young man, very clever," said the old lady. "But it's turtles all the way down!"

If you want to create a function, which would describe a world in which everything is a Turtle you could use the following.

C#

var x = new List{1, 2, 3};

var numbers = 
  x.Select(t => "turtle");

F#

[1; 2; 3] |> List.map (fun _ -> "turtle")

Haskell

map (\_ -> "turtle") [1, 2, 3]

Mapping example - Shift Letters

Suetonius in The Twelve Caesars gives use the following about Julius Caesar:

If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others.

If we wanted to create a simple shifting function we could use the following.

C#

var caesar = 

  String.Concat(

    "DOG".Select(

      c => (char)(c + 13)));

F#

"DOG" 

  |> List.ofSeq

  |> List.map (fun c -> char(int c + 13))

  |> List.toArray

  |> (fun s -> System.String s)

Haskell

map (\c -> chr (ord c + 13)) "DOG"

Filtering

Our second higher order function is f : A → if (f(A)) then B, called filtering.

In filtering, not everything in A which goes through the function f has a value in B.  Thus we say that f filters A into B or f : A → if (f(A)) then B.

Filtering example - Odds only

Say we want a function which will only let Odd values into a club.  We could use the following as a bouncer.

C#

var x = new List{1, 2, 3};

var odd = x.Where(

            (a) => a % 2 == 1);

F#

[1; 2; 3] |> List.filter (fun x -> x % 2 = 1)

Haskell

filter (\x -> mod x 2 == 1) [1, 2, 3]

OR

filter odd [1, 2, 3]

Filtering example - Strings longer than 7

Say you want a function which will only let strings that are greater than 7 in length.

C#

var x = new List{

  "Scarecrow",

  "Tin Man",

  "Cowardly Lion"};

var moreThanSeven = 

  x.Where((a) => a.Length > 7);

F#

["Scarecrow"; "Tin Man"; "Cowardly Lion"]

  |> List.filter (fun x -> String.length x > 7)

Haskell

filter (\x -> length x > 7) 

  ["Scarecrow", "Tin Man", "Cowardly Lion"]

Filtering example - Divisors of 6

In number theory it is common to want to know if some is a divisor of a number.

C#

var x = 

  new List{1, 2, 3, 4, 5};

var divisor = 

  x.Where((a) => 6 % a == 0);

F#

[1..5] |> List.filter (fun x -> 6 % x = 0)

Haskell

filter (\x -> mod 6 x == 0) [1..5]

Folding

Our third and finial higher order function is folding.  Folding is when you have a set of values and you run them through a function f and get one value out of the function, f : A → a.  Max, sum, average, ... are all examples of folding.

Folding example - Sum

A common problem with a set of number is finding the total, this is also called summing.

Since addition is associative, it does not matter if we fold from the left or from the right.  If we were doing subtracts, it would matter.  5 - 2 = 3, but 2 - 5 = -3.

C#

var x = new List{1, 2, 3};

var s = x.Sum();

F#

[1; 2; 3] |> List.fold (fun acc x -> acc + x) 0

OR

[1; 2; 3] |> List.sum

Haskell

foldl (\acc x -> acc + x) 0 [1, 2, 3]

OR

sum [1, 2, 3]

Folding example - Counting

It is funny once you get into really high mathematics you find that a lot the same problems that you study earlier, come up again with fancier names and more abstract ideas.  Combinatorics is a branch of mathematics which is concerned with grouping and counting items.  We can use folding to create a counting function.

C#

var x = new List{1, 2, 3};

var c = x.Count();

F#

[1; 2; 3] |> List.fold (fun acc _ -> acc + 1) 0

OR

[1; 2; 3] |> List.length

Haskell

foldl (\acc _ -> acc + 1) 0 [1, 2, 3]

OR

length [1, 2, 3]

Folding example - Min

It is quite a common problem to want to find the minimum value of a given set.  Again, we can use a folding function to solve this problem.

C#

var x = new List{1, 2, 3};

var m = x.Min();

F#

[1; 2; 3] |> List.fold (

        fun m x -> if m > x then x else m)

      System.Int32.MaxValue

OR

[1; 2; 3] |> List.min

Haskell

foldr1 (\m x -> if m > x then x else m) [1, 2, 3]

OR

minimum [1, 2, 3]

The rest of the presentation has been covered in the following previous blog post:

• Finding Perfect Numbers
• Counting Letter Occurrence
• Finding Islands of Data

Don't Mind the Gap

"That I might sleep out this great gap of time

My Antony is away."
-- Shakespeare's Antony and Cleopatra
Act I, Scene V, Lines 5-6

A very common problem with data sets is missing data.  It is such a common problem that we have well know patterns to identify missing data.

How to Find Data Gaps

A data gap is when data should be found either in some type of order or range or ... but is not.  Such as trade data for a security, the security should have some activity everyday, so if there are dates missing and open, close, high, and low then there is a data gap.

In the data set above, we see that 7, 8, 13, and 14 are missing.  In order to find what is missing we need to sort, remove duplicate records, group the data by a range id, and then find the min and max for the range id.

Given the algorithm above we can solve it with the following steps.

Step 1: sort

[1..5] @ [11..13] @ [33..40]

  |> List.sort

> val it : int list =

  [1; 2; 3; 4; 5; 11; 12; 13; 33; 34; 35; 36; 37; 38; 39; 40]

Step 2: dedup

[1..5] @ [11..13] @ [33..40]

  |> Seq.distinct

> val it : seq = seq [1; 2; 3; 4; ...]

Step 3: assign group ids

[1..5] @ [11..13] @ [33..40]

  |> Seq.mapi(fun i x -> (x, x - i))

> val it : seq = seq [(1, 1); (2, 1); (3, 1); (4, 1); ...]

Step 4: group

seq [(1, 1); (2, 1); (3, 1); (4, 1)]

  |> Seq.groupBy snd

> val it : seq> =

  seq [(1, seq [(1, 1); (2, 1); (3, 1); (4, 1)])]

Step 5: find group's min and max

seq [(1, seq [(1, 1); (2, 1); (3, 1); (4, 1)])]

  |> Seq.map (fun (k, v) -> (fst (Seq.min v), fst (Seq.max v)))

> val it : seq = seq [(1, 4)]

Finding Data Gaps with F# (tryfsharp)

let gapper x =

  x

    |> List.sort

    |> Seq.distinct

    |> Seq.mapi

      (fun i x -> (x, x - i))

    |> Seq.groupBy snd

    |> Seq.map

      (fun (k, v) -> 

        (fst (Seq.min v),

         fst (Seq.max v)))

    |> List.ofSeq

Examples

gapper ([1..5] @ [11..13] @ [33..40] @ [20] @ [2..5] @ [2]);;

> val it : (int * int) list = [(1, 5); (11, 13); (20, 20); (33, 40)]

gapper ([1..5] @ [2..9] @ [2..5] @ [2] @ [10..13] @ [102..110]);;

> val it : (int * int) list = [(1, 13); (102, 110)]

I blogged about this problem before in how to Find Islands of Data using T-SQL after reading about the problem in Itzik Ben-Gan's book High-Performance T-SQL Using Windowing Functions (which is really good).  

Finding Data Gaps with T-SQL (SQL Fiddle)

SELECT DISTINCT

   MIN(col1) OVER(PARTITION BY groupid) AS start_range

  ,MAX(col1) OVER(PARTITION BY groupid) AS end_range

  FROM (

    SELECT 

       col1

      ,col1 - ROW_NUMBER() OVER(ORDER BY col1) AS groupid

      FROM dbo.t1

  ) AS x

;

On CPS Part 1

"O, many
Have broke their backs with laying manors on 'em
For this great journey. What did this vanity
But minister communication of
A most poor issue?"
-- Shakespeare
Henry VIII
Act I, Scene I
Lines 83-87

I've moved further along in my journey of functional programming.  I find myself in a densely wooded forest of colossal pine trees.  The smell of juniper fills the air, bring with it memories of winters gone by.  This forest is where continuation lives.

Continuation-passing style is programming with no return, literally there is no return statement when you use continuation-passing style (CPS).  Instead what you do is pass in the function which you would like the function you are calling to return its result to.

Simple CPS example

Say you have function called f and you want f to take what ever value you give it and pass it to another function you give it that well call k.

In F# (on tryfsharp)

let f = fun x k -> k(x)


> val f : x:'a -> k:('a -> 'b) -> 'b


What we do is pass a function through k which takes one argument, like this:


f 5 (printfn "%d")



> 5
val it : unit = ()

FizzBuzz example

Lets do my favorite kata FizzBuzz using CPS.

First we make the fizzer and buzzer.

In F# (on tryfsharp)

let xzz n (w:string) =

    fun x ->
      match x with
      | x when x % n = 0 -> Some(w)
      | _ -> None
  
  let fizz x = (xzz 3 "Fizz") x
  
  let buzz x = (xzz 5 "Buzz") x

> val xzz : n:int -> w:string -> x:int -> string option
> val fizz : x:int -> string option
> val buzz : x:int -> string option


We now have a fizzer and a buzzer which will return string options.

Now let's make the fizzBuzzer using these functions.  We'll also use List.choose so we'll have either ["Fizz"], ["Buzz"], ["Fizz";"Buzz"], or [] as a result of applying fizzer and buzzer against the numerical input.  We'll then use List.reduce to concat the possible ["Fizz";"Buzz"] result.

In F# (on tryfsharp)

let fizzBuzzer n k =
  match [fizz; buzz] |> List.choose (fun f -> f n) with
  | [] -> k(n.ToString())
  | x -> k(x |> List.reduce (+))



> val fizzBuzzer : n:int -> k:(string -> 'a) -> 'a


Note this uses the fizz and buzz from before.

In order to consume this CPS version of FizzBuzz you could do the following:


 let p = (fun x -> printfn "%s" x);;
  fizzBuzzer 2 p;;
  fizzBuzzer 9 p;;
  fizzBuzzer 10 p;;
  fizzBuzzer 30 p;;

> val p : x:string -> unit

> 2
val it : unit = ()
> Fizz
val it : unit = ()
> Buzz
val it : unit = ()
> FizzBuzz
val it : unit = ()

The great thing about CPS with TDD is that you can pass what you are testing its own test case (see Full FizzBuzz example below).  I'll have more on CPS, once I wrap my head around it fully.  I am working on understanding one of the best responses I've seen on StackOverflow.

Full Fizz Buzz example in F# (with FsUnit):

open NUnit.Framework

open FsUnit

let xzz n (w:string) =

  fun x ->

    match x with

    | x when x % n = 0 -> Some(w)

    | _ -> None

let fizz x = (xzz 3 "Fizz") x

let buzz x = (xzz 5 "Buzz") x

let fizzBuzzer n k =

  match [fizz; buzz] |> List.choose (fun f -> f n) with

  | [] -> k(n.ToString())

  | x -> k(x |> List.reduce (+))

[<Test>]

let ``Validate that 2 can be Done`` () =

  (xzz 2 "Done") 2 |> should equal (Some("Done"))

[<Test>]

let ``Validate that 2 can not match`` () =

  (xzz 42 "Wrong") 2 |> should equal None

[<Test>]

let ``Validate that 6 is Fizz`` () =

  fizz 6 |> should equal (Some("Fizz"))

[<Test>]

let ``Validate that 5 is not Fizz`` () =

  fizz 5 |> should equal None

[<Test>]

let ``Validate that 10 is Buzz`` () =

  buzz 10 |> should equal (Some("Buzz"))

[<Test>]

let ``Validate that 3 is not Buzz`` () =

  buzz 3 |> should equal None

[<Test>]

let ``Validate that 2 is 2`` () =

  fizzBuzzer 2 id |> should equal "2"

[<Test>]

let ``Validate that k can be assert`` () =

  fizzBuzzer 2 (fun x -> Assert.AreEqual("2", x))

[<Test>]

let ``Validate that k can be shoulded`` () =

  fizzBuzzer 2 (fun x -> should equal "2" x)

[<Test>]

let ``Validate that 9 is Fizz`` () =

  fizzBuzzer 9 (fun x -> should equal "Fizz" x)

[<Test>]

let ``Validate that 20 is Buzz`` () =

  fizzBuzzer 20 (fun x -> should equal "Buzz" x)

[<Test>]

let ``Validate that 30 is FizzBuzz`` () =

  fizzBuzzer 30 (fun x -> should equal "FizzBuzz" x)

On Mapping

"You must be the change you wish to see in the world."
-- Mahatma Gandhi

Working in an industry with large amounts of data and having a need to apply changes to this data, I often find myself needing to apply functions against members of a data set.  In the world of functional programming this applying functions against a data set takes place on the island of higher order function on the beach known as mapping.

A mapping does exactly what we need to do when we want to apply a function against a data set, it takes each member of the data set and applies the function against it giving a resulting data set which has the results applied against it.

Here are a few simple examples:

Case 0: Identity function

The identity function does nothing, it literally takes the input and passes it as the output, applying nothing against the input.

Both Haskell and F# have a built in function called id which is the identity function.

In Haskell (on codepad):

map id [1 .. 4]

=> [1,2,3,4]

In F# (on tryfsharp):

List.map id [1 .. 4];;

val it : int list = [1; 2; 3; 4]

Case 1: Increment by 1

The "Hello World" for mapping (that actually does something) would be the increment by 1.  The function would add 1 to each input yielding an output with values that are one greater than the input.

Both Haskell and F# allow for the applying of the addition operator (+) in a mapping,

In Haskell (on codepad):

map (+1) [1 .. 4]

=> [2,3,4,5]

In F# (on tryfsharp):

List.map ((+) 1) [1 .. 4];;

val it : int list = [2; 3; 4; 5]

Case 2: Obtain first element of a tuple (or any complex data type)

One use that might not be obvious at first but is really useful is to map a certain part of a data set.  Mapping a certain value of a data set can allow for other higher order functions to apply to element later on in a chain.  Lets say you have a list of tuples and would like to get the first value of each one.

Both Haskell and F# have a first function which returns the first value in a tuple.

In Haskell (on codepad):

map fst [(1,2), (2,3), (3,5), (4,2)]

=> [1,2,3,4]

In F# (on tryfsharp):

List.map fst [(1,2); (2,3); (3,5); (4,2)];;

val it : int list = [1; 2; 3; 4]

There you have it a few simple examples of mapping in Haskell and F#.