Sunday, April 26, 2009

Applicative functors: mapping a function to more than 3 lists

Hello

Here is a short post that illustrates the power of higher level functions.

Everybody knows the List.map function that applies an arbitrary function to a list, producing a new list.

#light

List.map (fun x -> 2*x) [1;2]
List.map takes a function of one argument but there also exist List.map2 and List.map3 that take, respectively, a function of 2 and 3 arguments.
List.map2(fun x y -> x+y) [1;2] [1;2]

List.map3 (fun x y z -> x+y+z) [1;2] [1;2] [1;2]
But how do we do if we need a function List.map4 or List.map5 ? The straightforward solution is to explicitly write these functions.

I will show that List.map3, List.map4 or even List.map45 are not needed and with the help of a little operator, we can get the same functionality by simple composition.

First, let's try to evaluate the expression:

List.map (fun x y -> x+y) [1;2]
We get the signature:
val it : (int -> int) list
A list of functions. Clearly, if we combined this list with a list of int (i.e. [3;4]) , making sure that each function is applied to its corresponding integer, we could obtain the same result as the expression:
List.map2 (fun x y -> x+y)  [1;2]  [3;4]
That is precisely what the operator <$> below does:
let (<$>) fctList list = List.map2 (fun fct elem -> fct elem) fctList list
Using both List.map and <$>, we can implement any mapping we want. I.e.
let r = List.map (fun x y z -> x+y+z) [1;2] <$> [1;2] <$> [1;2]
is equivalent to
List.map3 (fun x y z -> x+y+z) [1;2] [1;2] [1;2]
We can also, if we want, explicitly define the equivalent of List.map4
let map4 f l1 l2 l3 l4 = List.map f l1 <$> l2 <$> l3 <$> l4
This technique works also for other types than list. It works with sequence, array... In short it works with any type supporting a map like function.

In the litterature (and more specifically in Haskell) all the types that support a mapping function form the class of Functors.

The types that support both a mapping function and the operator <> belong to the class of gt; belong to the class of Applicative Functors.

Functional Reactive Programming in F# (4)

In this post, I will introduce events in FRP.

Remember, a FRP is used to model systems that have an evolution with respect to continuous time. However the way such a system computes its output(s) may be modified at discrete moments in time. To take a simple example, suppose we want to simulate a ball moving in one direction along a horizontal axis at constant speed. Suppose also that wa have an input device with two controls, the first control sets the velocity of the ball and the second is a button that, when pressed, changes the direction of the ball. Moreover, the ball is only allowed to move between 2 vertical walls. Each time the ball hits one of these walls, its velocity changes direction. This system behaves continuously until one of the three following events occur:

  • The user changes speed.
  • The user presses the velocity direction button.
  • The ball hits a wall.
The first two events are what I called external events. External events are generated from outside of the system. They do not depend on a particular state of the system. They can occur at any moment in time. The third event is not generated by an external source but occurs when the state of the system (here, the ball's position) satisfies some condidtions. I call such events internal events.

The goal of this post is to discuss such internal events.

Some let's start with our Behavior type and its run function.

#light


type Time = float

type 'a Beh  = Beh of (Time -> ('a * 'a Beh))

let rec run (Beh bf) l =
   match l with
   |[] -> []
   |h::t -> let (r, nb) = bf h
            r::(run nb t)
I will not propose to implement the above case with the ball and the walls since this is still a bit too complex for the moment and would hide some important concepts. That is why I prefer an simpler example of a colored Behavior that is white at the beginning of its life and becomes black after some time (namely 10 units of time - i.e seconds). As usual, let's start the "hard way" by manually coding all the logic. Helpful combinators will be derived from this first coding.
type Color = White|Black

// a constant Behavior that is always Black
let rec blackB = Beh (fun t -> (Black, blackB))

let rec colorB =
   let bf t =  if (t<10.0)
               then (White, colorB)
               else let rec blackB = Beh (fun t -> (Black, blackB))
                    (Black, blackB)
   Beh bf

Looking at colorB, it is easy to see that it stays the same, it is always White. When the time reaches 10 seconds, colorB transforms itself into blackB.
let s = Seq.to_list (seq { for x in 1 .. 15 -> (float) x})

let r = run colorB s
As always, the name of the game is to find abstractions (that is, combinators) to help us writing such event handling logic.

The next step is to move the event detection outside of the Behavior function. This is done by defining a cond function that returns None if time is less than 10 seconds and Some blackB when time is higher than or equal to 10 seconds.

The cond function acts as a sort of event generator for colorB.

Now, the Behavior function (bf) invoques cond and tests whether it returns None of Some newBehavior. If cond returns None, then the colorB Behaviors stays the same else colorB becomes the new Behavior returns by cond (newBehavior). We can ask ourselves what we have gained here. The main advantage is that the logic of producing the event is now separated from the handling of the event.

Moreover the handling of the event is always the same and does not depends on a particular event: If cond is None, then we do nothing special if cond is Some newBehavior then we replace the current Behavior by newBehavior.

let rec colorB =
   let cond t = if (t<10.0)
                then None
                else let rec blackB = Beh (fun t -> (Black, blackB))
                     Some blackB
   let bf t =  match cond t with
               |None -> (White, colorB)
               |Some (Beh newColorB) -> newColorB t
   Beh bf

let r = run colorB s
One more step. Looking at cond, we see that it only depends on time. There is no particular reason to keep it defined within the definition of colorB. It could be passed as a parameter.
// val createColor : (Time -> Color Beh option) -> Color Beh

let rec createColor cond =
   let bf t = match cond t with
              |None -> (White, createColor cond)
              |Some (Beh newColorB) -> newColorB t
   Beh bf

// val cond : float -> Color Beh option
let cond t = if (t<10.0)
           then None
           else let rec blackB = Beh (fun t -> (Black, blackB))
                Some blackB

let colorB = createColor cond

let r = run colorB s
The next step is more fundamental. The cond function depends on time. But we already have things that depends on time, namely Behaviors. So why cond could not be a Behavior? If fact, cond can well become a Behavior. One big advantage of this is that cond functions may have internal state, just like any Behavior.
// -- cond becomes a behavior

let rec condB =
   let bf t = if (t<10.0)
              then (None, condB)
              else let rec blackB = Beh (fun t -> (Black, blackB))
                   (Some blackB, condB)
   Beh bf

Adapting createColor is rather easy.

// val createColor : Color Beh option Beh -> Color Beh

let rec createColor (Beh condf) =
   let bf t = match condf t with
              |(None, ncond) -> (White, createColor ncond)
              |(Some (Beh newColorB), ncond) -> newColorB t
   Beh bf

let colorB = createColor condB

let r = run colorB s
It is still possible to increase the abstraction level. Up to now createColor explicitly depends on the value White. But taking a closer look to what we want, we can conclude that colorB follows the rules:
  • Before some time t0 (10 seconds here) colorB is equal to a constant Behavior whose value is White.
  • After that time, colorB should be equal to the Behavior blackB.
The switchB function captures the essence of what we want: switchB takes a Behavior as first argument and a condition Behavior as second. switchB returns a Behavior that is equal to its first argument until the condition Behavior returns some new Behavior. At this point, the initial Behavior is replaced by the new one.

// val switchB : 'a Beh -> 'a Beh option Beh -> 'a Beh

let rec switchB (Beh bfInit) (Beh condf) =
   let bf t = match condf t with
              |(None, ncond) -> let (rInit, nBInit) = bfInit t
                                (rInit, switchB nBInit ncond)
              |(Some (Beh newBehavior), ncond) -> newBehavior t
   Beh bf

let rec whiteB = Beh (fun t -> (White, whiteB))

let colorB = switchB whiteB condB

let r = run colorB s

In the switchB signature, a quite complex type appears: 'a Beh option Beh . For the sake of clarity and to better discriminate between Behaviors and Events, a specific type is introduced for events:
// definition of event

type 'a Event =  Evt of (Time -> ('a option  * 'a  Event))

And the switchB function now becomes:
// val switchB : 'a Beh -> 'a Beh Event -> 'a Beh

let rec switchB (Beh bfInit) (Evt condf) =
   let bf t = match condf t with
              |(None, ncond) -> let (rInit, nBInit) = bfInit t
                                (rInit, switchB nBInit ncond)
              |(Some (Beh newB), ncond) -> newB t
   Beh bf

Here we are. In a next post I will present combinators and types to create various Events.