tag:blogger.com,1999:blog-1527203170295638572024-03-08T17:19:14.281+01:00call/ccJ-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-152720317029563857.post-34938224877568537702011-10-25T08:23:00.003+02:002011-10-25T08:24:05.602+02:00C# Strangeness<pre class="source-code">
public void Test()
{
string aa = "\0";
string cc = "";
var r0 = aa == cc;
var r1 = aa.Equals(cc);
var r2 = cc.Equals(aa);
var r3 = aa.CompareTo(cc);
var r4 = cc.CompareTo(aa);
}
</pre>
<p>
Thanks to <a href="http://fscheck.codeplex.com/">FsCheck </a> for pinpointing this "feature".</p>
<br>J-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.com0tag:blogger.com,1999:blog-152720317029563857.post-39471515120431046582009-10-20T18:09:00.048+02:002009-10-21T10:10:03.433+02:00Stack Overflow in F# Sequences<span style="font-size:130%;"><span style="font-family:georgia;">Not so long ago, I ran into a curious problem while writing some F# sequence code.</span>
</span><p style="font-family:georgia;"><span style="font-size:130%;">
Let's consider a simple function that takes a list and produces a sequence of the reversed list.</span></p>
<pre class="source-code"><span style="font-size:100%;">let rec reverse l =
seq { match l with
|h::t -> yield! reverse t
yield h
|[] -> yield! Seq.empty
}</span></pre><span style="font-size:130%;">
<span style="font-family:georgia;">Now let's try to count the number of elements of a very large sequence.</span></span>
<span style="font-size:100%;">
</span><pre class="source-code"><span style="font-size:100%;">let ls = Seq.to_list (seq {for i in 1..10000000 -> i})
Seq.fold (fun acc _ -> acc+1) 1 (reverse ls)</span></pre>
<span style="font-size:130%;"><span style="font-family:georgia;">And here, what happen? We get a stack overflow. </span></span><span style="font-size:130%;"><span style="font-family:georgia;">
Maybe the beginning of an explanation lies in the definition of </span></span><span style="font-style: italic;font-family:georgia;font-size:130%;" >reverse</span><span style="font-size:130%;"><span style="font-family:georgia;">.</span>
<p>
<span style="font-family:georgia;">Looking at it, we can see that the recursive call</span>
</p></span><span style="font-size:100%;">
</span><pre class="source-code"><span style="font-size:100%;"> yield! reverse t</span>
</pre><span style="font-size:130%;">
<span style="font-family:georgia;">appears before yielding the current head of the list. So we have a recursive call that is not in tail position.
<p>
That explains the stack overflow.</p></span>
<span style="font-family:georgia;">A solution is to use continuation passing style to move the recursive call to a tail position.</span>
</span><span style="font-size:100%;">
</span><pre class="source-code"><span style="font-size:100%;">
let reverse l =
let k0 () = Seq.empty
let rec proc l kc =
seq { match l with
|h::t -> let kc' () = seq { yield h
yield! kc()
}
yield! (proc t kc')
|[] -> yield! kc ()
}
proc l k0
</span></pre><span style="font-size:130%;">
<span style="font-family:georgia;">Now it works!</span>
<span style="font-family:georgia;">
</span></span>J-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.com1tag:blogger.com,1999:blog-152720317029563857.post-52362415903421012512009-05-16T08:56:00.027+02:002009-05-18T12:59:57.013+02:00Implementing Equals in C#<p>
<span style="font-size:130%;"><span style="font-family:georgia;">In this post I present a way that, in my opinion, correctly implements equality between</span>
<span style="font-family:georgia;">objects. Or at least, correctly implements equality with respect to some specific objectives.</span>
<span style="font-family:georgia;">Indeed, there are many ways to write Equals(). But, each way targets some specific goals and I</span>
<span style="font-family:georgia;">do not believe that there is only one way to do it.</span>
<p>
<span style="font-family:georgia;">To start with, let's state what the objectives are in this case:</span></p></span></p><ul style="font-family:georgia;"><li><span style="font-size:130%;">Equality for immutable value objects.</span></li><li><span style="font-size:130%;">Two objects are equals iff they are of exactly the same class, independently of the type of the variable that holds them.</span></li><li><span style="font-size:130%;">Support inheritance and reuse comparison logic from base classes.</span></li><li><span style="font-size:130%;">Support the </span><span style="font-style: italic;font-size:130%;" >== </span><span style="font-size:130%;">operator.</span></li><li><span style="font-size:130%;">Reduce the programmer's workload as much as possible.</span></li></ul><span style="font-size:130%;"><span style="font-family:georgia;">The code is below:</span></span>
<pre class="source-code">
<!-- code formatted by http://manoli.net/csharpformat/ -->
<pre class="csharpcode">
<span class="kwrd">using</span> System;
<span class="kwrd">using</span> System.Collections.Generic;
<span class="kwrd">using</span> System.Linq;
<span class="kwrd">using</span> System.Text;
<span class="kwrd">namespace</span> Equal
{
<span class="kwrd">public</span> <span class="kwrd">class</span> Util
{
<span class="rem">// Returns true if a and b are both non null and are of exactly the same class</span>
<span class="kwrd">public</span> <span class="kwrd">static</span> <span class="kwrd">bool</span> AreSameClass(Object a, Object b)
{
<span class="kwrd">return</span> a != <span class="kwrd">null</span> && b != <span class="kwrd">null</span> && a.GetType().Equals(b.GetType());
}
}
<span class="kwrd">public</span> <span class="kwrd">class</span> A
{
<span class="kwrd">private</span> <span class="kwrd">int</span> a;
<span class="kwrd">public</span> A(<span class="kwrd">int</span> a)
{
<span class="kwrd">this</span>.a = a;
}
<span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">int</span> GetHashCode()
{
<span class="kwrd">return</span> a;
}
<span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">bool</span> Equals(<span class="kwrd">object</span> o)
{
<span class="kwrd">return</span> Util.AreSameClass(<span class="kwrd">this</span>, o) && <span class="kwrd">this</span>.EqualMembers((A)o);
}
<span class="kwrd">protected</span> <span class="kwrd">bool</span> EqualMembers(A o)
{
<span class="kwrd">return</span> a == o.a;
}
<span class="kwrd">public</span> <span class="kwrd">static</span> <span class="kwrd">bool</span> <span class="kwrd">operator</span> ==(A a, A b)
{
<span class="kwrd">return</span> <span class="kwrd">object</span>.Equals(a, b); <span class="rem">// handle cases where a or b is null.</span>
}
<span class="kwrd">public</span> <span class="kwrd">static</span> <span class="kwrd">bool</span> <span class="kwrd">operator</span> !=(A a, A b)
{
<span class="kwrd">return</span> !(a == b);
}
}
<span class="kwrd">public</span> <span class="kwrd">class</span> B : A
{
<span class="kwrd">public</span> <span class="kwrd">int</span> b;
<span class="kwrd">public</span> B(<span class="kwrd">int</span> a, <span class="kwrd">int</span> b)
: <span class="kwrd">base</span>(a)
{
<span class="kwrd">this</span>.b = b;
}
<span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">int</span> GetHashCode()
{
<span class="kwrd">return</span> <span class="kwrd">base</span>.GetHashCode() + b;
}
<span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">bool</span> Equals(<span class="kwrd">object</span> o)
{
<span class="kwrd">return</span> Util.AreSameClass(<span class="kwrd">this</span>, o) && <span class="kwrd">this</span>.EqualMembers((B)o);
}
<span class="kwrd">protected</span> <span class="kwrd">bool</span> EqualMembers(B o)
{
<span class="kwrd">return</span> <span class="kwrd">base</span>.Equals(o) && b == o.b;
}
}
}</pre></pre>
<span style="font-size:130%;"><span style="font-family:georgia;">The Util class is a helper class that helps find whether two objects are of the same class. If at least one is null then the objects are considered not being of the same class.</span>
<span style="font-family:georgia;">As we will see later, the handling of null objects is done elsewhere.</span>
<span style="font-family:georgia;">Then comes the base class </span></span><span style="font-style: italic;font-family:georgia;font-size:130%;" >A</span><span style="font-size:130%;"><span style="font-family:georgia;">. This class follows the good practices in term of implementation of GetHashCode().
<p>
In addition:
</p><p>
</p></span></span><ul style="font-family:georgia;"><li><span style="font-size:130%;">The class A overrides </span><span style="font-style: italic;font-size:130%;" >A.Equals(object o)</span><span style="font-size:130%;">. It </span><span style="font-size:130%;">first </span><span style="font-size:130%;"> tests whether <span style="font-style: italic;">this </span>and the object to be compared to are of the same class, using for that the above mentionned Util class. If both objects are of the same class, it then calls the protected, non virtual </span><span style="font-style: italic;font-size:130%;" >A.EqualMembers(A o)</span><span style="font-size:130%;"> method to compare </span><span style="font-size:130%;">two by two </span><span style="font-size:130%;">the member variables of the class A. </span></li><li><span style="font-size:130%;">As said before, the class A implements </span><span style="font-style: italic;font-size:130%;" >A.EqualMembers(A o)</span><span style="font-size:130%;"> . This function compares two objects of type A with respect to their member variables. For this, it does it in the most appropriate way. That is, by invoking </span><span style="font-style: italic;font-size:130%;" >Equals()</span><span style="font-size:130%;">, the </span><span style="font-style: italic;font-size:130%;" >== </span><span style="font-size:130%;">operator or </span><span style="font-style: italic;font-size:130%;" >object.ReferenceEquals()</span><span style="font-size:130%;"> if necessary. </span><span style="font-style: italic;font-size:130%;" >A.EqualMembers(A o)</span><span style="font-size:130%;"> is not meant to be redefined by subclasses. If that should happen, the subclass should simply calls </span><span style="font-style: italic;font-size:130%;" >base.EqualMembers(A o)</span><span style="font-size:130%;">. </span></li><li><span style="font-size:130%;">Class A also implements the dual operators </span><span style="font-style: italic;font-size:130%;" >==</span><span style="font-size:130%;"> and </span><span style="font-style: italic;font-size:130%;" >!=</span><span style="font-size:130%;"> operators. The == operator calls objects.Equals(), making sure that nulls are handled properly.</span></li></ul><span style="font-size:130%;"><span style="font-family:georgia;">The implementation of equals for subclass B is not more complex:</span>
<p>
</p></span><ul style="font-family:georgia;"><li><span style="font-size:130%;">Class B implements </span><span style="font-style: italic;font-size:130%;" >GetHashCode()</span><span style="font-size:130%;"> which calls </span><span style="font-style: italic;font-size:130%;" >base.GetHashCode()</span><span style="font-size:130%;">.</span></li><li><span style="font-size:130%;">Class B implements </span><span style="font-style: italic;font-size:130%;" >B.equals(object o)</span><span style="font-size:130%;"> the same way as class A.</span></li><li><span style="font-size:130%;">Class B implements EqualMembers(B o). This method first calls </span><span style="font-style: italic;font-size:130%;" >base.EqualMembers(o)</span><span style="font-size:130%;"> in order to compare the member variables defined by class A and then compares the member variables defined by class B.</span></li><li><span style="font-size:130%;">Class B does not need to implements the == operator anymore. </span></li></ul><span style="font-size:130%;"><span style="font-family:georgia;">One can ask why we have defined the non virtual methods EqualMember(). Usually, the role of comparing objects in a type safe way is given to </span></span><span style="font-style: italic;font-family:georgia;font-size:130%;" >IEquatable<t>.Equals(T o)</t></span><span style="font-size:130%;"><span style="font-family:georgia;">. The answer is simple, in that case, two objects of the same type (B) which are different but whose common parts (A) are the same would be equal if the equality is tested from within a method of class B.</span>
<span style="font-family:georgia;">In other words, the equality would return different results depending on the caller's context.</span>
<p>
<span style="font-family:georgia;">This is shown in the code below:</span></p><p>
</p><pre class="source-code">
<!-- code formatted by http://manoli.net/csharpformat/ -->
<pre class="csharpcode">
<span class="kwrd">using</span> System;
<span class="kwrd">using</span> System.Collections.Generic;
<span class="kwrd">using</span> System.Linq;
<span class="kwrd">using</span> System.Text;
<span class="kwrd">namespace</span> Equal
{
<span class="kwrd">public</span> <span class="kwrd">class</span> Util
{
<span class="rem">// Returns true if a and b are both non null and are of exactly the same class</span>
<span class="kwrd">public</span> <span class="kwrd">static</span> <span class="kwrd">bool</span> AreSameClass(Object a, Object b)
{
<span class="kwrd">return</span> a != <span class="kwrd">null</span> && b != <span class="kwrd">null</span> && a.GetType().Equals(b.GetType());
}
}
<span class="kwrd">public</span> <span class="kwrd">class</span> A
{
<span class="kwrd">private</span> <span class="kwrd">int</span> a;
<span class="kwrd">public</span> A(<span class="kwrd">int</span> a)
{
<span class="kwrd">this</span>.a = a;
}
<span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">int</span> GetHashCode()
{
<span class="kwrd">return</span> a;
}
<span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">bool</span> Equals(<span class="kwrd">object</span> o)
{
<span class="kwrd">return</span> Util.AreSameClass(<span class="kwrd">this</span>, o) && <span class="kwrd">this</span>.Equals((A)o);
}
<span class="kwrd">protected</span> <span class="kwrd">bool</span> Equals(A o)
{
<span class="kwrd">return</span> a == o.a;
}
<span class="kwrd">public</span> <span class="kwrd">static</span> <span class="kwrd">bool</span> <span class="kwrd">operator</span> ==(A a, A b)
{
<span class="kwrd">return</span> <span class="kwrd">object</span>.Equals(a, b); <span class="rem">// handle cases where a or b is null.</span>
}
<span class="kwrd">public</span> <span class="kwrd">static</span> <span class="kwrd">bool</span> <span class="kwrd">operator</span> !=(A a, A b)
{
<span class="kwrd">return</span> !(a == b);
}
}
<span class="kwrd">public</span> <span class="kwrd">class</span> B : A
{
<span class="kwrd">public</span> <span class="kwrd">int</span> b;
<span class="kwrd">public</span> B(<span class="kwrd">int</span> a, <span class="kwrd">int</span> b)
: <span class="kwrd">base</span>(a)
{
<span class="kwrd">this</span>.b = b;
}
<span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">int</span> GetHashCode()
{
<span class="kwrd">return</span> <span class="kwrd">base</span>.GetHashCode() + b;
}
<span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">bool</span> Equals(<span class="kwrd">object</span> o)
{
<span class="kwrd">return</span> Util.AreSameClass(<span class="kwrd">this</span>, o) && <span class="kwrd">this</span>.Equals((B)o);
}
<span class="kwrd">protected</span> <span class="kwrd">bool</span> Equals(B o)
{
<span class="kwrd">return</span> <span class="kwrd">base</span>.Equals(o) && b == o.b;
}
<span class="kwrd">static</span> <span class="kwrd">public</span> <span class="kwrd">void</span> test()
{
B b1 = <span class="kwrd">new</span> B(1, 2);
B b2 = <span class="kwrd">new</span> B (1,3);
<span class="rem">// casts</span>
A a2 = b2;
<span class="rem">// returns true althought b1 and b2 are different</span>
<span class="kwrd">bool</span> r = b1.Equals(a2);
}
}
}</pre>
</pre>
<p></p><p><span style="font-family:georgia;">To finish, here is a set of test cases:</span>
<!-- code formatted by http://manoli.net/csharpformat/ --></p></span><pre class="source-code"><pre class="csharpcode">
<span class="kwrd">using</span> System;
<span class="kwrd">using</span> System.Collections.Generic;
<span class="kwrd">using</span> System.Linq;
<span class="kwrd">using</span> System.Text;
<span class="kwrd">namespace</span> Equal
{
<span class="kwrd">class</span> Program
{
<span class="kwrd">static</span> <span class="kwrd">void</span> Main(<span class="kwrd">string</span>[] args)
{
B b1 = <span class="kwrd">new</span> B(1, 2);
B b2 = <span class="kwrd">new</span> B(1, 3);
B b3 = <span class="kwrd">new</span> B(1, 2);
<span class="rem">// casts</span>
A a1 = b1;
A a2 = b2;
A a3 = b3;
<span class="kwrd">object</span> o1 = b1;
<span class="kwrd">object</span> o2 = b2;
<span class="kwrd">object</span> o3 = b3;
<span class="kwrd">bool</span> r = <span class="kwrd">true</span>;
r &= b1.Equals(b1);
r &= b1.Equals(a1);
r &= b1.Equals(o1);
r &= a1.Equals(b1);
r &= a1.Equals(a1);
r &= a1.Equals(o1);
r &= o1.Equals(b1);
r &= o1.Equals(a1);
r &= o1.Equals(o1);
r &= b1 == b1;
r &= b1 == a1;
r &= (b1 == o1); <span class="rem">// reference equality</span>
r &= a1 == b1;
r &= a1 == a1;
r &= (a1 == o1); <span class="rem">// reference equality</span>
r &= (o1 == b1); <span class="rem">// reference equality</span>
r &= (o1 == a1); <span class="rem">// reference equality</span>
r &= (o1 == o1); <span class="rem">// reference equality</span>
r &= !(b1.Equals(b2));
r &= !(b1.Equals(a2));
r &= !(b1.Equals(o2));
r &= !(a1.Equals(b2));
r &= !(a1.Equals(a2));
r &= !(a1.Equals(o2));
r &= !(o1.Equals(b2));
r &= !(o1.Equals(a2));
r &= !(o1.Equals(o2));
r &= !(b1 == b2);
r &= !(b1 == a2);
r &= !(b1 == o2); <span class="rem">// reference equality</span>
r &= !(a1 == b2);
r &= !(a1 == a2);
r &= !(a1 == o2); <span class="rem">// reference equality</span>
r &= !(o1 == b2); <span class="rem">// reference equality</span>
r &= !(o1 == a2); <span class="rem">// reference equality</span>
r &= !(o1 == o2); <span class="rem">// reference equality</span>
r &= b1.Equals(b3);
r &= b1.Equals(a3);
r &= b1.Equals(o3);
r &= a1.Equals(b3);
r &= a1.Equals(a3);
r &= a1.Equals(o3);
r &= o1.Equals(b3);
r &= o1.Equals(a3);
r &= o1.Equals(o3);
r &= b1 == b3;
r &= b1 == a3;
r &= !(b1 == o3); <span class="rem">// reference equality</span>
r &= a1 == b3;
r &= a1 == a3;
r &= !(a1 == o3); <span class="rem">// reference equality</span>
r &= !(o1 == b3); <span class="rem">// reference equality</span>
r &= !(o1 == a3); <span class="rem">// reference equality</span>
r &= !(o1 == o3); <span class="rem">// reference equality </span>
}
}
}
</pre></pre>J-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.com0tag:blogger.com,1999:blog-152720317029563857.post-57924841641946190652009-04-26T21:33:00.017+02:002009-04-26T22:13:15.067+02:00Applicative functors: mapping a function to more than 3 lists<p>
Hello
</p><p>
Here is a short post that illustrates the power of higher level functions.
</p><p>
Everybody knows the List.map function that applies an arbitrary function to a list, producing a new list.
</p><pre class="source-code">
#light
List.map (fun x -> 2*x) [1;2]
</pre>
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.
<pre class="source-code">
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]
</pre>
But how do we do if we need a function List.map4 or List.map5 ? The straightforward solution is to explicitly write these functions.
<p>
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.
</p><p>
First, let's try to evaluate the expression:
</p><pre class="source-code">
List.map (fun x y -> x+y) [1;2]
</pre>We get the signature:
<pre class="source-code">val it : (int -> int) list
</pre>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:
<pre class="source-code">
List.map2 (fun x y -> x+y) [1;2] [3;4]
</pre>That is precisely what the operator <$> below does:
<pre class="source-code">let (<$>) fctList list = List.map2 (fun fct elem -> fct elem) fctList list
</pre>
Using both List.map and <$>, we can implement any mapping we want. I.e.
<pre class="source-code">
let r = List.map (fun x y z -> x+y+z) [1;2] <$> [1;2] <$> [1;2]
</pre>is equivalent to
<pre class="source-code">List.map3 (fun x y z -> x+y+z) [1;2] [1;2] [1;2]</pre>We can also, if we want, explicitly define the equivalent of List.map4
<pre class="source-code">
let map4 f l1 l2 l3 l4 = List.map f l1 <$> l2 <$> l3 <$> l4
</pre>
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.
<p>
</p><p>
In the litterature (and more specifically in Haskell) all the types that support a mapping function form the class
of <span style="font-style: italic;">Functors</span>.
</p><p>
The types that support both a mapping function and the <the> operator <> belong to the class of <span style="font-style: italic;">gt; belong to the class of <span style="font-style: italic;"><span style="font-style: italic;">Applicative Functors</span>.</span></span></the></p>J-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.com1tag:blogger.com,1999:blog-152720317029563857.post-47392792800757482552009-04-26T15:34:00.057+02:002009-05-03T23:21:25.307+02:00Functional Reactive Programming in F# (4)<span style="font-size:130%;"><span style="font-family:georgia;">In this post, I will introduce events in FRP.</span>
<p>
<span style="font-family:georgia;">Remember, a FRP is used to model systems that have an evolution with respect to continuous</span>
<span style="font-family:georgia;">time. However the way such a system computes its output(s) may be modified at discrete moments in time.</span>
<span style="font-family:georgia;">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.</span>
<span style="font-family:georgia;">This system behaves continuously until one of the three following events occur:</span>
</span><ul style="font-family:georgia;"><li><span style="font-size:130%;">The user changes speed.</span></li><li><span style="font-size:130%;">The user presses the velocity direction button.</span></li><li><span style="font-size:130%;">The ball hits a wall.</span></li></ul><span style="font-size:130%;">
<span style="font-family:georgia;">The first two events are what I called </span></span><span style="font-style: italic;font-family:georgia;font-size:130%;" >external </span><span style="font-size:130%;"><span style="font-family:georgia;">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.</span>
<span style="font-family:georgia;">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 </span></span><span style="font-style: italic;font-family:georgia;font-size:130%;" >internal </span><span style="font-size:130%;"><span style="font-family:georgia;">events.</span>
</span><p style="font-family:georgia;"><span style="font-size:130%;">
The goal of this post is to discuss such </span><span style="font-style: italic;font-size:130%;" >internal </span><span style="font-size:130%;">events.
</span></p><p><span style="font-size:130%;">
<span style="font-family:georgia;">Some let's start with our Behavior type and its run function.</span></span>
</p>
<pre class="source-code">
#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)
</pre>
<span style="font-size:130%;">
<span style="font-family:georgia;">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).</span>
<span style="font-family:georgia;">As usual, let's start the "hard way" by manually coding all the logic. Helpful combinators will be derived from this first coding.</span>
</span>
<pre class="source-code">
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
</pre>
<span style="font-size:130%;">
<span style="font-family:georgia;">Looking at <span style="font-style: italic;">colorB</span>, 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.</span></span>
<pre class="source-code">
let s = Seq.to_list (seq { for x in 1 .. 15 -> (float) x})
let r = run colorB s
</pre>
<span style=";font-family:georgia;font-size:130%;" >As always, the name of the game is to find abstractions (that is, combinators) to help us writing such event handling logic.
</span><p style="font-family:georgia;"><span style=";font-family:georgia;font-size:130%;" >
The next step is to move the event detection outside of the Behavior function. This is done by defining a </span><span style="font-style: italic;font-family:georgia;font-size:130%;" >cond</span><span style=";font-family:georgia;font-size:130%;" > function that returns <span style="font-style: italic;">None </span>if time is less than 10 seconds and <span style="font-style: italic;">Some blackB</span> when time is higher than or equal to 10 seconds.
</span></p><p style="font-family:georgia;"><span style=";font-family:georgia;font-size:130%;" >The </span><span style="font-style: italic;font-family:georgia;font-size:130%;" >cond </span><span style=";font-family:georgia;font-size:130%;" >function acts as a sort of event generator for <span style="font-style: italic;">colorB</span>.</span></p><p style="font-family:georgia;"><span style=";font-family:georgia;font-size:130%;" >Now, the Behavior function (bf) invoques </span><span style="font-style: italic;font-family:georgia;font-size:130%;" >cond </span><span style=";font-family:georgia;font-size:130%;" >and tests whether it returns <span style="font-style: italic;">None </span>of <span style="font-style: italic;">Some newBehavior</span>. If </span><span style="font-style: italic;font-family:georgia;font-size:130%;" >cond </span><span style=";font-family:georgia;font-size:130%;" >returns <span style="font-style: italic;">None</span>, then the <span style="font-style: italic;">colorB </span>Behaviors stays the same else <span style="font-style: italic;">colorB </span>becomes the new Behavior returns by </span><span style="font-style: italic;font-family:georgia;font-size:130%;" >cond </span><span style=";font-family:georgia;font-size:130%;" >(</span><span style="font-size:130%;"><span style="font-family:georgia;"><span style="font-style: italic;">newBehavior</span>).</span></span><span style=";font-family:georgia;font-size:130%;" >
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.
</span></p><p><span style=";font-family:georgia;font-size:130%;" >Moreover the handling of the event is always the same and does not depends on a particular event:
If cond is <span style="font-style: italic;">None</span>, then we do nothing special
if cond is <span style="font-style: italic;">Some newBehavior</span> then we replace the current Behavior by <span style="font-style: italic;">newBehavior</span>.</span><span style="font-size:130%;">
</span></p><pre class="source-code">
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
</pre>
<span style=";font-family:georgia;font-size:130%;" >
One more step. Looking at <span style="font-style: italic;">cond</span>, we see that it </span><span style=";font-family:georgia;font-size:100%;" ><span style="font-size:130%;"><span style="font-family:georgia;">only depends on time.</span>
<span style="font-family:georgia;">There is no particular reason to keep it defined within the definition of <span style="font-style: italic;">colorB</span>. </span>
<span style="font-family:georgia;">It could be passed as a parameter.</span></span>
</span>
<pre class="source-code">
// 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
</pre>
<span style=";font-family:georgia;font-size:130%;" >
</span><span style=";font-family:georgia;font-size:130%;" >The next step is more fundamental. The </span><span style="font-style: italic;font-family:georgia;font-size:130%;" >cond </span><span style=";font-family:georgia;font-size:130%;" >function depends on time. But we already have </span><span style=";font-family:georgia;font-size:130%;" >things </span><span style=";font-family:georgia;font-size:130%;" >that depends on time, namely Behaviors.
So why </span><span style="font-style: italic;font-family:georgia;font-size:130%;" >cond </span><span style=";font-family:georgia;font-size:130%;" >could not be a Behavior?
If fact, </span><span style="font-style: italic;font-family:georgia;font-size:130%;" >cond </span><span style=";font-family:georgia;font-size:130%;" >can well become a Behavior. One big advantage of this is that </span><span style="font-style: italic;font-family:georgia;font-size:130%;" >cond </span><span style=";font-family:georgia;font-size:130%;" >functions may have internal state, just like any Behavior.
</span>
<pre class="source-code">
// -- 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
</pre>
<span style=";font-family:georgia;font-size:130%;" >
Adapting <span style="font-style: italic;">createColor </span>is rather easy.</span><span style="font-size:130%;">
</span>
<pre class="source-code">
// 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
</pre>
<span style=";font-family:georgia;font-size:130%;" ><span style="">It is still possible to increase the abstraction level. Up to now <span style="font-style: italic;">createColor </span>explicitly depends on the value White. But taking a closer look to what we want, we can conclude that <span style="font-style: italic;">colorB </span>follows the rules:</span><span style=""> </span></span><ul style="font-family:georgia;"><li><span style="font-size:130%;">Before some time t0 (10 seconds here) <span style="font-style: italic;">colorB </span>is equal to a constant Behavior whose value is White.</span></li><li><span style="font-size:130%;">After that time, <span style="font-style: italic;">colorB </span>should be equal to the Behavior <span style="font-style: italic;">blackB</span>.</span></li></ul><span style=";font-family:georgia;font-size:130%;" > The <span style="font-style: italic;">switchB </span>function captures the essence of what we want: <span style="font-style: italic;">switchB </span>takes a Behavior as first argument and a condition Behavior as second. <span style="font-style: italic;">switchB </span>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.</span>
<pre class="source-code">
// 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
</pre>
<span style=";font-family:georgia;font-size:130%;" >
In the <span style="font-style: italic;">switchB </span>signature, a quite complex type appears: </span><span style=";font-family:georgia;font-size:130%;" > <span style="font-style: italic;">'a Beh option Beh .</span>
For the sake of clarity and to better discriminate between Behaviors and Events, a specific type is introduced for events:
</span>
<pre class="source-code">
// definition of event
type 'a Event = Evt of (Time -> ('a option * 'a Event))
</pre>
<span style=";font-family:georgia;font-size:130%;" >
And the <span style="font-style: italic;">switchB </span>function now becomes:</span><span style="font-size:130%;">
</span>
<pre class="source-code">
// 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
</pre>
<span style=";font-family:georgia;font-size:130%;" >
Here we are. In a next post I will present combinators and types to create various Events.
</span>J-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.com2tag:blogger.com,1999:blog-152720317029563857.post-61826069488905637472009-03-18T21:41:00.056+01:002009-03-25T23:14:50.481+01:00Functional Reactive Programming in F# (3)<p>
</p><p>
</p><p>
In the previous post, I showed how it was possible with the so-called residual state machine to implement a pure function that maintains a internal state.
In this post I will apply this technique to the behaviors discussed in my first post on functional reactive programming.
First, let's recall what a Behavior is:
</p><pre class="source-code">
#light
type Time = float
type 'a Beh = Beh of (Time -> 'a)
</pre>
To add the possibility to manage state, such a Behavior may be simply transformed into the new type below:
<span style="font-size:100%;"><pre class="source-code">#light
type Time = float
type 'a Beh = Beh of (Time -> ('a * 'a Beh))
</pre>Its associated runList evaluator is an exact copy of the one defined for a state machine.
<span style="font-size:100%;"><pre class="source-code">
// val runList : 'a Beh -> Time list -> 'a list
let rec runList (Beh bf) times =
match times with
|[] -> []
|h::t -> let (r, nb) = bf h
r :: runList nb t
</pre>
Simple Behaviors, that are independent of any state, are then easy to implement:
<span style="font-size:100%;"><pre class="source-code">
let rec doubleB =
let bf t = (2.0 * t, doubleB)
Beh bf
let rec twoB =
let bf t = (2, twoB)
Beh bf
let rec timeB = Beh (fun t -> (t, timeB))
</pre>
The following function is constB, similar to constB described in the first post.
It takes a value and transforms it into a Behavior that always returns that value, whatever the time.
<p>
Two equivalent implementations are possible.
</p><p>
The first possibility makes constB explicitly recursive:
<span style="font-size:100%;"><pre class="source-code">// val constB : 'a -> 'a Beh
let rec constB v =
let bf t = (v, constB v)
Beh bf
</pre>
The second creates a non recursive constB and requests the inner bf function to be recursive.
<span style="font-size:100%;">
<pre class="source-code">
let constB v =
let rec bf t = (v, Beh bf)
Beh bf
</pre>
As far as my experience tells me, the choice between these two possibilities is left free to the developer.</span></span></p><p><span style="font-size:100%;"><span style="font-size:100%;">
The lifting functions for our new Behaviors are also quite similar to the old ones.
<span style="font-size:100%;"><pre class="source-code">
// val liftB : ('a -> 'b) -> 'a Beh -> 'b Beh
let rec liftB f (Beh bf1)=
let bf t = let (r1, nb1) = bf1 t
(f r1, liftB f nb1)
Beh bf
// val lift2B : ('a -> 'b -> 'c) -> 'a Beh -> 'b Beh -> 'c Beh
let rec lift2B f (Beh bf1) (Beh bf2)=
let bf t = let (r1, nb1) = bf1 t
let (r2, nb2) = bf2 t
(f r1 r2, lift2B f nb1 nb2)
Beh bf
</pre>
</span></span></span></p></span></span></span><span style="font-size:100%;"><span style="font-size:100%;"><span style="font-size:100%;"><span style="font-size:100%;"><span style="font-size:100%;"><span style="font-size:100%;">
The next function is a good example of how function may be created by simple composition of other functions.
The function makeB takes a function from a time to some type 'a and returns the (state independent) Behavior that implements this function.
</span></span></span></span></span></span><span style="font-size:100%;"><span style="font-size:100%;"><span style="font-size:100%;"><span style="font-size:100%;"><span style="font-size:100%;"><span style="font-size:100%;"><span style="font-size:100%;"><pre class="source-code">//val makeB : (Time -> 'a) -> 'a Beh
let makeB f = (liftB f) timeB
</pre>
As a comparison, here is the same makeB function implemented the usual way.
<span style="font-size:100%;"><pre class="source-code">
let makeB f =
let rec bf t = (f t, Beh bf)
Beh bf
</pre>
Now, what comes is an example of Behavior that manages state.
Suppose that we have a function that is passed a state in addition to a time variable, makeWithStateB is a combinator that transform that function into a Behavior.
<span style="font-size:100%;"><pre class="source-code">
// val makeWithStateB : ('state -> Time -> 'a * 'state) -> 'state -> 'a Beh
let rec makeWithStateB f (previousState:'state) =
let bf t = let (a1, nextState) = f previousState t // call f with the previous state
(a1, makeWithStateB f nextState) // pass the next state, returned by f to the next Behavior
in Beh bf
</pre>
Here is a simple example that returns the delta between the current time and a previous base time.
Everytime the delta reaches 10, the delta is reset to zero and the current time becomes the
new base time.
<span style="font-size:100%;"><pre class="source-code">
let f t0 t = if (t-t0 < 10.0)
then (t-t0, t0)
else (0.0, t)
let times = Seq.to_list (seq { for i in 0 .. 100 -> float i })
let r = runList fB times
</pre></span></span></span></span></span></span></span></span></span></span>J-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.com3tag:blogger.com,1999:blog-152720317029563857.post-85256199626692934502009-02-15T00:01:00.009+01:002009-02-15T00:09:26.187+01:00Quicksort in F# (again)Here is the quicksort algorithm in F#.
Nothing new here, this algorithm can be found on many sites. But I noticed that none of them takes advantage of partial application of (<) and (>=) operators in List.filter.
<p><span style="font-size:100%;"><pre class="source-code">#light
let rec quicksort l =
match l with
|[] -> []
|h::t -> quicksort (List.filter ((<) h) t) @ [h] @ (quicksort (List.filter ((>=) h) t))
let l = [8;2;10;5;3;6;12;23;1;2;5;11]
quicksort l
</pre></span></p>J-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.com0tag:blogger.com,1999:blog-152720317029563857.post-44117248058243558952009-02-14T23:43:00.061+01:002009-02-16T22:32:32.476+01:00Functional Reactive Programming in F# (2)<br>
In my previous post about <a href="http://call-with-cc-en.blogspot.com/2008/12/functional-reactive-programming-in-f-1.html">Functional Reactive Programming</a>, we have seen how a continuous function of time could be implemented in F# (Behaviors) and how it was possible to create more complex Behaviors by combining simpler Behaviors.
However, such Behaviors are in fact 'pure' functions of time, without any state.
In this post, we will see how Behaviors can handle state in a functional way (without side effects).
We start by considering a very simple state machine that consumes unit values () and produces a succession of boolean values: true, false, true, false...
Let's start with a classic, imperative implementation:
<p><span style="font-size:100%;"><pre class="source-code">#light
type 'a StateMachine = unit -> 'a
let TogglingMachine =
let state = ref true
let bf evt = state := not (!state)
!state
in (bf :bool StateMachine)
let eventList = [(); (); (); ()]
let r = List.map TogglingMachine eventList
</pre>Here, a state machine that produces results of type 'a is simply represented as a function from unit to 'a.
Here is a second example.
The next machine accepts a unit option as input value and returns a result which is defined as follows:
<ul><li>If the input value is None then the machine returns -1.</li><li>If the input value is Some() then the machine returns the number of None received since the last Some().</li></ul><p><span style="font-size:100%;"><pre class="source-code">
type 'a StateMachine = unit option -> 'a
let CountingMachine : int StateMachine =
let nbNone = ref 0
let bf evt = match evt with
|None -> nbNone := !nbNone + 1;
-1
|Some _ -> let res = !nbNone;
nbNone := 0;
res
in bf
let eventList = [None; None; Some(); None; Some(); Some(); None]
let r = List.map CountingMachine eventList
</pre>
In both examples above, we see that the machine needs to retain some state between two invocations and it does it with the help of some side effects (ref 0 and ref true).
There are several solutions to create state machines without side effects. The general idea is to design a machine that externalizes its state. In practice, that means:
<ul><li>Its state should be given as an additional input argument.</li><li>The machine produces a result that, in addition to itsexpected output, contains its new state.</li></ul>
Let's illustrate this with the previous example (the CountingMachine above).
First, we have to modify the type representing the machine. It is now a function that takes 2 arguments. The first one is the previous state of the machine (the state before the call) and the second is the usual unit option value. The state is simply the current count of None values.
This function returns a pair made of the count of None as explained above and the new state of the machine after the call.
<p><span style="font-size:100%;"><pre class="source-code">
type StateMachine = int -> unit option -> (int * int)
let CountingMachine : StateMachine =
let bf previousCount evt =
match evt with
|None -> (-1, previousCount+1)
|Some _ -> (previousCount, 0)
in bf
</pre>It is now the responsibility of the caller to make sure that the right state is passed to the Machine. For this, we can define a runList function which runs the machine against a list of inputs.
<p><span style="font-size:100%;"><pre class="source-code">
let rec runList previousCount machine events =
match events with
|[] -> []
|event::t -> let (res, nextCount) = machine previousCount event
nextRes :: runList nextCount machine t
let r = runList 0 CountingMachine eventList
</pre>We see clearly the drawbacks of such a solution. The runList function must be aware of two things:
<ul><li>The first, as already mentionned, is the handling of the state. Unfortunately, in this solution and in the next solution (a little bit below), this cannot be avoided.</li><li>The other drawback is the dependency of runList on the type of the state - int in this case. Thus, every Machine designed on state externalization needs its own runList function.</li><li>A third drawback, a bit less obvious at first sight, is the fact that the state must always be of the same type across several calls. It is not possible to replace, from one call to another, such a Machine with another that has a state of a different type.</li></ul>
Of course, the type for the machine presented above may be made generic:
<p><span style="font-size:100%;"><pre class="source-code">
type StateMachine<'a, 'state> = 'state -> unit option -> ('a * 'state)
</pre>
Last solution, based on residual state machines.
This solution is based on a simple fact. Since a State Machine is basically a function of one argument, let's imagine that this function returns both its expected value and new State Machine. This a new State Machine acts a bit like the state in the previous example.
The type of such a machine is:
<p><span style="font-size:100%;"><pre class="source-code">
type 'a StateMachine = SM of (unit option -> ('a * 'a StateMachine))
</pre>
We can already define some simple state machines:
A machine that always returns true. Two implementation are possible, depending on which definition is recursive.
<p><span style="font-size:100%;"><pre class="source-code">
let AlwaysTrueMachine = let rec bf evt = (true, SM bf)
SM bf
let rec AlwaysTrueMachine = let bf evt = (true, AlwaysTrueMachine)
SM bf
</pre>The Toggling Machine in the beginning of this post becomes.
<p><span style="font-size:100%;"><pre class="source-code">
let TogglingMachine = let rec bf previous evt = (previous, SM (bf (not previous)))
SM (bf true)
</pre>
To be able to run these machines, we must again define a runList function:
<p><span style="font-size:100%;"><pre class="source-code">
let rec runList (SM bf) events =
match events with
|[] -> []
|h::t -> let (r, nb) = bf h
r :: runList nb t
let r = runList TogglingMachine eventList
</pre>This runList function is somewhat similar to the one already defined above but with 2 advantages:
<ul><li>It does not depend on the way the state machine models its state (or not - see the AlwaysTrueMachine which has no state at all).</li><li>As a consequence, a state machine may well change its state representation at will. The only condition is that the values it produces must have the same type.</li></ul>
So we come to the end of this post. As a last note, I must admit that there could be another way to model state machines, which is based on sequences but I have not explored this direction yet.
In a next post, I will make the connection between state machines and Behaviors.
</span></p><p>
</p><p>
</p><p>
</p><p><span style="font-size:100%;">
</span></p></span></p></span></p></span></p></span></p></span></p></span></p></span></p></span></p>J-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.com1tag:blogger.com,1999:blog-152720317029563857.post-7767844410581895542008-12-10T21:58:00.006+01:002009-04-26T15:34:31.591+02:00Functional Reactive Programming in F# (1)<p><span style="font-size:100%;"></span> </p> <p><span style="font-size:100%;">Hello,</span></p> <p><span style="font-size:100%;">This message is the first of a series describing my exploration of Functional Reactive Programming (FRP).</span></p> <p><span style="font-size:100%;">Although I already had quite a bit of experience with imperative reactive programming, I discovered FRP while reading the book of Paul Hudak: </span><span style="font-size:100%;">"The Haskell School of Expression".</span></p>Articles about FRP have also been published by<a href="http://haskell.cs.yale.edu/yale/publications.html"> The Yale Haskell Group</a> . Most of the contents of this message and the followings has been quite largely inspired by these sources of information. <p></p> <p>I started my own implementation of a FRP library with 2 goals in mind: </p> <ul> <li>To gain a better understanding about this very peculiar domain. </li><li>To assess F# in a real functional context.</li></ul>To begin with, here is just a short reminder of what FRP is. A functional, reactive program is a program written in a functional language ( where side effects are inexistent or at least limited to a minimum) and producing results that depend on time, in a continuous manner on one hand and on discrete events on the other hand. I will first introduce a F# type called Behavior. A Behavior willl represent a quantity that vary with time in a continuous way. <p></p>Considering that time is a float, a Behavior that corresponds to a quantity of type 'a is: <p><span style="font-size:100%;"><pre class="source-code">#light
type Time = float
type 'a Behavior = Time -> 'a
</pre>Although this choice is correct, we rather use the next one. The very reason of this will be made clear in a following post. </span>
</p><p></p>
<p><span style="font-size:100%;"><pre class="source-code">type 'a Behavior = Beh of (Time -> 'a)
</pre>With this simple type, it is already easy to define some behavior.</span>
</p><p></p>
<p><span style="font-size:100%;"></span></p>
<table width="1010" border="1" cellpadding="2" cellspacing="0">
<tbody>
<tr>
<td valign="top" width="344"><span style="font-size:100%;"><strong>Kind of Behavior </strong></span></td>
<td valign="top" width="664"><span style="font-size:100%;"><strong>Implementation</strong></span></td></tr>
<tr>
<td valign="top" width="345"><span style="font-size:100%;">The constant 1 </span></td>
<td valign="top" width="664">
<p><span style="color: rgb(0, 0, 128);font-family:courier new;font-size:100%;" >let oneB = Beh (fun _ -> 1.0)</span></p></td></tr>
<tr>
<td valign="top" width="345"><span style="font-size:100%;">The constant "hello world!"</span></td>
<td valign="top" width="664">
<p><span style="color: rgb(0, 0, 128);font-family:courier new;font-size:100%;" >let helloB = Beh (fun _ -> "Hello World!")</span></p></td></tr>
<tr>
<td valign="top" width="345"><span style="font-size:100%;">The time itself </span></td>
<td valign="top" width="664">
<p><span style="color: rgb(0, 0, 128);font-family:courier new;font-size:100%;" >let timeB = Beh (fun t -> t)</span></p></td></tr>
<tr>
<td valign="top" width="345"><span style="font-size:100%;">The time times 3 </span></td>
<td valign="top" width="664">
<p><span style="color: rgb(0, 0, 128);font-family:courier new;font-size:100%;" >let time3B = Beh (fun t -> t * 3.0)</span></p></td></tr>
<tr>
<td valign="top" width="345"><span style="font-size:100%;">Sine of the time </span></td>
<td valign="top" width="664"><span style="color: rgb(0, 0, 128);font-family:courier new;font-size:100%;" >let sinB = Beh (fun t -> System.Math.Sin t)</span></td></tr>
<tr>
<td valign="top" width="345"><span style="font-size:100%;">Sine of the triple of the time </span></td>
<td valign="top" width="664"><span style="color: rgb(0, 0, 128);font-family:courier new;font-size:100%;" >let sin3B = Beh (fun t -> System.Math.Sin (t * 3.0))</span></td></tr></tbody></table>
<p><span style="color: rgb(0, 0, 128);font-family:courier new;" ></span></p><span style="font-size:100%;"></span>
<p><span style="font-size:100%;">To ease the creation of behavior, we can write some useful combinators:</span> </p>
<p><span style="font-size:100%;"><strong><u>constB</u></strong>: transforms a constant into a Behavior: </span></p>
<p><span style="font-size:100%;"><pre class="source-code">//val constB : 'a -> 'a Behavior
let constB v = let bf t = v
in
Beh bf
let oneB = constB 1
let helloB = constB "Hello World!"
</pre></span>
</p><p></p>
<p><span style="font-size:100%;">Considering the last 3 Behavior, the situation is a bit more complex. I.e. time3B looks very much like to timeB and it even seems possible to express time3B in terms of timeB: </span></p>
<p><span style="font-size:100%;"><pre class="source-code">let time3B = let (Beh time) = timeB
let bf = fun t -> 3.0 * (time t)
in Beh bf
</pre></span>
</p><p></p>
<p><span style="font-size:100%;">time3B can be further modified if timeB and the partial application </span><span style="font-size:100%;">((*) 3.0) are moved outside of the body of time3B: </span></p>
<p><span style="font-size:100%;"><pre class="source-code">let time3B = let liftB f b = let (Beh bf) = b
let lbf = fun t -> f (bft)
in Beh lbf
in liftB ((*) 3.0) timeB
</pre>Now, liftB is independent from the rest and can be defined as a stand alone combinator: </span>
</p><p></p>
<p><span style="font-size:100%;"><pre class="source-code">// val liftB : ('a -> 'b) -> 'a Behavior -> 'b Behavior
let liftB f b = let (Beh bf) = b
let lbf = fun t -> f (bf t)
in Beh lbf
</pre>As a result, not only time3 but also sinB and sin3B can be defined using liftB: </span>
</p><p></p>
<p><span style="font-size:100%;"><pre class="source-code">let time3B = liftB ((*) 3.0) timeB
let sinB = liftB System.Math.Sin timeB
let sin3B = liftB System.Math.Sin (liftB ((*) 3.0) timeB)
</pre>We see that combinators such as liftB allow us to combine Behavior and functions in order to create new Behavior. However the syntax is still a bit heavy. </span>
</p><p></p>
<p><span style="font-size:100%;">The syntax can be simplified quite a lot if we look at the signature of liftB. It is a function that takes as (first) argument a function that maps a value of type 'a to a value of type 'b. liftB then returns a function that maps a value of type 'a Behavior to a value of type 'b Behavior.</span></p>
<p><span style="font-size:100%;">liftB is a function that transforms a function defined 'in the world ' of any type (a', 'b) into a function defined in the world of Behavior.</span></p>
<p>We can then write: </p>
<p><span style="font-size:100%;"><pre class="source-code">let sinF = liftB System.Math.Sin
let sinB = sinF timeB
let tripleF = liftB ((*) 3.0)
let sin3B = sinF (tripleF timeB)
</pre>In the same way, combinators that lift function with many arguments can be defined.</span>
</p><p></p>
<p><span style="font-size:100%;"><pre class="source-code">//val lift2B : ('a -> 'b -> 'c) -> 'a Behavior -> 'b Behavior -> 'c Behavior
let lift2B f b1 b2 = let (Beh bf1) = b1
let (Beh bf2) = b2
let nbf t = f (bf1 t) (bf2 t)
in Beh nbf
//val lift3B : ('a -> 'b -> 'c -> 'd) -> 'a Behavior -> 'b Behavior -> 'c Behavior -> 'd Behavior
let lift3B f b1 b2 b3 = let (Beh bf1) = b1
let (Beh bf2) = b2
let (Beh bf3) = b3
let nbf t = f (bf1 t) (bf2 t) (bf3 t)
in Beh nbf
</pre>Here are some examples of lifted functions. </span>
</p><p></p>
<p><span style="font-size:100%;"><pre class="source-code">// val ( .* ) : (int Behavior -> int Behavior -> int Behavior)
let (.*) = lift2B (*)
// val ( ./ ) : (int Behavior -> int Behavior -> int Behavior)
let (./) = lift2B (/)
// val mapB : ('a -> 'b) Behavior -> 'a list Behavior -> 'b list Behavior
let mapB f b = (lift2B List.map) f b
</pre>Rem: because of the (almost) ubiquity of the "Value Restriction" error, mapB must be defined as a real function, its 'f' and 'b' arguments must appear explicitly.</span>
</p><p></p>
<p><span style="font-size:100%;"><pre class="source-code">error FS0030: Value restriction. Type inference has inferred the signature
val mapB : (('_a -> '_b) Behavior -> '_a list Behavior -> '_b list Behavior)
Either define 'mapB' as a syntactic function, or add a type constraint to instantiate the type parameters.
</pre>Before ending this first post, here are a couple of functions that execute a Behavior, that is, invoque the time to value function held/transported by a Behavior. </span>
</p><p></p><pre class="source-code">// val runOne : 'a Behavior -> Time -> 'a
let runOne b t = let (Beh bf) = b
in
bf t
// val runList : 'a Behavior -> Time list -> 'a list
let runList b t = let (Beh bf) = b
in
List.map bf t
// val runSeq : 'a Behavior -> seq<Time> -> seq<'a>
let runSeq b t = let (Beh bf) = b
in
Seq.map bf t
</pre>J-Chttp://www.blogger.com/profile/16452395026472444125noreply@blogger.com0